Let define a function $f: \mathbb{N} \rightarrow \mathbb{Z}$ such that : $i)$$f(p)=1$ for all prime numbers $p$. $ii)$$f(xy)=xf(y)+yf(x)$ for all positive integers $x,y$ find the smallest $n \geq 2016$ such that $f(n)=n$
Problem
Source: Netherlands TST for BxMO 2017 problem 2
Tags: function, number theory, prime numbers
Math-Ninja
01.02.2018 18:13
Why is this named beautiful problem. Titles are meant for description please.
ThE-dArK-lOrD
01.02.2018 19:57
Not hard to prove by induction on $s\in \mathbb{Z}^+$ that $$f(n)=n\sum_{i=1}^{k}{\frac{\alpha_i }{p_i}}$$where $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ is the canonical form of $n$ with $\sum_{i=1}^{k}{\alpha_i} =s$. Hence, $f(n)=n\sum_{i=1}^{k}{\frac{\alpha_i }{p_i}}$ where $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ is the canonical form of $n$ is true for all positive integer $n$. We want to find $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ that $f(n)=n\iff \sum_{i=1}^{k}{\frac{\alpha_i }{p_i}} =1$. If $k\geq 2$, we get that $\alpha_i \leq p_i$ for all $i\in \{ 1,2,...,k\}$. But we've $\sum_{i=1}^{k}{\alpha_i \times \frac{P}{p_i} }=P$ where $P=\prod_{i=1}^{k}{p_i}$. Modulo $p_1$ gives us $p_1\mid \alpha_1 \times \frac{P}{p_1}$, impossible since all $p_i$s are distinct. So, $k=1$. This gives $n=p^p$ for some prime number $p$. Easy to see that the smallest such $n$ that not smaller than $2016$ is $3125=5^5$.
soryn
02.02.2018 00:43
Very nice! I like this problem, I like this solution! Congratulations!)))))
User335559
05.02.2018 00:10
ThE-dArK-lOrD wrote: Not hard to prove by induction on $s\in \mathbb{Z}^+$ that $$f(n)=n\sum_{i=1}^{k}{\frac{\alpha_i }{p_i}}$$where $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ is the canonical form of $n$ with $\sum_{i=1}^{k}{\alpha_i} =s$. Hence, $f(n)=n\sum_{i=1}^{k}{\frac{\alpha_i }{p_i}}$ where $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ is the canonical form of $n$ is true for all positive integer $n$. We want to find $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ that $f(n)=n\iff \sum_{i=1}^{k}{\frac{\alpha_i }{p_i}} =1$. If $k\geq 2$, we get that $\alpha_i \leq p_i$ for all $i\in \{ 1,2,...,k\}$. But we've $\sum_{i=1}^{k}{\alpha_i \times \frac{P}{p_i} }=P$ where $P=\prod_{i=1}^{k}{p_i}$. Modulo $p_1$ gives us $p_1\mid \alpha_1 \times \frac{P}{p_1}$, impossible since all $p_i$s are distinct. So, $k=1$. This gives $n=p^p$ for some prime number $p$. Easy to see that the smallest such $n$ that not smaller than $2016$ is $3125=5^5$. How did you find the function? What's the motivation behind that?
liekkas
12.05.2018 15:08
It's 2015 Austria MO (maybe not posted yet)