Problem 1999

The sought functions are those of the form $f(n) = c \cdot \nu_p(n)$, where $p$ is some prime, $c$ is a positive integer, and $\nu_p(n)$ denotes the exponent of $p$ in the prime decomposition of $n$.

Solution 1. If a number $n$ is a product of primes, $n = p_1p_2\cdots p_k$, then
$$f(n) = f(p_1) + f(p_2) + \cdots + f(p_k),$$
in particular, $f(1) = 0$ (since $f(1) = f(1) + f(1)$).
It is also clear that $f(n) = 0$ implies $f(p) = 0$ for all primes $p$ dividing $n$.
Let us call a positive integer $n$ good if $f(k) = f(n-k)$ for $0 < k < n$. If $n$ is good then each its divisor $d$ is also good; indeed, if $n = dm$, then
$$f(k) = f(mk) - f(m) = f(n - mk) - f(m) = f(m(d - k)) - f(m) = f(d - k)$$
for $0 < k < d$. Thus, good numbers are products of good primes.
It follows immediately from (1) that there exists a prime $p$ such that $f(p) \neq 0$; let $p$ be the smallest such prime. Then $f(r) = 0$ for all $r < p$ (since all prime divisors of $r < p$ are less than $p$). Now every good number $n > p$ must be divisible by $p$. Indeed, if $n = pk + r$ is a good number, $k > 0$, $0 < r < p$, then $f(p) \le f(pk) = f(n - pk) = f(r) = 0$, a contradiction. Since any divisor of a good number is also good, this means that if a divisor $r$ of a good number is not divisible by $p$, it is less than $p$. Thus all good numbers have the form $r \cdot p^k$ with $r < p$. The condition (3) implies that $k$ can be arbitrarily large, consequently all powers of $p$ are good.

If $q \neq p$ is a prime, $p^{q-1}-1$ is divisible by $q$ and $p^{q-1}$ is good. Then $f(q) \le f(p^{q-1}-1) = f(1) = 0$, that is, $f(q) = 0$.
Now, we see that $f(n) = \nu_p(n) \cdot c$, where $c = f(p)$. The conditions (1) and (2) for all such functions with $c \neq 0$ are obvious; the condition (3) holds for all $n = p^m$, since $\nu_p(p^m - k) = \nu_p(k)$ when $0 < k < p^m$.

Solution 2. We use the notion of a good number from the previous solution. As above, we also denote by $\nu_p(n)$ the exponent of a prime $p$ in the prime decomposition of $n$.
Say that a positive integer $k$ is big if $f(k) > 0$. Let $\mathcal{B}$ be the set of big primes, and let $p_1 < p_2 < \dots$ list the elements of $\mathcal{B}$ (this set might be either finite or infinite). By the problem conditions, we have
$$f(n) = \sum_{i} \nu_{p_i}(n) f(p_i); \qquad (B1)$$
thus, the big numbers are those divisible by at least one big prime.
For a positive integer $k$, define its essence $e(k)$ to be the largest product $e$ of (not necessarily different) big primes such that $e \mid k$. In other words,
$$e(n) = \prod_{p_i \in \mathcal{B}} p_i^{\nu_{p_i}(n)}.$$
This yields that $k/e(k)$ is not big, so $f(k) = f(e(k)) + f(k/e(k)) = f(e(k))$.
Lemma. Assume that $n$ is a good number. Then $e(k) = e(n-k)$ for all $0 < k < n$.
Proof. Arguing indirectly, choose a minimal $k$ for which the claim of the lemma is violated. Clearly, $k$ is big, as otherwise $f(k) = f(n-k) = 0$ and hence $e(k) = e(n-k) = 1$.
There are $t = k/e(k)$ multiples of $e(k)$ in each of the segments $[1, k]$ and $[n-k, n-1]$. On the other hand, there are $t-1$ such multiples on $[1, k-1]$ — and, by minimality of $k$, on $[n-k+1, n-1]$ as well. This yields that $n-k$ is a multiple of $e(k)$. Therefore,
$$f(e(k)) = f(k) = f(n-k) = f(e(k)) + f\left(\frac{n-k}{e(k)}\right),$$
so the last summand vanishes, hence $\frac{n-k}{e(k)}$ has no big prime divisors, that is, $e(n-k) = e(k)$. This contradicts to our choice. □
Back to the problem, assume that $|\mathcal{B}| \ge 2$. Take any good number $n > p_1p_2$, and let $p_1^\alpha$ be the largest power of $p_1$ smaller than $n$, so that $n \le p_1^{\alpha+1} < p_1^\alpha p_2$. By the lemma, $e(n-p_1^\alpha) = e(p_1^\alpha) = p_1^\alpha$, which yields $p_1^\alpha | n$. Similarly, $p_2 | n$, so that $n \ge p_1^\alpha p_2$. This contradiction shows that $|\mathcal{B}| \le 1$, which by (B1) yields that $f$ is listed in the answer.

Solution 3. We have $f(\prod p_i^{\alpha_i}) = \sum \alpha_i f(p_i)$. Note that
$$f(n-1) + f(n-2) + \dots + f(n-k) \ge f(1) + f(2) + \dots f(k)$$
for all $k = 1, 2, \dots, n-1$, since the difference LHS - RHS is just $f\left(\binom{n-1}{k}\right)$. Assume that $f(p) > 0$. If $f(k) = f(n-k)$ for all $k$, it implies that $\binom{n-1}{k}$ is not divisible by $p$ for $k = 1, 2, \dots, n-2$. It is well known that it implies $n = a \cdot p^s$, $a < p$. If there are two primes $p, q$ such that $f(p) > 0$, $f(q) > 0$, there exist only finitely many $n$ which are equal both to $a \cdot p^s$, $a < p$, and $b \cdot q^t$, $b < q$. So there exists at most one such $p$, and therefore $f(n) = C \cdot \nu_p(n)$ for some constant $C$.

Solution 4. We call a function $f : \mathbb{N} \to \mathbb{N}_0$ satisfying (2) additive. We call a pair $(f, n)$, where $f$ is an additive function and $n \in \mathbb{N}$, good, if for all $k < n$ it holds $f(k) = f(n-k)$. For an additive function $f$ and a prime number $p$ the number $\frac{f(p)}{\ln p}$ is denoted by $g(f, p)$.
Let $(f, n)$ be a good pair such that $f(p) > 0$ for at least two primes less than $n$. Let $p_0$ be the prime with maximal $g(f, p)$ among all primes $p < n$. Let $a_0$ be the maximal exponent such that $p_0^{a_0} < n$. Then $f(k) < f(p_0^{a_0})$ for all $k < p_0^{a_0}$. Indeed, if $k = p_1^{a_1} \cdots p_m^{a_m} < p_0^{a_0}$, then
$$\begin{align*} f(k) &= a_1 f(p_1) + \dots + a_m f(p_m) \\ &= g(f, p_1) a_1 \ln p_1 + \dots + g(f, p_m) a_m \ln a_m \\ &< g(f, p_0) a_0 \ln p_0 = f(p_0^{a_0}). \end{align*}$$

Let $n = bp_0^{a_0} + r$, where $0 < r < p_0^{a_0}$. Then $f(r) = f(bp_0^{a_0}) \ge f(p_0^{a_0})$. This contradiction shows that $p_0^{a_0} | n$. Then $n = p_0^{\nu_{p_0}(n)}n'$, where $n' \le p_0$.
The function $f_1(m) := f(p_0)\nu_{p_0}(m)$ and $f_2 := f - f_1$ are additive (obviously $f(m) \ge f(p_0^{\nu_{p_0}(m)}) = f_1(m)$, since $p_0^{\nu_{p_0}(m)}$ divides $m$). For $k < n$, $\nu_p(k) = \nu_p(n-k)$. Hence the pair $(f_2, n)$ is also good. Note that $f_2(p_0) = 0$.
Choose among all primes $p < n$ the prime $q_0$ with maximal $g(f_2, p)$. As above we can prove that $n = q_0^{\nu_{q_0}(n)}n''$ with $n'' < q_0$. Since $p_0 \ne q_0$, we get a contradiction. Thus $f(n) = f(p) \cdot \nu_p(n)$.