Matematyka.pl

Niech
\(\displaystyle{ f(2n) = \frac{1}{2} f(n) }\) oraz \(\displaystyle{ f(2n+1) = 1+f(2n) }\) oraz \(\displaystyle{ f(0) = 0.}\)
Ile jest liczb m takich, że \(\displaystyle{ m = 2^{20} f(m)}\) ?

Naiwne podejście. Bez dowodów. Heurystyka i hipotezy. Wypiszmy kilka wyrazów ciągu \(\displaystyle{ f}\)
\begin{tabular}{|c|c|c|}
\hline
n & f(n) & \checkmark \\
\hline
\red{1} & \red{1/1} & \checkmark \\
\blue{2} & \blue{1/2} \\
\blue{3} & \blue{3/2} & \checkmark \\
\red{4} & \red{1/4} \\
\red{5} & \red{5/4} & \checkmark \\
\red{6} & \red{3/4} \\
\red{7} & \red{7/4} & \checkmark \\
\blue{8} & \blue{1/8} \\
\blue{9} & \blue{9/8} & \checkmark \\
\blue{10} & \blue{5/8} \\
\blue{11} & \blue{13/8} \\
\blue{12} & \blue{3/8} \\
\blue{13} & \blue{11/8} \\
\blue{14} & \blue{7/8} \\
\blue{15} & \blue{15/8} & \checkmark \\
\red{16} & \red{1/16} \\
\red{17} & \red{17/16} & \checkmark \\
& \dots \\
\hline
\end{tabular}
Gdzie \(\displaystyle{ \checkmark}\) oznacza, że spełnione jest równanie \(\displaystyle{ f(m)=m/2^k}\) dla pewnego \(\displaystyle{ k=0,1,\dots}\). Jeszcze w binarnym systemie to zapiszmy:
\begin{tabular}{|c|c|c|}
\hline
n & f(n) & \checkmark \\
\hline
\red{(1)_2} & \red{(1)_2/1} & \checkmark \\
\blue{(10)_2} & \blue{(01)_2/2} \\
\blue{(11)_2} & \blue{(11)_2/2} & \checkmark \\
\red{(100)_2} & \red{(001)_2/4} \\
\red{(101)_2} & \red{(101)_2/4} & \checkmark \\
\red{(110)_2} & \red{(011)_2/4} \\
\red{(111)_2} & \red{(111)_2/4} & \checkmark \\
\blue{(1000)_2} & \blue{(0001)_2/8} \\
\blue{(1001)_2} & \blue{(1001)_2/8} & \checkmark \\
\blue{(1010)_2} & \blue{(0101)_2/8} \\
\blue{(1011)_2} & \blue{(1101)_2/8} \\
\blue{(1100)_2} & \blue{(0011)_2/8} \\
\blue{(1101)_2} & \blue{(1011)_2/8} \\
\blue{(1110)_2} & \blue{(0111)_2/8} \\
\blue{(1111)_2} & \blue{(1111)_2/8} & \checkmark \\
\red{(10000)_2} & \red{(00001)_2/16} \\
\red{(10001)_2} & \red{(10001)_2/16} & \checkmark \\
& \dots \\
\hline
\end{tabular}

Wygląda więc na to, że

Zatem dla \(\displaystyle{ k=21}\) zmilczamy palindromy. Jest ich \(\displaystyle{ 2^{10} \times 2}\). I tyle pewnie jest rozwiązań.