The only functions that work are $f(x)=f(p) \cdot \nu_p(x)$ for some prime $p$ with $f(p)>0$ By the first condition $\exists \, p$ such that $f(p)>0$. Call all $n$ satisfying (iii) as "good". For a good $n$ we have : $$f\left( \binom {n-1}{k} \right)= \sum_{i=1}^{n-1} f(i) - \sum_{i=1}^{k}f(i) - \sum_{i=1}^{n-k-1}f(i)= \sum_{i=n-k}^{n-1} f(i) - \sum_{i=1}^{k}f(i) =0$$ Now note that if $p\mid m$, we must have that $f(m)>0$. Hence for all large enough good $n$, we have that $p \not \vert \tbinom {n-1}{k}$. By Lucas's theorem we have that $n=a\cdot p^b$ for some $a<p$. Now assume there exists a prime $p'\neq p$ with $f(p')>0$. Then all large enough good $n$ must also be of the form $a' \cdot p'^{b'}$. However only finitely many such $n$ can exist, so $p$ is the only prime satisfying $f(p)>0$. Now its easy to that $f(x)=f(p) \cdot \nu_p(x)$ for all $x\in \mathbb N$.

We use the notion of "good" as in the above post. Property (ii) allows us to write, for each positive integer $n$, $$f(n) = \sum_{p \text{ prime}} f(p) \cdot v_p(x).$$ It is easy to check with (ii) that all divisors of good positive integers are good as well (and as always, $f(1) = 0$). The main goal is to prove that $f(p) \neq 0$ for at most one prime $p$; the rest should be immediate. First, we prove that there are only finitely many good prime numbers. The main claim is as follows. Claim: If $p$ is a good prime then $f(k) = 0$ for all $k < p$. Proof: For $p = 2$ this is clear, so assume that $p > 2$. We then proceed by induction on $k$. Suppose that for some $2 \leq k_0 < p$, we have $f(k) = 0$ for all $k < k_0$. Take some $1 \leq k < k_0$ such that $p \equiv k \pmod{k_0}$. Then, $f(p - k) = f(k) = 0$ by induction hypothesis. Since $k_0 | p - k$, we get $f(k_0) = 0$. $\square$ This means that all the good positive integers have their prime divisors among these finitely many good prime numbers. Now, since there are infinitely many good positive integers, but only finitely many of which are prime, there must exist a good prime number $p$ such that $p^k$ is good for all $k \geq 1$. Indeed, suppose for the sake of contradiction that this is not the case. For each good prime number $p$, let $k_p$ be the maximum such $p$. Then it is easy to see that there can be no good positive integer greater than $\prod_{p \text{ good}} p^{k_p} < \infty$; a contradiction. Finally, for each prime $p' \neq p$, there exists some $k \geq 1$ such that $p' | p^k - 1$. Thus, $f(p') \leq f(p^k - 1) = 0$, implying $f(p') = 0$. We are done.

We claim $f(n)=k\nu_p(n)$, for some prime $p$ and constant $k$. It is easy to see that this works, now we show that any $f$ must be of that form. Let $p$ be the smallest number for which $f(p) \not = 0$. By condition (i), $p$ must be prime. Call a number $n$ an $S$-thing if $f(a)=f(b)$ whenever $a+b=n$. Lemma 1: For any $S$-thing $s$, either $s\le p$ or $p\mid s$. Proof: Assume $s\ge p$. Since $f(1)=f(2)=\cdots=f(p-1)=0$, we also have $f(s-1)=f(s-2)=\cdots=f(s-(p-1))=0$. If $p\nmid s$, then one of $\{s-1,s-2,\ldots,s-(p-1)\}$ is a multiple of $p$. But since $f(p)>0$, this contradicts condition (ii). $\blacksquare$ Lemma 2: Any divisor of an $S$-thing is also an $S$-thing. Proof: Suppose $s$ is an $S$-thing, and $d\mid s$. Let $d'=s/d$. We want to show that for any $a$ and $b$ with $a+b=d$, we have $f(a)=f(b)$. If $a+b=d$, then $ad'+bd'=s$, which means $f(ad')=f(bd')$. Hence $f(a)+f(d')=f(b)+f(d')$, and hence $f(a)=f(b)$. $\blacksquare$ Full characterization of $S$-things: Combining Lemma 1 and Lemma 2, we can fully characterize all $S$-things: any $S$-thing is of the form $\ell \cdot p^n$ for some $n\ge 1$ and for some $\ell < p$. It suffices to show that for any prime $q\not = p$, we have $f(q)=0$, from which the claimed function $f$ follows simply from condition (i). We want to find an $S$-thing whose restricted zone contains a multiple of $q$, where the restricted zone of $x$ is defined to be $\{x-1,x-2,\ldots,x-(p-1)\}$. This is because for an $S$-thing $x$, we proved in Lemma 1 that $f$ maps every value in the restricted zone of $x$ to $0$. If we can prove one of these is a multiple of $q$, then we are done by condition (i). By the characterization, the $\nu_p$ of $S$-things grows arbitrarily large. Hence $p^{q-1}$ divides some $S$-thing, so by Lemma 2, $p^{q-1}$ is an $S$-thing. Since $q\mid p^{q-1}-1$ and $p^{q-1}-1$ is in the restricted zone of $p^{q-1}$, we are done.

Let $y=1$ and we can get $f(1)=0$. Use (ii) iteratively and we can get $f(n)=\sum_{p|n}\nu_p(n)f(p)$. There exists at least one prime $p$ s.t. $f(p)\neq 0$; otherwise, $\forall n\in\mathbb N, f(n)=0$. Assume that there exist two primes $p$ and $q$ s.t. $f(p), f(q)\neq 0$, and WLOG let $p$ be the smallest one, $q$ be the second smallest one. Suppose $n$ satisfies the condition (iii). Let's have an induction on $j$ to prove that $\forall j\leq\log_pn,\ p^j|n$. For the base case $j=0$ is trivial. Assume that for $j=k-1$, $p^{k-1}|n$. For $j=k$, let $n=mp^{k-1}$ and we have $\forall 1\leq i\leq p-1,\ f(m-i)+(k-1)f(p)=f(n-p^{k-1}i)=f(p^{k-1}i)=(k-1)f(p)+f(i)=(k-1)f(p)(\because i\leq p-1)$. $\Rightarrow\forall 1\leq i\leq p-1,\ f(m-i)=0$ $\Rightarrow p|m$, and we get $p^k|n$. $\therefore$ by induction, $p^{\lfloor\log_pn\rfloor}|n$ In another word, $n=m_1p^{k_1}$, where $1\leq m_1\leq p-1$. $\Rightarrow\forall 1\leq i\leq n-1,\ \nu_p(i)=\nu_p(n-i)$, which means the value of $f(p)$ doesn't effect the condition (iii). $\Rightarrow$ We can then assume that $q$ is the smallest prime and have the same induction on $q$, and get that $n=m_2q^{k_2}$, where $1\leq m_2\leq q-1$. $k_2=\nu_q(n)=\nu_q(m_1)+k_1\nu_q(p)=0$ $\Rightarrow 1\leq n\leq q-1$, only finite $n$ satisfies the condition, which makes a contradiction. $\therefore$ there is exactly one prime $p$ s.t. $f(p)\neq 0$. Also, $\forall k\in\mathbb N,\ f(p^k)$ satisfies the condition (iii). $\therefore f(x)=c\nu_p(x)$, where $c\in\mathbb N$ and $p\in\mathbb P$

All the solutions are $f(n)=mv_p(n)$ for some prime $p$ and $m\in\mathbb N$. It is easy to see that $f$ satisfies $(i)$ and $(ii)$. For $(iii)$, it suffices to take $n=p^{\alpha}$ for each $\alpha\in\mathbb N$. We now show that this class of function is the only solution. By $(i)$ pick the smallest $p$ scuh that $f(p)\neq 0$. If $p$ is not a prime say $p=qr$, where $p>q\geq r>1$, then $\max\{f(q),f(r)\}\geq 1$, wchih contradicts the minimality of $p$. Let $P=\{p_1,p_2,...\}$ be the set of primes where $f(p_i)\neq 0$ and $p_1<p_2<...$ Then from $(ii)$ and simple induction we have $$f(n)=\sum_{p\in P}f(p)v_{p}(n)$$ If $k=1$ then we are done. Otherwise, assume $k\geq 2$ suppose the integers in (iii) are $n_1,n_2,...$ Claim.$n_1=mp_1^{\alpha}$ where $m<p_1$, $(m,p_1)=1$ and $\alpha\in\mathbb Z_{\geq 0}$ Proof. Otherwise suppose for some $i$, $n_i=mp_1^{\alpha_i}$ where $m>p_1$. Let $m=bp_i+c$, where $0<c<p_1$ then $$f(p_1^{\alpha_i}c)=f(p_1^{\alpha_i})+f(c)=f(p_1^{\alpha_i})=\alpha_if(p_i)$$ but $$f(n_i-p_1^{\alpha_i}c)=f(p_1^{\alpha_i+1}b)\geq f(p_i)(\alpha_i+1)$$ contradiction. $\blacksquare$ Therefore, by pigeonhole principle there exists $m$ such that for infinitley many $i$, $n_i$ can be written as the form $$n_i=mp_1^{\alpha}$$ where $m<p$ and $(m,p_1)=1$, $\alpha\in\mathbb Z_{\geq 0}$. \newline\newline Notice that $f(m)=0$ so let $k=\alpha-p_2+1$, where $i$ is sufficiently large such that $k>0$, then $$f(mp_i^k)=f(m)+f(p^k)=f(p_i)k$$ but $$f(mp_1^{\alpha}-mp_1^k)=f(mp_1^k)f(p^{\alpha-k}-1)\geq f(mp_1^k)+f(p_2)\geq f(mp_1^k)+1$$ since $p_2|p_1^{\alpha-k}-1$ by Fermat Little Theorem. This contradiction completes the proof.

Aryan-23 wrote: Hence for all large enough good $n$, we have that $p \not \vert \tbinom {n-1}{k}$. By Lucas's theorem we have that $n=a\cdot p^b$ for some $a<p$. I am quite confused, how did u apply Lucas, can someone plz explain..

Answer. $f(n)=k v_p(n)$ for some fixed positive integer $k$ and a prime $p$. Verification is easy. Claim 1. $f(1)=0$. Proof. $f(1)=f(1\cdot 1)=f(1)+f(1)$, so $f(1)=0$. $\square$ Call a positive integer $n$ good if $f(k)=f(n-k)$ for all $k<n$. Condition $(iii)$ tells that there are infinitely many good numbers. Claim 2. Let $n$ be a good number. Then any divisor $d$ of $n$ is also good. Proof. Define $e$ by $n=de$. Pick a positive integer $k<d$. Then $$f(k)+f(e)=f(ke)=f(n-ke)=f((d-k)e)=f(d-k)+f(e)$$ Hence $f(k)=f(d-k)$ for all $k<d$. $\square$ Pick a minimal positive integer $p$ with $f(p)>0$. Claim 1 implies $p>1$. Assume $p$ is composite. Then $p=ab$ for some posittive integers $a,b>1$. Since $f(p)=f(a)+f(b)$ we must have $f(a)>0$ or $f(b)>0$, contradiction. Hence $p$ is prime. Claim 3. Any good number is of the form $p^e m$ for a nonnegative integer $e$ and a positive integer $m\le p-1$. Proof. Assume $n$ is good. Write $n=p^e m$ with $p\nmid m$. Assume $m>p$. By claim 2, $m$ is good. Write $m=qp+r$ with $r<p$. Then $0=f(r)=f(qp)=f(q)+f(p)>0$, contradiction. $\square$ Corollary 4. All powers of $p$ are good. Proof. Let $k$ be a nonnegative integer. Pick a good number $n\ge p^{k+1}$. By claim 2, $n=p^e m$ for nonnegative integer $e$ and a positive integer $m\le p-1$. Hence $p^{e+1}>p^e m=n\ge p^{k+1}$, so $e\ge k$. Hence $p^k\mid n$, so by claim 2 the number $p^k$ is good. $\square$ Claim 5. For every prime $q$ different than $p$ we have $f(q)=0$. Proof. By Fermat's little theorem, $p^{q-1}=1+qm$ for a positive integer $m$. Corollary 4 implies that $p^{q-1}$ is good, so $0=f(1)=f(qm)=f(q)+f(m)$. Therefore $f(q)=0$. $\square$ By $(ii)$, $f(n)=0$ for all positive integers $n$ prime to $p$. Now let $n$ be an arbitrary positive integer. Then $n=p^{v_p(n)}m$ with $p\nmid m$. Assume $f(p)=k$. By construction, $k>0$. By $(ii)$, $f(n)=k v_p(n)$.

The answer is $f(x) \equiv c \nu_p(x)$ for some $c \in \mathbb{N}$ and some prime $p$. Call a positive integer $\textbf{GOOD}$ if and only if it fulfills condition $(iii)$ $\color{green}\boxed{\textbf{Some Simple But Useful Observation}}$ 1.$f(p_1^{\alpha_1} \ldots p_k^{\alpha_k}) = \alpha_1f(p_1) + \ldots + \alpha_k f(p_k)$ 2.$\text{If } p \mid k \ \text{and} f(k)=0 \ \text{then} \ f(p)=0$ 3.$\textbf{The Function Doesn't Have an Upper Bound}$ $\color{magenta} \rule{25 cm}{1 pt}$ $\color{green} \boxed{\textbf{Claim 1.}}$ There exist infinitely many positive integers $k$ such that all $\textbf{GOOD}$ integers greater than $k$ is divisible by $k$. Let there exist only finitely many. Then there exist $N \in \mathbb{N}$ such that for every $k \geq N$, there exist a $\textbf{GOOD}$ integer $n > k$ which is not divisible by $k$. Then there must exist an integer $1 \leq x \leq k-1$ such that $k \mid n-x$. From condition $(iii)$ we have $$\begin{align*} f(x) &= f(n-x) \\ &= f(k) + f\left( \dfrac{n-x}{k}\right) \\ &\geq f(k) \end{align*}$$ So for every $k \geq N$, $f(k) \leq \text{max}\{f(1),\ldots,f(k-1)\}$. Thus, we have $f(x) \leq \text{max}\{f(1),\ldots,f(N-1) \}$ for every $x \in \mathbb{N}$. This cause the function to have an upper bound (Contradiction). So, the claim is true. $\color{magenta}\rule{25 cm}{1 pt}$ Call a positive integer $\textbf{OP}$ if and only if it fulfill the condition from $\color{green} \boxed{\textbf{Claim 1.}}$. It is obvious that if $x,y$ is $\textbf{OP}$, then $\text{LCM(x,y)}$, is also $\textbf{OP}$ (This is crucial). $\color{green} \boxed{\textbf{Claim 2.}}$ If $p$ is a prime such that $\nu_p(x)$ over all $\textbf{OP}$ integers $x$ doesn't have an upper bound, then $f(p)=0$. By infinite PHP, there must exist an $\textbf{OP}$ integer $q_1^{\alpha_1}\ldots q_k^{\alpha_k} \times t$ such that $\alpha_1+\ldots+\alpha_k=p-1$ and $q_1\equiv q_2 \equiv \ldots q_k \not \equiv 0\ (\text{mod} \ p)$. Then for some $\textbf{GOOD}$ integer $q_1^{\alpha_1} \ldots q_k^{\alpha_k} \times tm$, we have $$f(tm (q_1^{\alpha_1} \ldots q_k^{\alpha_k}-1)) = f(tm)$$ $$f(tm) + f(q_1^{\alpha_1} \ldots q_k^{\alpha_k}-1) = f(tm)$$ $$f(q_1^{\alpha_1} \ldots q_k^{\alpha_k}-1)=0$$ Since by FLT $p \mid q_1^{\alpha_1} \ldots q_k^{\alpha_k} -1$, then $f(p)=0$. Thus, the claim has been proven. $\color{magenta}\rule{25cm}{1 pt}$ $\color{red} \boxed{\textbf{Finishing}}$ Since if $x,y$ is $\textbf{OP}$ then $\text{LCM}(x,y)$ is also $\textbf{OP}$, we have that the number of prime $p$ that doesn't fulfill the condition of $\color{green} \boxed{\textbf{Claim 2.}}$ is at most $1$. In other words, the number of prime $p$ such that $f(p) \ne 0$ is at most $1$. From here, it is trivial to obtain $f(x) \equiv c \nu_p(x)$ for some $c \in \mathbb{N}$ and some prime $p$. Hence, we are done.

P(x,1) gives $f(1)=0$. Now let S be the set of all integers satisfying (iii) and let p be the smallest prime for which $f(p) \neq 0$. Claim 1: Every element of S is of the form $p^ab$ where $1 \leq b \leq p-1$. First we prove the following lemma: Lemma: $n \in S, n>p$, then $p \mid n$. Proof: Suppose for sake of contradiction,$n=kp+j$ with $j \neq 0$. So $f(np)=f(j) \Longrightarrow f(j)=f(n)+f(p)>0 \because f(p)>0$. But now $j \leq p-1$ which means all prime factors of j are less than p. So by definition of p, $f(j)=0$. Contradiction. Now suppose $n=p^ab$ with $g(b,p)=1$. Then note that $\forall c<b$, we have $f(p^ab-p^ac)=f(p^ac)$. But by second condition, this gives: $af(p)+f(b-c)=af(p)+f(c) \forall c<b \Longrightarrow f(b-c)=f(c) \forall c<b$. So $b \in S$. Since $g(b,p)=1$ and $b \in S$, $b<p$. This proves the claim. Claim 2: For every prime q>p, f(q)=0 Lemma: If q is the smallest prime >p for which $f(q) \neq 0$, then there is no $n \in S,n>q$ Proof: Suppose for sake of contradiction there exists such an n. Let $n=qk+r, 0 \leq r<q$. Case 1:$r \neq 0$. Now we have $f(r)=f(qk)=f(q)+f(k)>0 \because f(q)>0$. So by definition of q, we must have $p \mid r \Longrightarrow p \mid k$. Let $v_p(n)=a$. Repeating the same logic, we obtain $p^a \mid k,r$. So let $k=p^ak_0,r=p^ar_0 \Longrightarrow n=p^a(qk_0+r_0)$. But then by claim 1, $qk_0+r_0<p<q$. But then this means $k_0=0$, a contradiction. Case 2: $r=0$ This gives $n=qk \Longrightarrow q \mid n$. But by claim 1, $n=p^ab$ for some a, $b<p$. So $q \mid p^ab \Longrightarrow q \mid b \Longrightarrow q \leq b<p$, a contradiction. This proves the lemma. Since S is an infinite set there are always terms greater than q in S. This proves the claim. Combining claims 1 and 2, it is clear that $f(x)=v_p(x)f(p)$.

$$\begin{tabular}{p{12cm}} The answer is $\boxed{f(n) = Nv_p(n)}$ for some $N \in \mathbb{N}$. It's easy to see that they work; set $n = p^l$, $l \geq 1$ to be the numbers satisfying the third assertion --- as $v_p(k) = v_p(p^l-k)$ for every $k < p^l$. \end{tabular} \\ $$ Perfect 50-50 balanced NT/Alg problem. While (my) Main Claim is certainly A-flavored, the rest makes use of heavy NT-oriented-pigeonholes-and-primroots, so a mix of both is required here. Call the numbers which are supposed to satisfy the third assertion $\color{green} \textbf{\textit{stabilizers}}$. So, the numbers $p^l$ are the stabilizers in our solution set. $\color{green} \rule{6.5cm}{2pt}$ $\color{green} \clubsuit$ $\boxed{\textbf{Main Weapon of Destruction.}}$ $\color{green} \clubsuit$ $\color{green} \rule{6.5cm}{2pt}$ For every $n$ stabilizer, $m \mid n$ is also a stabilizer. That implies that for every $p^k \mid n$, $p^k$ is a stabilizer. (What a perfect way to set up $n = p^l$ being a stabilizer for every $l \geq 1$, is it not?) $\color{green} \rule{25cm}{0.5pt}$ $\color{green} \spadesuit$ $\boxed{\textbf{Suprisingly Fast Proof.}}$ $\color{green} \spadesuit$ We'd like to prove that $f(k) = f(m-k)$ for every $k$ smaller than $m$. Letting $q$ (quotient) be $$q = \dfrac{n}{m}$$ we know that $f(qk) = f(n-qk)$ for every $qk < n$; i.e. for every $k < \dfrac{n}{q} = m$. In turn, since $$f(q)+f(k) = f(qk) = f(n-qk) = f(q)+f(m-k)$$ this implies the desired conclusion. $\blacksquare$ Now, we consider the stabilizers in the form of $p^k$ for some $p$ prime. For each $p$, define its $\color{cyan} \textbf{\textit{stabilizer-height}}$ to be the (theoretical) maximum $k$ so that $p^k$ is a stabilizer while $p^{k+1}$ is not. If this number does not exist, say its stabilizer-height to be $+\infty$. Moreover, call the amount $d$ of primes which are stabilizers to be the $\color{cyan} \textbf{\textit{stabilizer-dimension}}$. Again, if there is no upper bound for this (i.e. the number is not finite) say that $d$ is equal to $+\infty$. $\color{cyan} \rule{6.5cm}{2pt}$ $\color{cyan} \clubsuit$ $\boxed{\textbf{Fat Upwards or Fat Sideways.}}$ $\color{cyan} \clubsuit$ $\color{cyan} \rule{6.5cm}{2pt}$ Either there exists a prime $p$ with $+\infty$ stabilizer-height or the number $d$ is equal to $+\infty$. Else, the third assertion about stabilizers being infinite will be false. $\color{cyan} \rule{25cm}{0.5pt}$ $\color{cyan} \spadesuit$ $\boxed{\textbf{Proof.}}$ $\color{cyan} \spadesuit$ Let there are finite primes which are stabilizers (let they are $p_1,p_2,\dots,p_d$) with each of them having finite stabilizer-height (let the heights be $h_1,h_2,\ldots,h_d$, respectively). Then, all stabilizers are divisors of the number $$L = p_1^{h_1}p_2^{h_2}\ldots p_d^{h_d}$$ That is because if any number $m$ is a stabilizer with $m \nmid L$, then there exists $p_i^{k_i} \mid m$ so that $k_i > h_i$, contradicting our assumption. $\color{cyan} \rule{25cm}{0.5pt}$ We now tackle the first case (which more resembles the solution set); where one particular prime $p$ has infinite stabilizer-height. $\color{red} \rule{3cm}{2pt}$ $\color{red} \clubsuit$ $\color{red} \boxed{\textbf{First Case.}}$ $\color{red} \clubsuit$ $\color{red} \rule{3cm}{2pt}$ We claim that if $p$ has an infinite height, then $f(n) \equiv Nv_p(n)$ for some $N$. Note that this implies that the other primes $q \ne p$ are irrelevant; that $p$ is the only prime-base which is $\textbf{alive}$. $\color{red} \rule{25cm}{0.5pt}$ $\color{red} \spadesuit$ $\color{red} \boxed{\textbf{Proof.}}$ $\color{red} \spadesuit$ First we establish that the other primes give null values ($f(q) = 0$ for $q \ne p$). This is actually very easy, as we know that $f(1) = f(p^{q-1}-1) = 0$ since $p^q$ is a stabilizer and $f(1) = 0$. Also, we know that $q \mid p^{q-1}-1$ by FLT, so $$0 = f(p^{q-1}-1) = f(q)+ f\left(\dfrac{p^{q-1}-1}{q}\right) \geq f(q)$$ implying the result. Let $f(p) = N$. Then, if $$n = p^l \prod_{p_i \ne p} p_i^{\alpha_i}$$ then $f(n) = lf(p)+\sum\alpha_i f(p_i) = lN = N \cdot v_p(n)$. $\blacksquare$ $\blacksquare$ $\color{blue} \rule{3.5cm}{2pt}$ $\color{blue} \diamondsuit$ $\color{blue} \boxed{\textbf{Second Case.}}$ $\color{blue} \diamondsuit$ $\color{blue} \rule{3.5cm}{2pt}$ First, recall that $f(1) = 0$ by plugging $m = n = 1$ to the second assertion. Now, there existing infinite stabilizers mean that some odd prime $p$ is a stabilizer, so $$0 = f(1) = f(p-1) = f(2) + f\left(\dfrac{p-1}{2} \right) \geq f(2)$$ implying $f(2) = 0$. $\color{blue} \rule{25cm}{0.5pt}$ By the first assertion, there exist primes which do not have a zero image. Let $p_k$ being the first of them; so we get $f(p_1 = 2) = 0$, $f(3) = 0$, and so on, until $f(p_{k-1}) = 0$ and $f(p_k) \ne 0$. Consider $f(g)$ where $g$ is a primitive root of $p_k$. Since all of $g$'s prime factors will obviously be $p_{k-1}$ or less, we know that $f(g) = 0$. In turn, this will cause $f(g^k) = 0$ for $1 \leq k \leq p-1$. So, for each residue $r$ modulo $p$, set $n_r$ so that $f(n_r) = 0$ and $n_r \equiv r \pmod p$ (this is the only time where the primitive root drives the Solution forward, but this is very crucial.) $\color{magenta} \rule{25cm}{0.5pt}$ Finally we Claim that there exists no primes $\color{magenta} p > \text{max}(n_1,n_2,\ldots,n_{p_k-1},p_k)$ so that $\color{magenta} p$ is a stabilizer. $\color{magenta} \rule{25cm}{0.5pt}$ Let $p$ is greater than all of them, and $p \equiv s \pmod{p_k}$. By that, $p$ being a stabilizer implies $$0=f(n_s) = f(p-n_s) = f(p_k) + f\left( \dfrac{p-n_s}{p_k} \right) \geq f(p_k) > 0$$ since $p_k \mid p-n_s$ (and $p-n_s > 0$, too). This yields a blatant contradiction. As we have exhausted all the cases, we are done. $\blacksquare$ $\blacksquare$ $\blacksquare$

Pretty nice. Note that condition (ii) just gives $$f(n) =\sum_{p \text{ prime}} v_p(n)f(p)$$ Then, condition (i) implies that $f(p) \neq 0$ for at least one prime $p$. Call all such primes good, and take $p$ to be the smallest good prime. If $f(q)=0$ for all other primes $q$, then we get the solution $$\boxed{f(n)= A \cdot v_p(n) \ \ \forall n \in \mathbb{N}}$$ where $A>0$ is any constant. This indeed works: conditions i) and ii) are satisfied trivially, and condition iii) is satisfied whenever $n$ is a power of $p$. Otherwise, let $q$ be the second smallest good prime. Choose an $n>q$ satisfying condition (iii). Let $m$ be the largest positive integer satisfying $p^m \leq n$. Claim 1: $n=lp^m$ for some $1 \leq l \leq p-1$. Proof: Call $n=n_0$ for now. Since $f(k)=0$ for all positive integers $k<p$, we must have $f(n-k)=0$ as well $\implies$ $p \nmid n-k$ for $k=1,2, \dots p-1$ $\implies$ $p \mid n=n_0$. Let $n_1=\frac{n_0}{p}$. If $n_1<p$, we are done. Else, note that $f(kp)=f(p)$ for all positive integers $k<p$, and $kp<p^2 \leq pn_1$, so $f(pn_1-pk)=f(p)$ as well $\implies$ $f(n_1-k)=0$ $\implies$ $p \nmid n_1-k$ for $k=1,2, \dots p-1$ $\implies$ $p \mid n_1$ $\implies$ $p^2 \mid n$. Then we can define $n_2=\frac{n_1}{p}$ and keep continuing the process until we get $p^m \mid n$. Then, since $p^{m+1}>n$, we will have $n=lp^m$ for some $1 \leq l \leq p-1$, and we are done. $\blacksquare$ Claim 2: $v_p(k)=v_p(n-k)$ for all positive integers $k<n$. Proof: Since $k<n<p^{m+1}$, we must have $v_p(k) \leq m$. If $v_p(k)<m=v_p(n)$, we are trivially done. Else, assume $k=l'p^m$ for some $l'<l$. Then, $n-k=(l-l')p^m$, and $0 < l-l' < l<p$, so $v_p(n-k)=m$ as well, and we are done. $\blacksquare$ Now, clearly $q \nmid n$ since $q \neq p$ and $l<q$. Therefore $q \mid n-r$ for some positive integer $r<q<n$. Note that the only good prime that can possibly divide $r$ is $p$, and so $f(r)=v_p(r)f(p)$. $$\implies f(n-r) \geq v_p(n-r)f(p)+f(q) = v_p(r)f(p)+f(q)=f(r)+f(q)>f(r)$$ Contradiction! Therefore there are no solutions in this case. $\blacksquare$

Here's a quick solution: Observation:If $f(k)=0$ then each prime divisor $r$ of $k$ has the property $f(r)=0$. Trivially it suffices to define f on the set of primes. Let $p$ the least prime for which $f(p)$ is nonzero, thus for each integer $x<p$ we have $f(x)=0$. We are going to prove for every other prime $q$ we have $f(q)=0$. Define $A$ the set of the positive integers having the property of the third condition. Key claimThere is no M such that $M\geq U_{p}(a)$ where $a \in A$ Proof: FTSOC assume the statement is not true i.e there exist such M. By infinite PHP there is a $\epsilon$ such that $U_{p}(a)=\epsilon$ for infinitely many a \in A. Let $n=p^{\epsilon}c$ where $(c,p)=1$. Obviously there are infinitely many such $c$ thus take c arbitrarily large. Set now $k=p^{\epsilon}u^{r}$ where $u<p$ is a primitive root mod p.Equivalently $f(c-u^{r})=rf(u)=0$. As (c,p)=1 there is r such that $p \mid c-u^{r}$, hence $f(p)=0$ by the observation, absurd. That ends the proof of the claim. Now it is easy to finish: Pick a sufficiently large $M$ such that $U_{p}(n)=M$ where $n \in A$ and write $n=p^{M}c$ where $(c,p)=1$. Thus $f(p^{M}c-k)=f(k)$. Choose now k=p^{t}c and we get $f(p^{M-t}-1)=0$. For each prime $q$ different from $p$ there is a t such that $q-1 \mid M-t$ and by FLT $q \mid p^{M-t}-1$, implying that $f(q)=0$. Thus $f(p)=c$ and $f(q)=0$for each prime q different from p. We conclude that $f(x)=cU_{p}(x)$.

My highest NT ISL solve Repost cause the acronym synonymous to lol apparently counts as offensive language now so my first post was taken down Here's my solution during my country's TST

Note that $f(x) = \sum_{p | x} v_p(x)f(p)$. Define $d(k,p)$ to be the greatest divisor of $k$ relatively prime to $p$ where $k$ is a positive integer and $p$ is a prime. Clearly $f(k) = f(d-k)$ for all $k$ whenever $f(k) = f(n-k)$ for all $k$ and $d | n$. Note that we can set $d = d(n,p)$ here. Additionally, over all $n$-values as in condition $3$, $d(n,q)$ can be bounded for at most $1$ prime $q$. We consider $2$ cases. Case $1$: There is no such $q$. We proceed with strong induction to prove the following claim: If $p$ is a prime and $f(r) = 0$ for all $r < p$, then $f(p) = 0$. For the base case, since $d(n,2)$ is unbounded, we can choose $n$ such that $d(n,2) > 1$. Then $f(2)\le f(d(n,2) - 1) = f(1) = 0$, as desired. For the induction step, choose $n$ with sufficiently large $d(n,p)$ and let $d(n,p) = mp + r$ with $r < p$. Then $f(p)\le f(mp) = f(r) = 0$, and the induction step is complete. But then $f\equiv 0$, which contradicts the first condition. Case $2$: There is $1$ such $q$. We proceed with strong induction to prove the following claim: If $p\neq q$ is a prime and $f(r) = 0$ for all $r < p$ relatively prime to $q$, then $f(p) = 0$. For the base case, we will consider $2$ subcases. If $q$ is odd, then $f(2) = 0$ by the same exact reasoning as in case $1$. If $q = 2$, consider any $n = m\cdot 2^k$ for odd $m$ and sufficiently large $k$, which exists since $d(n,2)$ is bounded. Then $3 | d(m,3)\cdot 2^e - 1$ for some $e\in \{1,2\}$, and hence $f(3)\le f(d(m,3)\cdot 2^e - 1) = f(1) = 0$, as desired. For the induction step, consider any $n$ such that $v_q(n) > \log_q{(p)}$, which exists since $d(n,q)$ is bounded. As in case $1$, let $d(n,p) = mp + r$ with $r < p$. Since $q^{\lfloor\log_q{(p)}\rfloor + 1} | mp + r$ and $v_q{(r)}\le \log_q{(p)}$, clearly $v_q{(r)} \le v_q{(m)}$. But then $f(p)\le f\left(\frac{mp}{q^{v_q{(r)}}}\right) = f(d(r,q)) = 0$, and the induction step is complete. But this means $f(p) = 0$ for all $p\neq q$, and hence $f(x) = f(q)v_q{(x)}$, which clearly satisfies all $3$ conditions, is the only solution.

It is clear that we must have $f(n)=f\left(\prod_{p prime} p^{v_p(n)}\right)=\sum_{p prime}f(p)v_p(n)$, where the $f(p)$ must be nonnegative, and at least one must be greater than $0$. Let $p$ be the smallest such prime. Let the numbers in iii) be of the form $n=p^kt$, with $(t,p)=1$. Assume $t=ap+r$, with $a>0$ and $0<r<p$ (i.e. $t>p$). Then we must have $kf(p)+f(t-r)=f(p^kt-p^kr)=f(p^kr)=kf(p)+f(r)=kf(p)$ because $0<r<p$. This implies $f(t-r)=0$ which is impossible since $p|t-r$ and $t-r>0$. Therefore all numbers from iii) must be of the form $p^kt$ with $0<t<p$. Since it is clear that $f(n)=f(p)v_p(n)$ works, let $g(n)=f(n)-f(p)v_p(n)$, which preserves the additive property and still satisfies the same set of $n$ from iii). So let $q$ be the smallest prime (which must be greater than $p$) such that $g(q)>0$ (if it exists). Then by the same logic we must have that all the numbers from iii) must be of the form $q^kt$, with $0<t<q$. However, if $p^kt$ is bigger than $q$ (it can be arbitrarily big since there are infinitely many) we have a contradiction since it isncoprime with $q$ (because $0<p,t<q$). Thus $g(q)=0$ for all primes. In other words $f(x)=f(p)v_p(x)$ for all $x$, which clearly works.

The answer is $f(x)=k\cdot \nu_p(x)$ for some integer $k>0$ and prime $p$. These clearly work, so we now show that no other solutions exist. Clearly $f$ is determined uniquely by the values it attains over the primes. If $f(p)=0$ for all primes $p$, then $f \equiv 0$ which is not allowed. If $f(p)\neq 0$ for exactly one prime $p$, we obtain the solution set above. Henceforth suppose $f(p) \neq 0$ for at least two primes $p$. Pick the least two primes that satisfy this, and let them be $p<q$. Let $S$ be the set of all $n$ such that $a+b=n \implies f(a)=f(b)$. I will now prove the following lemmas: Lemma 1: If $n \in S$, then either $p \mid n$ or $n<p$. Proof: Suppose otherwise, so we can write $n=pn'+k$ for $p>k \neq 0$ and $n'>0$. We then have $f(p) \leq f(pn')=f(k)$, so $f(k) \neq 0$, which contradicts the minimality of $p$. Lemma 2: If $n \in S$, then any divisor of $n$ is also in $S$. Proof: Write $n=ab$. Then $f(ax)=f(ay) \implies f(x)=f(y)$ for any $x,y$ with $x+y=b$, hence $b \in S$. Combining the above lemmas, it follows that if $n \in S$ then $n$ is of the form $p^ka$, where $k \geq 0$ and $1\leq a<p$. Since $S$ is unbounded, it follows that $\nu_p(n)$ where $n \in S$ is unbounded, as we have $n<p^{\nu_p(n)+1}$ for all $n \in S$. Now pick some $n \in S$ with $\nu_p(n)\geq\log_p(q)$, from which it follows that $n\geq q$. Now write $n=aq+b$, where $0<b<q$ (we cannot have $b=0$ because that would imply $q \in S$, contradicting lemma 1). If $\nu_p(aq)=\nu_p(a) \neq \nu_p(b)$, then $\nu_p(n)\leq \nu_p(b)$. However, since $b<q$ it follows that $\nu_p(b)<\nu_p(n)$ for size reasons, which is a contradiction. Hence we have $\nu_p(a)=\nu_p(b)$. Since $n \in S$, we have $f(aq)=f(b)$. By the minimality of $p$ and $q$, since $b<q$ we have $f(b)=f(p)\nu_p(b)$. But we also have $f(aq)=f(a)+f(q)\geq f(p)\nu_p(b)+f(q)$, which implies $f(q)=0$: a clear contradiction. Hence we have at most one prime $p$ with $f(p)\neq 0$, as desired. $\blacksquare$

The answer is and $f(x) \equiv c \nu_p(x)$ for any prime $p$ and constant $c \ge 0$. These obviously work. For the other direction, let $\mathcal M$ be the set of integers satisfying the sum condition. Claim: $\mathcal M$ is closed under division. Proof. Tautological. $\blacksquare$ Now assuming $f$ is not identically zero, fix $p$ the smallest prime for which $f(p) > 0$. Claim: This prime $p$ divides any element of $\mathcal M$ which is greater than $p$. Proof. Suppose $m \in \mathcal M$ and $m > p$. Use division algorithm to get $m = p \cdot s + r$ where $0 \le r < p$. If $r > 0$, then $$f(r) = f(p \cdot s) = f(p) + f(s) > 0$$ a contradiction to minimality of $p$. $\blacksquare$ Claim: Every element of $\mathcal M$ equals a power of $p$ times an integer less than or equal to $p$. Proof. Follows from the last two claims. $\blacksquare$ Assume for contradiction $q$ is a prime greater than $p$ and with $f(q) > 0$. For some $p^e \in M$ exceeding $q$, use the division algorithm to get $$p^e - qs = r < q$$ and hence $$f(q) + f(s) = f(r), \qquad r < q.$$ But evidently $\nu_p(s) = \nu_p(r)$ and $\nu_q(r) = 0$, hence $f(s) = f(r)$, contradiction.

Any function of the form $f(n)=v_p(n)f(p)$ for a fixed prime $p$ satisfies the problem conditions. Call a natural $n$ good if it satisfies the condition 3. Claim 1:If a natural $n$ is good,so are all its divisors $d$ Proof:Let $n=dk$.Since $n$ is good,we have $f(kl)=f(kd-kl)$.By using condition 2,we get $f(l)=f(d-l)$ for all naturals $l<d$. Suppose there exist 2 distinct primes $p$ and $q$ for which $f(p)\neq 0$,$f(q)\neq 0$ and $p$ is the least prime for which its image is non zero. Claim 2:$f(k)=0$ for all $k<p$. Proof:Trivially it is true because $k$ has all prime factors $<p$ for which their images is $0$ by the choice of $p$,and k can be expressed as $\Sigma v_r(k)f(r)$ for all its prime factors $r$ Therefore if their exist good $n$ for which $n>p^{v_p(n)}$, then taking $m$ as $\frac{n}{p^{v_p(n)}}$, If $m>p$ we get by Claim 2 $0=f(m (mod p))=f(m-m(modp))\geq f(p)>0$, a contradiction. Therefore all good numbers are of the form $p^ks$ where $s<p$. If there exist some good $n$ for which $v_p(n)\geq q-1$ Then by Claim 1 ,$p^{q-1}$ is good. But by Fermat's Little Theorem, $$0<f(q)\leq f(p^{q-1}-1)=f(1)=0$$ a contradiction. Therefore all good numbers are of the form $p^ks$ where $k<q-1$ and $s<p$. But then this would make the set of good numbers to be finite,a contradiction. Therefore the assumption about the existence of $q$ is false. Also by condition 1 and condition 2 there exists atleast one prime $p$ for which $f(p)\neq 0$ Thus we conclude that the above stated family of functions are only possible$\blacksquare$

Let $S$ be the set of all $n$ satisfying condition $(iii)$. Claim: There exists a prime $p$ so that $f(p)>0$. Proof: If not, then $f\equiv 0$, a contradiction $\blacksquare$. Let $p$ be the smallest such prime. Claim: If $n\in S$, then either $n\ge p$ or $p|n$. Proof: Note $f(1)=f(2)=\ldots=f(p-1)$. Suppose $n>p$. Then $f(n-1)= f(n-2)= \ldots=f(n-(p-1))=0$. If $p\nmid n$, then one of these is a multiple of $p$, a contradiction $\blacksquare$. Claim: If $n\in S$, then any positive integer divisor of $n$ is in $S$. Proof: Let $d$ be a divisor of $n$. We want to show that for all $x+y=d$, $f(x)=f(y)$. Indeed, $$f(x\cdot \frac{n}{d})=f(y\cdot \frac{n}{d})\implies f(x)+f(\frac{n}{d})=f(y)+f(\frac{n}{d})\implies f(x)=f(y)$$ $\blacksquare$ So all $n\in S$ can be written as $a\cdot p^k$, where $k$ is a nonnegative integer and $0<a< p$ Claim: All powers of $p$ are in $S$. Suppose $p^l$ is not in $S$. This implies the only powers of $p$ that are in $S$ are less than $p^l$. But this implies there are finitely many values for $a$ as well as $k$, so $S$ is finite, a contradiction $\blacksquare$. Claim: There exists no prime $q>p$ so that $f(q)>0$. AFTSOC there does. We note that $p^{q-1}$ is good and also $1\pmod q$. Thus, for some positive integer $c$, $f(1)=f(cq)=0\implies f(q)=0$, a contradiction $\blacksquare$. So the solution is (with $p$ being the only prime so that $f(p)>0$) $\boxed{f(x)=f(p)\cdot \nu_p(x)}$. Now we will show that this works. Since $f(p)>0$, the first condition is satisfied. $$f(xy)=f(p)\cdot \nu_p(xy)=f(p)\cdot (\nu_p(x)+\nu_p(y))=f(p)\cdot \nu_p(x)+f(p)\cdot \nu_p(y)=f(x)+f(y),$$ which proves the second condition is satisfied. For the third condition, we claim that any $n=a\cdot p^k$, where $0<a< p$ works. For $x+y=ap^k<p^{k+1}$, we note $\nu_p(x)=\nu_p(y)$, because if $\nu_p(x)>\nu_p(y)$ (or similarly for $\nu_p(y)>\nu_p(x)$), then $\nu_p(x+y)=\nu_p(y)=k$, which is not possible as it implies $\nu_p(x)\ge k+1$. Since $\nu_p(x)=\nu_p(y), f(x)=f(y) \blacksquare$.

We claim that the only answer is $f(n)=c.\nu_p(n)$ for some fixed prime number $p$, which obviously works. From the second condition, we have that $f(n)=\sum_{q|n} f(q)\nu_q(n)$, where $q$ is a prime divisor of $n$. Hence, since there is an element belonging to the image of $f$ which is greater than $0$, we have that there exists a prime number $p$ satisfying $f(p)>0$. Take such $p$ to be minimal. This implies that $f(1)=f(2)=...=f(p-1)=0$, otherwise the minimality of $p$ would be contradicted. $(\star)$ Now, we will prove that $p$ is unique. Indeed, assume for the sake of the contradiction that there exists a prime number $q$ greater than $p$ such that $f(q)>0$. Pick such $q$ to be the smallest prime number greater than $p$ such that $f(q)>0$. In this way, we have that, $f(p+1)=f(p+2)=...=f(q-1)=0$, otherwise the minimality of $p,q$ would be contradicted. $(\spadesuit)$ Pick $n \in \mathbb{Z}_{>0}$ satisfying the third condition. I will prove that $p|n$. Indeed, observe that among the consecutive numbers $n-1,n-2,...,n-p+1,n-p,n-p-1,...,n-q+1$ there are $q-2 \geq p$ numbers, and for each $k \in \{n-1,n-2,...,n-q+1\}$, we have that $f(k)=0$ (from $(\star),(\spadesuit)$, with excepetion of $k=n-p$. Hence, since there is a multiple of $p$ in $\{n-1,n-2,...,n-q+1\}$, it must be $n-p$. Thus, $p|n$. $(\heartsuit)$ Pick an $n$ satifying the third condition, write $n=p^e.N$. Therefore, $f(N)=f(n-N)=f(N(p^e-1)) \implies f(p^e-1)$ for each $e \leq \nu_p(n)$. Thus, if $\nu_p(n) \geq q-1$, we may pick $e=q-1$, then $f(p^{q-1}-1)=0$, a contradiction since $q|p^{q-1}-1$. Hence, $\nu_p(n)$ is bounded for each $n$ satisfying the thid condition $\implies \frac{n}{p^{\nu_p(n)}}$ is unbounded, since the property holds for infinitely many $n$. Now, observe that if the $n$ satisfying the third condition can be written as $p^eN$, with $p \not | N$ and $N>1$, then, for any $1 \leq k <N$, $f(p^ek)=f(n-p^ek)=f(p^e(N-k)) \implies f(k)=f(N-k)$, but then $N$ satisfies the third condition, so from $(\heartsuit)$, $p|N$, a contradiction. Therefore, $N=1$, and in particular, $q \not | n$, where $n$ is an integer satisfying the third condition. Thus, $q \not | n-q$, where $n$ satisfies the thid condition. This implies that $q|n-p$, because there are $q$ numbers among $\{n-q,n-q+1,...,n-1\}$ and $q \not | n-q$ (observe that due to $(\star), (\spadesuit)$, $q \not | n-q+1,n-q+2,...,n-p-1,n-p+1,...,n-1$). Hence, $q|n-p-q \implies f(p+q)=f(n-p-q) >0 \implies$ there exists a prime number $r$ different from $p,q$ such that $f(r)>0$ and $r|p+q$. Due to $p,q$ minimality, $r>q > \frac{p+q}{2}$, a contradiction, since every positive divisor of $p+q$ is less than or equal to $\frac{p+q}{2}$. Therefore, $q$ does not exist, so $f(n)=\nu_p(n)f(p)=\nu_p(n)c$ for all $n \in \mathbb{Z}_{>0}$, as desired. $\blacksquare$

Indeed $f(1)=0.$ Let $X=\{x:f(y)=f(x-y)\}.$ It is obvious that if $x=pq$ then $p,q\in X.$ Let $p$ be the smallest prime such that $f(p)\neq 0.$ So $f(k)=0~\forall k<p.$ Note that $x=c\cdot p^k$ for all $x\in X$ and $c<p.$ It is also clear that $p^k\in X.$ If there is a prime $q>p$ such that $f(q)\neq 0$, then $q\mid p^{q-1}-1$ so $f(q)\leq f(p^{q-1}-1)=0.$ So $f(q)=0,$ absurd. So the solution is $f(x)=\nu_p (x)\cdot f(p).$ It works.

The functions satisfying the problem are $f(n) = c \nu_p(n)$ for some prime $p$, natural number $c$, and taking the set of condition (iii) as powers of $p$, which can easily be seen to work. Call the set of condition (iii) as $S$. Let $p$ be the smallest prime such that $f(p) > 0$ (exists by condition (i)), then $f$ is $0$ on anything below this. First, note that every element $n$ of $S$ must be divisible by $p$, or else if say $n = kp + r$, then $f(r) = f(kp) = f(k) + f(p) > 0$, a contradiction since $r < p$. So let $n = p^k m$ with $m$ coprime to $p$ and say $m = lp + r$. If $m > p$, then we have $(k+1)f(p) +f(l)= f(l.p^{k+1}) = f(p^k(m-lp)) = f(r) + f(p^k) = kf(p)$, impossible. So we have that every element in $S$ is of the form $p^k.r$ for $r < p$. Now the key observation, note that if $kn \in S$, then $f(a) + f(k) = f(ak) = f(kn - ak) = f(n-a) + f(k) \implies f(a) = f(n-a)$ and so $n \in S$ too. So since $S$ is infinite and contains infinitely many numbers of the form $p^k.r$, $k$ must be unbounded and hence every power of $p$ must be in $S$. So if there was another prime $q$ with $f(q) > 0$, let $p^{z-1} < q < p^z$, then $f(rq) = f(p^z - rq)$ where $1 \le r < p$ is chosen so that $p^z - rq$ is smaller than $q$ and hence $f(r) + f(q) = f(p^z - rg) = 0$, a contradiction since $f(q) > 0$. So there is exactly one prime with $f(p) > 0$ which gives the solution set claimed, so we're done. $\blacksquare$

The only functions that work are $f(x)=c\cdot \nu_p(x)$ for any fixed prime $p$ and constant $c>0$. For such $f$, any power of $p$ works as $n$ in third condition. $(ii): f(x) =\sum_{\text{primes } p} f(p)\cdot \nu_p(x)$. We use $n,k$ for the assertions in $(iii)$. Let $p$ be the smallest prime such that $f(p)>0$. We have $0=f(1)=f(2)=\dots=f(p-1)$. Claim 1 : If $p^{\alpha}\le n < p^{\alpha +1}$, then $p^{\alpha}\mid n$. Proof : $k=1,2,\dots,p-1 : f(n-1)=f(n-2)=\dots=f(n-(p-1))=0$. Hence $p$ doesn't divide any of these $p-1$ numbers. Hence $p \mid n$. Similarly, $k=p\cdot 1, p\cdot 2, \dots, p \cdot (p-1) : f\left(\frac{n}{p}-1\right)=f\left(\frac{n}{p}-2\right)=\dots=f\left(\frac{n}{p}-(p-1)\right)=0$. Hence $p$ doesn't divide any of these $p-1$ numbers. Hence $p \mid \frac{n}{p} \implies p^2 \mid n$. Similarly, $k=p^2\cdot 1, p^2\cdot 2, \dots, p^2 \cdot (p-1) : f\left(\frac{n}{p^2}-1\right)=f\left(\frac{n}{p^2}-2\right)=\dots=f\left(\frac{n}{p^2}-(p-1)\right)=0$. Hence $p$ doesn't divide any of these $p-1$ numbers. Hence $p \mid \frac{n}{p^2} \implies p^3 \mid n$. Doing this so on upto, $k=p^{\alpha-1}\cdot 1, p^{\alpha-1}\cdot 2, \dots, p^{\alpha-1} \cdot (p-1)$ : $p \mid \frac{n}{p^{\alpha-1}} \implies p^{\alpha} \mid n$. This proves claim 1. $\square$ Claim 2 : For any prime $q \neq p$, $f(q)=0$. Proof : Choose $n$ such that $n \ge p^{q-1}$. We have by claim 1. $p^{q-1} \mid n$. $k=\frac{n}{p^{q-1}} : f\left(\frac{n}{p^{q-1}}\right)=f\left(\frac{n}{p^{q-1}}\cdot (p^{q-1}-1) \right) \implies f(p^{q-1}-1)=0$. As $\nu_q(p^{q-1}-1) \ge 1$, but $f(p^{q-1}-1)=0$, we must have $f(q)=0$. This proves claim 2. $\square$ From claim 2, we get $f(x)=f(p)\cdot \nu_p(x)$ and we get the set claimed at the start, and we are done!

I claim that the answer is when $f(x)=C\nu_p(x)$ for any positive integer $C$, which clearly works. By considering the prime factorization of $x$, we can write $$f(x)=\sum_{p\text{ prime}}f(p)\nu_p(x).$$ By considering $\nu_p\Big(\binom nk\Big)$, we can get that $$\sum_{k=1}^{x}\nu_p(k)\le \sum_{k=n-x}^{n-1}\nu_p(k).$$ But the conditions imply that these must be equal for any $k$. Letting $$a=p^{\left\lfloor\log_p(n)\right\rfloor},$$ we can see that both sides must reach a multiple of $a$ simultaneously for equality, which is when $a\mid n$. Now assume FTSOC that there exist distinct primes $p$ and $q$ such that $f(p),f(q)\ne 0$. Assume WLOG that $p<q$, then we see that $$p^{\left\lfloor\log_p(n)\right\rfloor}q^{\left\lfloor\log_q(n)\right\rfloor}\mid n.$$ However, this is clearly impossible as $$n\ge p^{\left\lfloor\log_p(n)\right\rfloor}q^{\left\lfloor\log_q(n)\right\rfloor}\ge p^{\left\lfloor\log_p(n)\right\rfloor}q > p^{\left\lfloor\log_p(n)\right\rfloor+1}\ge n\rightarrow n>n.$$ Thus, there is at most one prime $p$ such that $f(p)\ne 0$, which gives us the functions we already named above. QED.

Let $p$ be the smallest prime such that $f(p)>0$ (so $f(x)=0$ if $x<p$). Let $M$ be the set of $n$ such that the second condition is satisfied. If there is any $m\in M$ such that $m=pq+r$, where $q$ is nonnegative and $r<p$ is positive, then we get $f(r)=f(pq)=f(p)+f(q)>0$, but this implies that there is a prime divisor $d$ of $r$ that is less than $p$ such that $f(d)>0$, contradiction. Hence $p$ divides all elements of $M$ that are greater than $p$. We also note that if $ab\in M$, then $a\in M$. This is true due to $$f(b)+f(k)=f(bk)=f(ab-bk)=f(b)+f(a-k),$$ as long as $k<a$. Furthermore, there cannot be anything in $M$ of the form $cp^e$ where $c>p$ and $e\in \mathbb{Z}_{\geq 0}$: Otherwise, take $q\in \mathbb{Z}$ such that $qp<c<(q+1)p$, so that $$f(q)+(e+1)f(p)=f(qp^{e+1})=f(cp^e-(c-qp)p^e)=f(c-qp)+ef(p).$$ Hence $(e+1)f(p)=ef(p)$, which is impossible. So now we know that $M$ consists of an infinite number of integers of the form $cp^e$, where $e\in \mathbb{Z}_{\geq 0}$ and $1\leq c<p$. FTSOC assume there is any prime $q\neq p$ such that $f(q)>0$. Since $c$ is bounded, we know that $e$ is unbounded, so there must be something in $M$ with $\nu_p$ being at least $q$; then $p^{q-1}\in M$. Since $q\mid p^{q-1}-1$, we have $$0<f\left(\frac{p^{q-1}-1}{q}\right)+f(q)=f(p^{q-1}-1)=f(1)=0,$$ contradiction. Hence $f(q)=0$ for all primes $q\neq p$. This implies that $f(x)=0$ for all $x$ such that $p\nmid x$. Therefore $f(x)=f(p)\cdot \nu_p(x)$, where $f(p)$ is any positive integer. We can check that this works.

First, note that $a\mid b$ implies $f(a)\le f(b)$. Second, note that we have $$f(x)=\sum_{\text{p prime}}f(p)v_p(x)$$ This means $f(1)=0$ and that in order for $f$ not to be $0$ everywhere, we must have $f(p)>0$ for some prime $p$. Consider the smallest such $p$. For any such $n\ge p$ as mentioned in the problem, observe that $f(n-p+1),f(n-p+2),\dots,f(n-1)$ must all be $0$, hence $n-p+1,n-p+2,\dots,n-1$ are all not divisible by $p$. This means $n$ must be divisible by $p$. Now, note that any divisor of such an $n$ as mentioned in the problem is itself such an $n$; this is seen by noting that if $d$ is a divisor of such an $n$, then $$f(d-k)=f\left(\frac{n}d(d-k)\right)-f\left(\frac{n}d\right)=f\left(n-\frac{n}dk\right)-f\left(\frac{n}d\right)=f\left(\frac{n}dk\right)-f\left(\frac{n}d\right)=f(k)$$ Now, observe that we have arbitrarily large such $n$; we then always have $\frac{n}{p^{v_p(n)}}\le p<p$; hence we have arbitrarily large $p^{v_p(n)}$ which themselves are such $n$ mentioned in the problem. Since arbitrarily large powers of $p$ are such $n$, this implies that all powers of $p$ are such $n$ because any power of $p$ is a divisor of a sufficiently large power of $p$. Now, observe that for any prime $q\ne p$, we have $q\mid p^{\operatorname{ord}_q(p)}-1$ so $f(q)\le f(p^{\operatorname{ord}_q(p)}-1)=f(1)=0$. This implies then that $f(x)=f(p)v_p(x))$ for all $x$; thus the only solutions are positive integer multiples of $v_p$ for all primes $p$ (and all of these work by taking $n$ to be powers of $p$).

One of the best ISL number theory problems I have done. The only functions that work are $f(x)=C \cdot \nu_p(x)$ for some prime $p$ and positive integer $C$. Clearly these are valid solutions. Take prime $p$ with $f(p)>0$, which exists by condition (i), and take $n$ satisfying condition (iii). Then we have $$f\left( \binom {n-1}{k} \right)= \sum_{i=1}^{n-1} f(i) - \sum_{i=1}^{k}f(i) - \sum_{i=1}^{n-k-1}f(i) = \sum_{i=n-k}^{n-1} f(i) - \sum_{i=1}^{k}f(i),$$ and this simplifies to $0$ as $n$ satisfies condition (iii). If $p \mid \tbinom {n-1}{k}$, then $f(\tbinom {n-1}{k})>0$, which is false. Thus, for sufficiently large $n$ satisfying (iii), $p \nmid \tbinom{n-1}{k}$ for all $0 \le k \le n-1$, from which Lucas's theorem implies $n=p^{n_1} \cdot n_2$, where $n_2 < p$. Suppose that $q$ is any prime with $f(q)>0$. By taking sufficiently large $n$, we can write both $n=p^{n_1} \cdot n_2$ where $n_2 < p$ and $n=q^{m_1} \cdot m_2$ where $m_2<q$. If $p \neq q$, then there are only finitely many $n$ that can be written in both forms, so $p=q$. Thus, $f(q)=0$ for all $q$ distinct from $p$. Using conditions (i) and (ii), we write $$f(x)=\sum_{q \text{ prime}}f(q) \cdot \nu_q(x)=f(p) \cdot \nu_p(x) + \sum_{ q \neq p, \ q \text{ prime}} 0 = f(p) \cdot \nu_p(x).$$ The solution set for $f$ follows.

woah this is cute

We claim that $f(x) = cv_{p}(x)$ for some constant $c$ and some prime $p$. Let $p$ be the smallest integer such that $f(p)> 0$. Clearly, $p$ is a prime, because otherwise, we could write it in its prime factorization and must have one of the terms be $> 0$, which is a contradiction by minimality. Let $n$ be a sufficiently large integer that satisfies the second condition. We claim that we must have $p \mid n$. For the sake of contradiction, let $n \equiv k \neq 0 \pmod{p}$. Thus, $$f(k) = f(n-k) = f(p)+f(\cdots) > 0$$ but $k< p$, so $f(k) = 0$, contradiction. We claim that there doesn't exist any other prime $q$ such that $f(q) > 0$. For the sake of contradiction, let $q$ be the second smallest prime such that $f(q) > 0$. We claim that $q \mid n$ as well. Let $l = \lfloor\log_{p}(q)\rfloor$. Note that $p^{l} \mid n$ by the same logic that $p\mid n$ except if $p\mid k$, we'll have a greater exponent of $p$, contradiction. Thus, for the sake of contradiction let $n \equiv k \pmod{q}$. If $p \nmid k$, then $f(k) = 0 = f(n-k) = f(q)+f(\cdots) > 0$. If $p \mid k$, then we get $f(k) = f(p^{v_{p}(k)}) = f(p^{v_{p}(k)})+f(q) + f(\cdots)$, because $v_{p}(k) \leq l$. Thus, we must have $q \mid n$. However, if $n = aq\cdot p^{b}$, such that $v_{p}(a) = 0$. Note that $aq = cp+k$ for some $k < p$. Thus, we can just take $f(cp^{b+1}) = f(kp^{b})$, which is a contradiction. From here, it is clear that $f(x) = cv_{p}(x)$ for some constant $c$ and some prime $p$.

MatBoy-123 wrote: Aryan-23 wrote: Hence for all large enough good $n$, we have that $p \not \vert \tbinom {n-1}{k}$. By Lucas's theorem we have that $n=a\cdot p^b$ for some $a<p$. I am quite confused, how did u apply Lucas, can someone plz explain.. Claim: For a prime number $p$ and a positive integer $n$ if $p\nmid \tbinom{n-1}{k}, \forall 0\leq k\leq n-1$ then $n=a\cdot p^b$ for some $1\leq a<p$ and $b$ non negative. Proof: Let $n-1=\sum_{i=0}^{s} n_i p^{i}$ for some non negative integer $s$ and $0\leq n_i<p$ for all $0\leq i\leq s$. The case $s=0$ is trivial, so we can assume $s\geq 1$. Take $0\leq j\leq s-1$ and assume BWOC that $n_j<p-1$ so that the $j$th digit base $p$ of $(n_j+1)p^j$ is still just $n_j+1$. Note that $\tbinom{a}{b}=0$ if $b>a$. We can now apply Luca's theorem in the following way: $$\binom{n-1}{(n_j+1)p^j}\equiv \prod_{i=0}^{s} \binom{n_i}{\delta_{ij} (n_j+1)}\equiv \binom{n_j}{n_j+1}\equiv 0 \pmod p$$ Here $\delta_{ij}$ is the Kronecker delta symbol (=1 if $i=j$ and =0 otherwise). Now since $(n_j+1)p^j<n$ we know that $p$ can't divide $\tbinom{n-1}{(n_j+1)p^j}$ which is a contradiction. So $n_j=p-1, \forall 0\leq j\leq s-1$. Now it easily follows: $$n=1+n_s p^s+\sum_{i=0}^{s-1} (p-1) p^{i}=(n_s+1)p^s$$ Which is of the form $a\cdot p^b$ for $1\leq a<p$ and we are done $\blacksquare$. I hope this helped .

Let's forget for a moment that $\mathbb{N}_0$ has a nice total order (which is used in the official solution). We will only use the fact that $\mathbb{N}_0$ is an integral monoid (commutative, and addition can be cancelled out, i.e., $a + c = b + c$ implies $a = b$); torsion-free (for any $k \in \mathbb{N}_0$, if $n \cdot k = 0$ for some positive integer $n$, then $k = 0$). Quote: Let $\mathbb{N}$ denote the set of positive integers. Let $M$ be a torsion-free integral monoid. Determine all functions $f : \mathbb{N} \to M$ such that $f$ is additive: $f(xy) = f(x) + f(y)$ for every $x, y \in \mathbb{N}$, there are infinitely many positive integers $n$ such that $f(k) = f(n - k)$ for all $k \in \mathbb{N}$ such that $k < n$. Answer. $n \mapsto \nu_p(n) \cdot c$ for some prime $p$ and $c \in M$. More generally, if $M$ is not torsion-free, then any function of the form $p^k x \mapsto kc + \chi(x)$ for some monoid homomorphism $\chi : (\mathbb{Z}/p\mathbb{Z})^{\times} \to M$ works. However, we may have pathological solutions as well, for example, using Legendre symbols when $M = \mathbb{Z}/2\mathbb{Z}$. See the solution below for more detail. We will not assume that $M$ is torsion-free, unless necessary. We say that a positive integer $n$ is $f$-nice if $f(k) = f(n - k)$ for all $k \in \mathbb{N}$ such that $k < n$. For any positive integers $c$ and $d$, if $cd$ is $f$-nice, then $f(ck) = f(cd - ck) \implies f(c) + f(k) = f(c) + f(d - k) \implies f(k) = f(d - k)$ for any $k < n$, so $d$ is $f$-nice as well. That is, the set of $f$-nice positive integers is divisor-closed. Since this set is assumed to be infinite, either (1). there exists a prime $p$ such that $p^k$ is $f$-nice for any $k \geq 0$; (2). there exists infinitely many $f$-nice primes. The following lemma is crucial in both cases. Lemma. Let $p$ be an $f$-nice prime. Then $f(km \bmod{p}) = f(k) + f(m)$ for any positive integers $k, m < p$, where $km \bmod{p}$ denote the remainder of $km$ under division by $p$.

The lemma tells us that $f$, when restricted over $\{1, 2, \ldots, p - 1\}$, is essentially a monoid homomorphism $(\mathbb{Z}/p\mathbb{Z})^{\times} \to M$. In particular, when $M$ is torsion-free, $f$ would necessarily restrict to the zero map on $(\mathbb{Z}/p\mathbb{Z})^{\times}$. Case 1. There exists a prime $p$ such that $p^k$ is $f$-nice for any $k \geq 0$. We claim that $f(x) = f(x \bmod{p})$ for any positive integer $x$ coprime with $p$. The claim is the bulk of the solution in Case 1.

Now let $\chi : (\mathbb{Z}/p\mathbb{Z})^{\times} \to M$ be the restriction of $f$ to $(\mathbb{Z}/p\mathbb{Z})^{\times}$. Recall by the above lemma that $\chi$ is a monoid homomorphism. The above claim yields that $f(x) = \chi(x \bmod{p}) = \chi(x)$ for any $x \in \mathbb{N}$ coprime with $p$. As a result, $f(p^k x) = k f(p) + \chi(x)$ for any $k \geq 0$ and $x \in \mathbb{N}$ coprime with $p$. Note that if $M$ is torsion-free, then $\chi$ is necessarily zero, since $(p - 1) \chi(x) = \chi(x^{p - 1}) = \chi(1) = 0$ for any $x \in (\mathbb{Z}/p\mathbb{Z})^{\times}$. In this case, we have $f(p^k x) = k f(p) = \nu_p(p^k x) f(p)$. That is, $f(n) = \nu_p(n) f(p)$ for any $n \in \mathbb{N}$. Case 2. There exists infinitely many $f$-nice primes. Assuming that $M$ is torsion-free, this case has a short solution as follows. By the above lemma and the same argument as in the final paragraph in Case 1, for any $f$-nice prime $p$, we have $f(n) = 0$ for any $n < p$. Now for any $n \in \mathbb{N}$, there must be an $f$-nice prime greater than $n$ since there are infinitely many $f$-nice primes. Thus we get $f(n) = 0$ for any $n \in \mathbb{N}$. However, if $M$ is not torsion-free, then there exists a prime $q$ such that there exists an injective homomorphism $\mathbb{Z}/q\mathbb{Z} \hookrightarrow M$. If we can construct a weird function $f : \mathbb{N} \to \mathbb{Z}/q\mathbb{Z}$ with infinitely many $f$-nice primes, then the same holds for $\mathbb{N} \to M$ just by composing with that homomorphism. Such construction exists for $q = 2$; we construct it below.

In the case where $q$ is odd, it suffices to find a sequence of primes $p_1 < p_2 < \ldots$ and compatible non-zero homomorphisms $f_k : (\mathbb{Z}/p_k \mathbb{Z})^{\times} \to \mathbb{Z}/q\mathbb{Z}$ and leave it there. By compatible, we mean that $f_k(n) = f_m(n)$ whenever $n < \min\{p_k, p_m\}$. Then we can set $f(n) = f_n(n)$, and check that since $q$ is odd, the equality $f(n) = f(p_k - n)$ always holds whenever $n < p_k$. Unfortunately, finding such sequence looks like an open problem on itself... Edit on April 14: It turns out that Chebotarev density theorem alone is enough to prove that such sequence exists, and it works without much extra work. View $\mathbb{Z}/q\mathbb{Z}$ as being isomorphic to the subgroup $\langle \zeta_q \rangle$ of $\mathbb{Q}(\zeta_q)^{\times}$. The homomorphisms $f_k$ are chosen to be the $q^{\text{th}}$ power symbol on $\mathbb{Q}(\zeta_q)$, and the primes $p_1, p_2, \ldots$ are chosen inductively using Chebotarev density theorem on a suitable abelian extension of $\mathbb{Q}(\zeta_q)$ at each step.

Amazing problem, but had to use ARCH hint to solve. $\rule{25cm}{0.5pt}$ We claim $\boxed{f(x) = \nu_p(x) \cdot c}$ for some prime $p$ and some constant $c$. Let $S$ denote the set of all integers $n$ satisfying for $f(n-k) = f(k)$ for all $k < n$. $\color{blue} \textbf{Claim}$: For any $n \in S$, any divisor $d$ of $n$ must be in $S$. Proof . Assume some $n \in S$. Then take some divisor of $n$, say $d$. Let $k$ be such that $dk = n$. Then note for any $\ell < d$ that we have, $$\begin{align*} f(\ell k) &= f(n - \ell k)\\ f(\ell ) + f(k) &= f(k) + f(d - \ell)\\ f(\ell) &= f(d- \ell ) \end{align*}$$ which is sufficient. $\blacksquare$ Now assuming that $f$ is not the zero function, take the smallest $p$ such that $f(p) > 0$. Clearly $p$ is prime from our previous claim. Also we find that $p \in S$, as for any $\ell < p$ we have, $$\begin{align*} f(\ell) = f(p-\ell) = 0. \end{align*}$$ $\color{red} \textbf{Claim}$: For any $n \in S$, with $n > p$, we must have $p \mid n$. Proof. Assume otherwise and let $n = pm + r$. Then we find, $$\begin{align*} f(n - r) &= f(r)\\ f(pm) &= f(r)\\ f(p) + f(m) &= f(r) \end{align*}$$ However this implies that $f(r) \geq f(p) > 0$, with $r < p$, a contradiction. $\blacksquare$ In fact we can slightly strengthen our claim. $\color{blue} \textbf{Claim}$: Any $n \in S$ must be of the form $kp^e$ for some $k \in (1, 2, \dots, p-1)$. Proof. Assume otherwise. Then there exists some element $n \in S$ of the form $tp^e$, with $t > p - 1$. Note by our first claim we find that $t \in S$. However then from our second claim as if $t > p - 1$, we find $p \mid t$, a contradiction to our assumption. $\blacksquare$ Finally from the infinite size of $S$, we must have that for any $e$ we have $p^e \in S$. $\color{red} \textbf{Claim}$: For all other primes $q \neq p$, we have $f(q) = 0$. Proof. Assume that there is some prime $q > p$ such that $f(q) > 0$. Then noting that $q \mid p^{q-1}-1$ we find, $$\begin{align*} f(p^{q-1}-1) = f(q) + f(k) \end{align*}$$ where $k$ is such that $qk = p^{q-1}-1$. Note that from our previous claim, namely that all powers of $p$ lie in $S$, we have $f(p^{q-1}-1) = f(1) = 0$. Then we must have $f(q) = 0$, a contradiction. $\blacksquare$ Now we are almost finished. Note that from the additivity of $f$, for any $n = p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ we have, $$\begin{align*} f(n) = \sum_{i=1}^{k} e_i \cdot f(p_i) \end{align*}$$ Now from the condition that for any prime $q \neq p$ we have $f(q) = 0$, we find that for any $n$ we must have, $$\begin{align*} f(n) = \nu_p(n) \cdot f(p) \end{align*}$$ Letting $f(p)$ be some integer constant greater than or equal to $0$, we can conclude that $f$ is indeed the claimed function.

Our answer is $\boxed{f(x) = c \cdot v_p(x)}$ for a nonnegative constant $c$ and a prime $p$, which can be tested to work. Note that $f(x)=0$ is obviously valid, so from here we assume $f$ is not the zero function. Define $N$ as the infinite set of integers $n$ satisfying the second condition. Claim 1: If $d \mid n$ and $n \in N$, then $d \in N$. Choose an arbitrary positive integer $k < d$. Since $\frac nd \in \mathbb{Z}$, we get $$f(k) = f(d-k) \iff f\left(\frac{nk}{d}\right) = f\left(\frac nd (d-k)\right) = f\left(n - \frac{nk}{d}\right),$$ which is true by definition of $n$. ${\color{blue} \Box}$ Claim 2: If $p$ is the smallest positive integer with $f(p)>0$, $p$ must be prime and $p \in N$. The first part is clear from our first condition and the second part is clear from our second condition along with the minimality of $p$. ${\color{blue} \Box}$ Claim 3: Each element of $N$ greater than $p$ is of the form $p^eq$ for $1 \leq q < p$, and every power of $p$ is in $N$. Assume FTSOC there exists an element $ap+b$, where $1 \leq b \leq p-1$. This tells us $$f(b) = f(ap) = f(a)+f(p) > 0,$$ contradicting the minimality of $p$. Now assume FTSOC there exists an element $p^er$, where $p \nmid r$ and $r > p$. Claim 1 tells us $r \in N$, but our previous results then says $p \mid r$, contradiction. Finally, the infinite size of $N$ along with Claim 1 grants us the final portion of our claim. ${\color{blue} \Box}$ Claim 4: For all primes $q \ne p$, we have $f(q)=0$. By construction all $q<p$ already satisfy this condition. For $q>p$, Claim 3 tells us $$f \left(\frac{p^{\operatorname{ord}_q(p)}-1}{q}\right) + f(q) = f \left(p^{\operatorname{ord}_q(p)}-1\right) = f(1) = 0. \quad {\color{blue} \Box}$$ The first condition finally gives us the desired expression of $f(x)$ through its prime factorization: $$f(x) = \sum_{k \text{ prime}} f(k) \cdot v_k(x) = f(p) \cdot v_p(x). \quad \blacksquare$$

Denote $S=\{n\mid f(k)=f(n-k)\forall 1<k<n\}$. Let $n\in S$ then if $d\mid n$ then let $a+b=d$. We have $\tfrac{an}{d}+\tfrac{bn}{d}=n$ so $$f(a)+f\left(\frac{n}{d}\right)=f\left(\frac{an}{d}\right)=f(b)+f\left(\frac{n}{d}\right)$$ which implies that $d\in S$. Let $p$ be the smallest number such that $f(p)\neq 0$. If $p=ab$ where $a,b$ are positive integers less than $p$ then $f(p)=f(a)+f(b)=0$ which is a contradiction. Thus, $p$ is prime. Suppose $n\in S$ and $n\ge p$ then $f(n-1)=f(n-2)=\dots=f(n-(p-1))=0$. Let $n=kp+m$ where $m\in \{1,2,\dots,p-1\}$ then $$0=f(n-m)=f(kp)=f(k)+f(p)=f(p)$$ which is another contradiction. Thus, $p\mid n$. Now let $n=bp^a$ where $p\nmid b$ then since $b\mid n$, $b\in S$ which means $b<p$. If $p^k\not\in S$ for some $k$ then all multiples of $k$ are not in $S$. Thus, $S\setminus \{1,2,\dots,p-1\} \subseteq \{bp^a\mid a<k, b<p\}$, so $S$ is not infinite, contradiction. Therefore, $p^k\in S\forall k$. Supposed $f(q)\neq 0$ for some $q\neq p$ then note that $$0=f(p^{q-1}-1)=f(q)+f\left(\frac{p^{q-1}-1}{q}\right)>0$$ which is a contradiction. Thus, $f(q)=0$ for all $q\neq p$. After prime factorizing $x$ we can easily see that $f(x)=c\nu_p(x)$ for some $c$, $p$. This function clearly satisfies all three properties.

I claim the answer is only $f(x) = k\nu_p(x)$, which obviously works for all positive integer $k$ and primes $p$. Call all integers satisfying the third property good. If an integer $n$ is good, so is any divisor of it $d$: observe $f(x) = f(y)$ is true iff $f(x) + f(\frac nd) = f(y) + f(\frac nd)$ which is true iff $f(\frac{xn}{d}) = f(\frac{yn}{d})$. Clearly, for any $x,y$ chosen such that $x + y =d$, the last statement holds, thus so does the first one and $d$ is good. In addition, if $n$ is a root, so is every divisor of it $d$, this is trivial by assuming otherwise and then forcing $f(n) > 0$. Observe $f(x) = f(x) + f(1)$, so $f(1) = 0$. Now consider the first value of $x$ with $f(x) > 0$. If $x$ is not prime, we can write it as $f(x) = f(a) + f(b)$, with $ab = n$, $a$,$b$ $< n$. Then since $f(a) = f(b) = 0$, we also have $f(x) = 0$, contradiction. Thus there exists some $p$ with $p$ prime that is the smallest solution to $f(x) = 0$. Clearly $p$ is good, since $f(k) = f(p - k) = 0$. Now we prove there are no good numbers above $p$ not dividing $p$. Assume there exists another good prime, called $q$. Then we have $f(x) = f(q - x)$, so for $1 \le x \le p - 1$ this shows that $f(q - 1) \cdots f(q - p + 1) = 0$. Now since $q, \cdots q - p + 1$ is a complete residue set mod $p$, we must have one of those numbers is divisible by $p$, and its not $q$ by definition of $q$. Let that number be $a$, we have $f(a) = 0$, but also $f(a) = f(p) + f(\frac pa) \ge f(p) > 0$, contradiction. Now any good number cannot have a divisor greater than $p$ that is not divisible by $p$, this means that they all must be of the form $cp^x$ for $1 \le c \le p - 1$, so since there are a finite number of elements of the form $cp^x$ for $x \ge N$, we can conclude the set of good numbers has unbounded $\nu_p$. Now there always exists $x > N$ for all $N$ such that $p^x$ is good. Then since $p^N \mid p^x$, we have $p^N$ is good for all $N$. To finish, we have $0 = f(1) = f(p^k - 1)$. Now all divisors of $p^k - 1$ also must be a root of $f$. Indeed, $p^k \equiv 1 \mod m$ always has a solution, this is well known as long as $\gcd(p , m) = 1$, which is true, so all numbers relatively prime to $p$ divide some expression of the form $p^k - 1$, meaning all numbers relatively prime to $p$ are roots of $f$. Let $f(p) = k$, then we can easily show $f(p^x) = kx$ by using $f(p^x) = f(p^{x- 1}) + f(p)$ and induction, then if $\nu_p(x) = c$, we can write $f(x) = f(p^c) + f(\frac{x}{p^c}) = kc + f(\frac{x}{p^c})$, since $\frac{x}{p^c}$ is relatively prime to $p$ by definition of $c$, we have $f(x) = kc = f(p^c) = k\nu_p(p^c) = k\nu_p(x)$, so we have $f(x) = k\nu_p(x)$ Remark: putting actual effort into writeups is so boring. why would anyone do this.

Solved with a hint motivating the first lemma ($n$ good implies $d \mid n$ good). After that it still took me a while, but in hindsight I realized I was expecting something a little more $\nu_p$-flavored (the only use of $\nu_p$ in the solution is to actually show that the functions work). Solution. The only solutions are $f(n) = c\nu_p(n)$ for some prime $p$ and positive integer $c$. Claim: All such functions work. Proof. The zero function trivially satisfies the equation. For $f(n) = c\nu_p(n)$, take $n = p^\ell$ for any positive integer $\ell$; we have $$f(n - k) = c\nu_p(p^\ell - k) = c\nu_p(-k) = f(k)$$ since $\nu_p(k) < \ell$ for each $k < n$, as desired. $\square$ Let $p$ be the smallest positive integer for which $f(p)$ is nonzero. Clearly $p$ is prime, since otherwise $p = ab$ for $a, b < p$ and then one of $f(a)$ and $f(b)$ is nonzero. Our goal is to show that this is the only such prime, from which it easily follows that $f(n) = f(p)\nu_p(n)$ for all $n$. Suppose to the contradiction that there exists a prime $q > p$ for which $f(q) > 0$. Call a positive integer $n$ good if it satisfies the third condition. We begin with the following: Claim: If $n$ is good, any divisor $d \mid n$ is good. Proof. Write $n = md$. Take an integer $k \in [1, d - 1]$; it suffices to show that $f(k) = f(d - k)$. Indeed, we have $$f(m) + f(k) = f(mk) = f(md - mk) = f(m) + f(d - k),$$ and subtracting $f(m)$ yields the desired. $\square$ Claim: All good positive integers are of the form $ap^k$, where $a < p$ and $k$ is a nonnegative integer. Proof. Let $n > p$ be a good integer, and write $n = mp + r$ for some $m \geq 1$ and $r < p$. If $r \neq 0$, we have $f(r) = f(mp) = f(m) + f(p) > 0$, a contradiction, so $r = 0$ and $n = mp$. By the previous claim, $m$ is good and so we can repeat this until $m < p$, completing the proof. $\square$ Claim: $p^k$ is good for every positive integer $k$. Proof. There are infinitely many good integers, so we can find arbitrarily large $k$ for which $ap^k$ is good for some $a < p$. Since any divisor of $ap^k$ is good, we deduce the desired result. $\square$ Now we can finish as follows: since $p^{q - 1}$ is good, we have $$0 = f(1) = f(p^{q - 1} - 1) = f(q) + f\left(\frac{p^{q - 1} - 1}{q}\right) > 0,$$ by Fermat, a contradiction. Thus $p$ is the only prime for which $f(p) > 0$, which completes the proof. $\square$