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 3 of 6: Step 3
Previous stepNext step
f(n)=n⟺b1⋯br=br⋯b1f(n)=n\Longleftrightarrow b_1\cdots b_r=b_r\cdots b_1
Detailed analysis

Fixed points are exactly those with palindromic interior. A binary word of length rr has 2⌈r/2⌉2^{\lceil r/2\rceil} palindromes.