MathDB
function

Source:

May 18, 2015
number theoryfunction

Problem Statement

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