It's trivial to choose values of $f(p), f(p-1)$ and $f(pq)$ satisfying the conditions. Then choose $f(20)=1000000000000000$ and $f(n)=42$ else. This is clearly a counter-example?!?

Tintarn wrote: It's trivial to choose values of $f(p), f(p-1)$ and $f(pq)$ satisfying the conditions. Then choose $f(20)=1000000000000000$ and $f(n)=42$ else. This is clearly a counter-example?!? I may have not understood your argument, but, I think that example doesn't satisfy $ \text{(iii)} , $ because, otherwise, it would imply $ 1000000000000000=f(20)=f(2\cdot 2\cdot 5)=2f(2)+f(5)=126. $

CatalinBordea wrote: I may have not understood your argument, but, I think that example doesn't satisfy $ \text{(iii)} , $ because, otherwise, it would imply $ 1000000000000000=f(20)=f(2\cdot 2\cdot 5)=2f(2)+f(5)=126. $ Uh? How does (iii) imply that $f(20)=2f(2)+f(5)$. To which prime numbers $p$ and $q$ have you applied (iii)?

Tintarn wrote: CatalinBordea wrote: I may have not understood your argument, but, I think that example doesn't satisfy $ \text{(iii)} , $ because, otherwise, it would imply $ 1000000000000000=f(20)=f(2\cdot 2\cdot 5)=2f(2)+f(5)=126. $ Uh? How does (iii) imply that $f(20)=2f(2)+f(5)$. To which prime numbers $p$ and $q$ have you applied (iii)? Ah, of course. I fix it now.

Note that we're being asked to prove that $3\log_{3}{n} \leq f(n) \leq 3\log_{2}{n}$. First, we'll show that this holds for any prime number, to do so we'll use induction on the $n$'th prime number. It is trivial to see that this holds for primes $p\leq 7$, so we'll prove it for $p\geq 11$. So, assume that for $p_1,p_2,\dots ,p_{n-1}$ the result holds. Lemma. The result holds for all combinations of $p_1,p_2, \dots, p_{n-1}$. Proof. Let $n=\prod_{i=1}^{n-1} p_{i}^{k_i}$, using the third condition we have that \begin{align*} f(n) & =\sum_{i=1}^{n-1} k_i f(p_i)\leq 3\sum_{i=1}^{n-1} k_i\log_{2}{p_i}=3\log_{2}{n} \;\; \text{and} \\ f(n) & =\sum_{i=1}^{n-1} k_i f(p_i)\geq 3\sum_{i=1}^{n-1} k_i\log_{3}{p_i}=3\log_{3}{n}. \end{align*}which proves the lemma. $\blacksquare$ Now, we'll prove that the inequalities hold for $p_n$. Note that by the second condition, and since the result holds for $f(p_n-1)$ because all divisors of $p_n-1$ are less than $p_n$ we have that $$f(p_n)=1+f(p_n-1)\geq 1+3\log_{3}(p_n-1) \geq3 \log_{3}(p_n)$$beacuse $\left(\frac{p_n}{p_n-1}\right)^3\leq 3$ holds for $p_n \geq 11$. Also, since that all prime divisors of $p_n+1$ are less than $p_n$ the result holds for $f(p_n+1)$, so using the second condition we get $$f(p_n)=f(p_n+1)-1\leq 3\log_{2}(p_n+1)-1 \leq 3\log_{2}(p_n)$$because $\left(\frac{p_n+1}{p_n}\right)^3 \leq 2$ for $p_n \geq 11$, which shows that the result holds for $p_n$ too, hence by induction hypothesis the problem statement holds for all prime numbers. Let $n=\prod_{i=1}^{\ell} p_{i}^{k_i}$, we have that \begin{align*} f(n) & =\sum_{i=1}^{\ell} k_i f(p_i)\leq 3\sum_{i=1}^{\ell} k_i\log_{2}{p_i}=3\log_{2}{n} \;\; \text{and} \\ f(n) & =\sum_{i=1}^{\ell} k_i f(p_i)\geq 3\sum_{i=1}^{\ell} k_i\log_{3}{p_i}=3\log_{3}{n}. \end{align*}which proves the problem for all $n \geq 2$. $\blacksquare$

XbenX wrote: Note that we're being asked to prove that $3\log_{3}{n} \leq f(n) \leq 3\log_{2}{n}$. First, we'll show that this holds for any prime number, to do so we'll use induction on the $n$'th prime number. It is trivial to see that this holds for primes $p\leq 7$, so we'll prove it for $p\geq 11$. So, assume that for $p_1,p_2,\dots ,p_{n-1}$ the result holds. Lemma. The result holds for all combinations of $p_1,p_2, \dots, p_{n-1}$. Proof. Let $n=\prod_{i=1}^{n-1} p_{i}^{k_i}$, using the third condition we have that \begin{align*} f(n) & =\sum_{i=1}^{n-1} k_i f(p_i)\leq 3\sum_{i=1}^{n-1} k_i\log_{2}{p_i}=3\log_{2}{n} \;\; \text{and} \\ f(n) & =\sum_{i=1}^{n-1} k_i f(p_i)\geq 3\sum_{i=1}^{n-1} k_i\log_{3}{p_i}=3\log_{3}{n}. \end{align*}which proves the lemma. $\blacksquare$ Now, we'll prove that the inequalities hold for $p_n$. Note that by the second condition, and since the result holds for $f(p_n-1)$ because all divisors of $p_n-1$ are less than $p_n$ we have that $$f(p_n)=1+f(p_n-1)\geq 1+3\log_{3}(p_n-1) \geq3 \log_{3}(p_n)$$beacuse $\left(\frac{p_n}{p_n-1}\right)^3\leq 3$ holds for $p_n \geq 11$. Also, since that all prime divisors of $p_n+1$ are less than $p_n$ the result holds for $f(p_n+1)$, so using the second condition we get $$f(p_n)=f(p_n+1)-1\leq 3\log_{2}(p_n+1)-1 \leq 3\log_{2}(p_n)$$because $\left(\frac{p_n+1}{p_n}\right)^3 \leq 2$ for $p_n \geq 11$, which shows that the result holds for $p_n$ too, hence by induction hypothesis the problem statement holds for all prime numbers. Let $n=\prod_{i=1}^{\ell} p_{i}^{k_i}$, we have that \begin{align*} f(n) & =\sum_{i=1}^{\ell} k_i f(p_i)\leq 3\sum_{i=1}^{\ell} k_i\log_{2}{p_i}=3\log_{2}{n} \;\; \text{and} \\ f(n) & =\sum_{i=1}^{\ell} k_i f(p_i)\geq 3\sum_{i=1}^{\ell} k_i\log_{3}{p_i}=3\log_{3}{n}. \end{align*}which proves the problem for all $n \geq 2$. $\blacksquare$ wrong