Q23 Matemática  (Balkan MO Shortlist 2014)

Seja $f:\mathbb{N}\to \mathbb{N}$ uma função dos inteiros positivos para os inteiros positivos para os quais $f(1)=1,f(2n)=f(n)$ e $f(2n+1)=f(n)+f(n+1)$ para todos os $n\in \mathbb{N}$. Prove que para qualquer número natural $n$, o número de números naturais ímpares $m$ tal que $f(m)=n$ é igual ao número de inteiros positivos não maiores que $n$ não tendo fatores primos comuns com $n$.