Question 53
Let $f: N \rightarrow N$ be a function from the positive integers to the positive integers for which $f(1) = 1$, $f(2n) = f(n)$ and $f(2n+1) = f(n)+f(n+1)$ for all $n \in N$. Prove that for any natural number $n$, the number of odd natural numbers $m$ such that $f(m) = n$ is equal to the number of positive integers not greater than $n$ having no common prime factors with $n$.