BMO2 2011 Question 3 - How to Find the Pattern in this Function? The function $f$ is defined on the positive integers as follows:
$$f(1) = 1$$
$$f(2n) = f(n), \text{if $n$ is even}$$
$$f(2n) = 2f(n), \text{if $n$ is odd}$$
$$f(2n + 1) = 2f(n) + 1, \text{if $n$ is even}$$
$$f(2n + 1) = f(n), \text{if $n$ is odd}$$
Find the number of positive integers n which are less than $2011$ and
have the property that $f(n) = f(2011)$.
Calculating the values of $f(n)$ up to $20$ didn't yield any pattern, so I am not sure where to go from here. Usually I try to figure out whether the function is increasing, decreasing or doing something predictable, but here I do not see it.
 A: (Hint) Another way of viewing the function is by looking at the input upon divisibility by 4. For example, if the input is of the form $2n$ where $n$ is odd, then the input is of the form $2(2k+1) = 4k+2$. Thus we can envision the functions as 
$$
f(n) = \begin{cases}
f(\lfloor n/2\rfloor)& n \equiv 0,3 \mod 4 \\
2f(\lfloor n/2\rfloor)+1& n \equiv 1\mod 4 \\
2f(\lfloor n/2)& n\equiv 2\mod 4
\end{cases}
$$
Moreover, using J.G.'s suggestion, we can work in binary where $\lfloor n/2\rfloor$ is equivalent to deleting the rightmost bit. In binary, $2011 = 11111011011$ so 
\begin{align}
f(11111011011) &= f(1111101101) \\
&= 2f(111110110)+1 \\
&= 4f(11111011)+1 \\
&= 4f(1111101)+1 \\
&= 8f(111110)+5 \\
&= 16f(11111)+5 \\
&= 16f(1)+5 = 21
\end{align} 
Notice immediately that long strings of 1s or long strings of 0s are invariant under this function. This will allow you to construct binary strings whose values don't change. For example, $f(1110110)=f(2011)$.
A: This is a partial answer:
Note that any binary string can be divided into alternating blocks of $0$'s and $1$'s, for example, $1111001101001110=B_1B_2B_3B_4B_5B_6B_7B_8$, where $B_1=1111,\ B_2=00,\ B_3=11,\ B_4=0,\ B_5=1,\ B_6=00,\ B_7=111,\ B_8=0$.  Now note that $f(n)$ will be unchanged if the trailing block is replaced by a single $1$ or a single $0$ (depending on whether the block consisted of $0$'s or $1$'s). Now, note that a trailing $0$ implies $f(n)=2f(n/2)$, and trailing $1$ implies. $f(n)=2f((n-1)/2)+1$, which means $f(n)$ has the binary expansion of where the trailing bit is $0$ or $1$ dependeing on whether the trailing block of   binary expansion of $n$ were a block of $0$ or $1$. 
Repeating this procedure, it is easy to argue that the binary expansion of $f(n)$ is alternating binary number $1010\cdots$ with number of bits equal to the number of alternating blocks in the binary expansion of $n$. For example $f(13)=f(1101_b)=101_b=3$. 
To find the number $g(n)$ of $m\le n$ such that $f(m)=f(n)$, following is an idea:
Let the number of bits in the expansion of $n$ is $k$, and let the expansion of $n$ has $l$ alternating blocks. Then, any number $m<n$ such that $m$ also has $l$ blocks is a candidate to count. Now, if we count all numbers $m$ such that $m\le 2^{k}$, (call that number $h(k)$) and $m$ has $l$ alternating blocks, then that number will overestimate $g(n)$ by some amount, which we denote $e(n,k)$. Then, $g(n)=h(k)-e(n,k)$.
Let $z(n),u(n)$ be the number of blocks of $0$ and $1$, respec., in the binary expansion of $f(n)$, and let it has $c_1,\cdots,\ c_{z(n)}$ and $d_1,\cdots,d_{u(n)}$ elements in those blocks, respec.
Define the following set of $l$-tuples of positive integers: $$S_k=\{m_1,\cdots,\ m_l: 1\le m_j,\ j=1,2,\cdots,\ l,\ \sum_{j=1}^l m_j\le k\}$$ 
After some observation, we can conclude that $h(k)$ is the cardinality of the set $S_k$.
Then it follows that $h(k)$ is the sum of coefficients of $x^{l+j}$ for $j=0,\cdots, k-l$ in the expnasion of $x^l(1-x)^{-l}$, which results in $$h(k)=1+\sum_{j=1}^{k-l}\binom{l+j-1}{j}=\binom{k}{l}$$ 
However, finding $e(k,n)$ seem to be quite difficult. The difficulty lies in finding the pattern in which the number of $0$'s and $1$'s in the blocks can vary for numbers larger than $n$ and having $k$ bits. I can understand that the number of $1$'s in the leading block will always be nondecreasing but how does the number of $0$'s and $1$'s in the latter blocks changes, might require some careful analysis.
So, for example, for the given problem, $f(n)=10101,\ l=5,\ z(n)=2,\ u(n)=3,\ $, $c_1=c_2=1,\ d_1=5,\ d_2=2,\ d_3=2,\ k=11$.
Then, $$h(k)=1+\sum_{j=1}^{6}\binom{4+j}{j}=462$$
