Recursive Function

Let $g(n)$ be the number of $1$ s in the binary representation of $n$ . We claim that $g(n)=f(n)$ .

Obviously $g(1)=f(1)$ because $1_{10}=1_2$ . If $n=2k$ , let $n=a_n*2^n+a_{n-1}*2^{n-1}+...+a_1*2^1$ . Then $k = a_n*2^{n-1}+a_{n-1}*2^{n-2}+...+a_1$ , so $k$ has the same number of $1$ s as $n$ in binary, or $g(2k)=g(k)$ . If $n=2k+1$ , let $n=a_n*2^n+a_{n-1}*2^{n-1}+...+a_1*2^1 + 1$ . It follows that $k= a_n*2^{n-1}+a_{n-1}*2^{n-2}+...+a_1$ , so $n$ has one more of the digit $1$ than $k$ in binary. Hence, $g(2k+1)=g(k)+1$ .

In summary, $g(1)=1$ , $g(n)=g(k)$ if $n=2k$ , and $g(n)=g(k)+1$ if $n=2k+1$ . This means that $g(n)=f(n)$ , as desired.

It suffices to find the number of values of $n$ , $1\le n\le 2013$ such that $n$ has the largest number of $1$ s in binary. Since $2013=11111011101_2$ , which has nine $1$ s in $11$ digits, we see $n$ can at most have ten $1$ s in binary. This occurs when the only $0$ that appears in the binary representation of $n$ is in the $i$ th spot from the left, where $1\le i\le 5$ . Otherwise, if $i>5$ , $n\ge11111011111_2>2013$ .

Thus, there are only $5$ values of $n$ that have ten $1$ s in binary, so the answer is $\boxed{5}$ .

A non-negative integer $n$ can be expressed as $n = \sum_{i=0}^{k}a_i 2^i$ , where $k$ is the largest integer such that $a \geq 2^k$ , and each $a_i = 0$ or $1$ . This is called the binary representation of the number.

Let $g(n)$ be the number of $a_i$ which are equal to $1$ . $g(1) = 1$ . $g(2n)$ can be expressed as $2n = \sum_{i=0}^{k+1}b_i 2^i$ , where $b_0 = 0$ and $b_i = a_{i-1}$ for $1 \leq i \leq k+1$ . Thus, $g(2n) = g(n)$ . $2n+1$ has the same expansion, except that $b_0 = 1$ , and therefore $g(2n+1) = g(n) + 1$ . So, the function $g$ turns out to be identical to the function $f$ in the problem.

The largest $k$ such that $2013 \geq 2^k$ is 10. $2^{11}-1 = 2047$ can thus be expressed as $\sum_{i=0}^{10} a_i 2^i$ , where all the $a_i$ are 1. $f(2047) = 11$ . The numbers less than 2047 for which $f(n) = 10$ are the ones where one of the $a_i$ is changed to 0. This corresponds to subtracting a power of 2, and the numbers are 2047-1, 2047-2, 2047-4, 2047-8, 2047-16, 2047-32, 2047-64, 2047-128, 2-47-256, 2047-512, 2047-1024. Since 2047-2013 = 34, only 2047-64, 2047-128, 2-47-256, 2047-512, 2047-1024 satisfy the condition of being $\leq 2013$ . Those are five numbers, so the answer is five.

Lemma: $f(n)$ is equal to the number of ones in the binary representation of $n$ .

Proof by induction: $n = 1 = 1_2$ , has $1 = f(1)$ ones in its binary representation. as claimed.

Now assume the Lemma holds true for all positive integers $n \le 2^m - 1$ .

If $2^m \le n \le 2^{m+1}-1$ and $n$ is even, then $n = 2k$ where $k \le 2^m - 1$ . So,the binary representation of $n$ is the binary representation of $k$ with a $0$ added at the end. Since $k \le 2^m - 1$ , by the inductive assumption, the binary representation of $k$ has $f(k)$ ones. Hence, the binary representation of $n$ will have $f(k) = f(n)$ ones, as claimed.

If $2^m \le n \le 2^{m+1}-1$ and $n$ is odd, then $n = 2k+1$ where $k \le 2^m - 1$ . So,the binary representation of $n$ is the binary representation of $k$ with a $1$ added at the end. Since $k \le 2^m - 1$ , by the inductive assumption, the binary representation of $k$ has $f(k)$ ones. Hence, the binary representation of $n$ will have $f(k)+1 = f(n)$ ones, as claimed.

Thus, the Lemma holds for all positive integers $n \le 2^{m+1} - 1$ . Therefore, by induction, the Lemma holds for all positive integers $n$ .

End Lemma

Since $2^{10} \le 2013 < 2^{11}$ , any integer $n \le 2013$ will have at most $11$ digits in its binary representation. Then, since $n \le 2013 < 2^{11}-1$ , $n$ cannot have $11$ ones in its binary representation. But $n = 2^{10}-1 \le 2013$ has $10$ ones in its binary representation. Thus, $A = 10$ .

There are $\binom{11}{1} = 11$ integers $n < 2^{11}$ with $10$ ones in their binary representations. These integers are in the form $n = 2^{11} - 2^{k}-1$ for $0 \le k \le 10$ . If we have $0 \le k \le 5$ , this yields $n > 2013$ , but for $6 \le k \le 10$ we get $n \le 2013$ .

Therefore, there are $\boxed{5}$ values of $n$ with $1 \le n \le 2013$ such that $f(n) = A = 10$ .

Lemma . By induction $f(2^ab) = f(2^{a-1}b) = \dots = f(b)$ .

$f(n)$ is the number of ones in the binary representation of $n$ . That is, if $n = 2^{k_1}+2^{k_2}+\dots+ 2^{k_l}$ where $k_i < k_{i+1}$ then $f(n) = l$ .
Proof by induction:
When $l=1$ by previous lemma, $f(2^{k_1}\cdot 1) = f(1) = 1$ . Assume the statement true for all sums of length $l-1$ . Then $\begin{aligned} f(2^{k_1}+\dots + 2^{k_l}) &= f(2^{k_1}\cdot(1+2^{k_2-k_1} + \dots + 2^{k_l - k_1}))\\ &= f(1+2^{k_2-k_1} + \dots + 2^{k_l - k_1})\\ &= f(1+2\cdot (2^{k_2-k_1-1} + \dots + 2^{k_l - k_1-1)})\\ &= f(2^{k_2-k_1-1} + \dots + 2^{k_l - k_1-1}) + 1\\ & = (l-1)+1=l \end{aligned}$ .
The equalities follow from the lemma, the definition of $f$ and the inductive hypothesis.

Now we can consider binary representations of integers in $[1, 2013]$ .
$f(2013_{10}) = f(11111011101_2) = 9$ . The maximum is $f(1023_{10}) = f(1111111111_2) = 10$ . Other numbers with $f(n) = 10$ can be built by inserting a $0$ in this one. Notice that only $5$ of these are lower than $2013$ .

We can write $n$ in base $2$ and prove that the value of $f(n)$ is given by the numbers of digits "1" in the binary representation of $n$ . (We can see it by applying the algorithm of conversion from base 10 to base 2).

We can write $n$ with $11$ binary digits since the maximum value of $n$ is between $1024$ and $2047$ . If all digits are "1" we have that $n=2047$ but it is impossible. So the maximum number of "1" is 10, that implies $A=10$ . So, we have that $n$ must have 10 digits "1" and one digit "0", and the only possible values of $n$ are: $01111111111_2=1023$ , $10111111111_2=1535$ , $11011111111_2=1791$ , $11101111111_2=1919$ and $11110111111_2=1983$ . The others are greater than $2013$

f(n) counts the number of ones on the binary expression of n. we notice that f(2^m) = f(2^{m-1}) = ... f(2) = f(1) = 1 and f(2^m-1) = f(\sum {i=0}^{m-1} 2^i) = f(\sum {i=0}^{m-2} 2^i)+1=f(2^{m-1}-1)+1. The last equality implies f(2^m-1) = f(2^{m-1}-1)+1 = f(2^{m-2}-1)+2= ... = f(2-1)=f(1)+m-1=m. Thus, f(1023) = f(2^{10}-1)=10. Because the definition of f, we notice that f(n) <= log 2 (n+1). Because that f(2k) =f(k),we have that f(2^m-1 + \sum {i=p}^{m-1} 2^i) = f(2\sum {i=p}^{m-1} 2^i + \sum {j=0}^{p-1} 2^j) = f(2\sum {i=p}^{m-1} 2^i) + p-1 = f(\sum {i=p}^{m-1} 2^i) + p-1 = (m+1-p)+p-1=m. then f(1023) = f(1023+512) = f(1023+512+256) = f(1023+512+256+128) = f(1023+512+256+128+64) = 10. Since 1023+512+256+128+64+32 = 2015>2013. We conclude that 5 is the answer

Claim. If n has x '1's when it is written in base 2, then f(n)=x. Proof. We will proceed by induction. Base case: x=1, n=2^a for some non-negative integer a, f(n)=f(2^a)=1. Inductive step: Assume the hypothesis is true. If n has (x+1) '1's when it is written in base 2, f(n)=f(2^(a1)+2^(a2)+...+2^(ax)+2^(a(x+1)))=f(2^(a(i+1))+2^(a(i+2))+...+2^(a(i+x))+1)=f(2^(a(i+1))+2^(a(i+2))+...+2^(a(i+x)))+1=x+1. This proves the claim. Note that 1111111111(base 2)=1023<2013 and 11111111111(base 2)=2047>2013. Since 11111111111(base 2) is the smallest number which contains 11 '1's in base two representation, the maximum value of f(n) occurs when there is exactly 10 '1's in the base 2 representation of n. Therefore, the maximum value of f(n)=10. A=10. There is 1 value of n satisfying f(n)=10 when n has 10 digits in its binary representation and there are 10C1=10 values of n satisfying f(n)=10 when n has 11 digits in its binary representation if 1<=n<2047. Manually calculate all the values of n satisfying 2013<n<2047 and f(n)=10 and we notice that there are 6 such values. The number of values of n with 1<=n<=2013 such that f(n)=A=10 is 1+10-6=5.

Note that $f(k * 2^b) = f(k)$ for all integers $b>0, k>1$ . Then $f(k * 2^b + 1) = f(k) + 1$

Thus we can arrive at the maximum repeating the following: multiply by 2 and add 1.

The most obvious sequence we can find is that of $1, 3, 7, 15, 31,..., (2^q - 1),...,1023$ . The sequence is of length $10$ , which is the max; to prove this, assume there is a sequence of length $11$ . Then $n$ must cycle through $11$ powers of $2$ , or $n \geq 2^{11}-1 \geq 2013$ , but $2013$ is the maximum value. Therefore, $A=10$ .

Thus, we must find sequences that iterate $10$ times without exceeding $2013$ : To build such sequences, it is most favorable to let the resulting $n$ be odd (apply the transformation $n \rightarrow 2n + 1, f(n) \rightarrow f(2n+1) + 1$ - an even value does not increase $f(n)$ but increases $n$ . However, we must double $n$ once so that we don't get the exact same sequence. Note that doubling $n$ at a later point in the sequence results in a larger end value $($ the value of $n$ when $f(n) = 10$ $)$

Four such sequences are found (following normal rules): $1, 2*, 5, 11, 23, 47, 95, 191, 383, 767, 1535$ $1, 3, 6*, 13, 27, 55, 111, 223, 447, 895, 1791$ $1, 3, 7, 14*, 29, 59, 119, 239, 479, 959, 1919$ $1, 3, 7, 15, 30*, 61, 123, 247, 495, 991, 1983$

$*$ : We applied the transformation $n \rightarrow 2n$ to get here.

Note that we cannot apply $n \rightarrow 2n$ any later than at $2n=30$ : for example, the next possible sequence is $1, 3, 7, 15, 31, 62*, 125, 251, 503, 1007, 2015$ , but $2015 > 2013$ .

Note that we cannot apply the transformation $n \rightarrow 2n$ more than once: $1, 2*, 4*, 9, 19, 39, 79, 159, 309, 619, 1239, 2479$ but $2479 > 2013$ .

Thus, we have $5$ values of $n$ such that $f(n) = A$ : when $n=1023, 1535, 1791, 1919, 1983$ .

We start with n=1 and multiply by 2 and add 1 each time to find the maximum value of f(n). 1->3->7->15->31->63->127->255->511->1023, so the maximum value A is 10. This is reached at 5 values of n, 1023, 1535,1791,1919,1983. 1535->767->383->191->95->47->23->11->5->2, 1791->895->447->223->111->55->27->13->6->3->1. 1919->959->479->239->119->59->29->14->7->3->1. 1983->991->495->247->123->61->30->15->7->3->1. There is no larger one because 1->3->7->15->31-62->125->251->503->1007->2015>2013. So the answer is 5.

Let $a_2$ denote the number $a$ in base $2$ . Let us show by induction that $f(n)$ is the number of 1's in the binary representation of $n$ .

Base case: Clearly $f(1) = 1 = 1_{2}$ , which is equal to the number of 1's in its binary representation. Assume that $f(k)$ is equal to the number of 1's in its binary representation.

Induction step: $f(2k) = f(k)$ and $(2k)_2 = 10_2\times k_2$ and this is just $k_2$ with a 0 appended at the end, thus it has the same number of ones as $k_2$ . Also, $f(2k+1) = f(k) + 1$ and $(2k+1)_2 = 10_2\times k_2 + 1_2$ and this is just $k_2$ with a 1 appended at the end, thus it has 1 more one than $k_2$ . Therefore $f(2k)$ and $f(2k+1)$ are equal to the number of 1's in their respective binary representations.

Since $2013 < 2^{11}$ , the maximum value of $f(n)$ will be $10$ . We can calculate that $11111111111_2 = 2047_{10}$ and $2047 - 2013 = 35 > 32$ , so the values of $n \leq 2013$ that satisfy $f(n)=10$ are $11110111111_2=1983_{10}$ , $11101111111_2=1919_{10}$ , $11011111111_2=1791_{10}$ , $10111111111_2=1535_{10}$ and $1111111111_2=1023_{10}$ .

Hence, there are $5$ of them.