MathLabs

Problem 3

A function ff on positive integers is defined by f(1)=1f(1)=1, f(3)=3f(3)=3, f(2n)=f(n)f(2n)=f(n), f(4n+1)=2f(2n+1)−f(n)f(4n+1)=2f(2n+1)-f(n), and f(4n+3)=3f(2n+1)−2f(n)f(4n+3)=3f(2n+1)-2f(n). Determine the number of positive integers n≤1988n\le1988 for which f(n)=nf(n)=n.
Step 2 of 6: Step 2
Previous stepNext step
n=(1brbr−1⋯b11)2⟹f(n)=(1b1b2⋯br1)2n=(1b_rb_{r-1}\cdots b_1 1)_2\Longrightarrow f(n)=(1b_1b_2\cdots b_r1)_2
Detailed analysis

Induction on binary length gives: if odd n has digits 1b_r...b_1 1, then f(n) has digits 1b_1...b_r1. Thus f reverses exactly the interior block.