Recently encountered the following question:
A function $f$ defined on the set of positive integers has the properties that, for any positive integer $n$, $f(f(n)) = 2n$ and $f(4n + 1) = 4n + 3$ . What are the last three digits of $f(2016)$?
I tried to find the function, $f$. But was very unsuccessful. The closest I got was $f(x) = x+2$. However, it doesn't satisfy the composite; for instance, $f(f(10))$ is $14$ and not $2n$, i.e $20$. I then tried to apply the compound function on the other function given, i.e $f(f(4n+1)) = 2(4n+1)$. I don't know where I was going with that and ended up getting stuck again.
How would you solve this question (would you try to determine the function at all)? What would be the tools you use to attack this? If possible, can you please provide a solution to the problem?
Thanks a lot.
Best Answer
Hint
Prove that $f$ is injective. After that you can conclude that $f(2n)=2f(n)$ and then $$f(2n)=2f(n)\to f(2^k\cdot n)=2^kf(n)\quad (1)$$
Now you have to calculate $f(63)$. But, $63=4\cdot 15+3$.