MathDB

Let

f

be the function of the set of positive integers into itself, defined by

f(1) = 1

f(2n) = f(n)

and

f(2n + 1) = f(n) + f(n + 1)

. Show that, for any positive integer

n

, the number of positive odd integers m such that

f(m) = n

is equal to the number of positive integers[color=#0000FF] less or equal to

n

and coprime to

n

.
[color=#FF0000][mod: the initial statement said less than

n

, which is wrong.]

Problem Statement