Find the largest value in a sequence

[anemone]

The sequence \(\displaystyle a_1,\;a_2,\;a_3,\cdots\) is defined by \(\displaystyle a_1=1\), \(\displaystyle a_{2n}=a_n\), \(\displaystyle a_{2n+1}=a_{2n}+1\).

Find the largest value in \(\displaystyle a_1,\;a_2,\;a_3,\cdots,\; a_{1989}\) and the number of times it occurs.

 

[caffeinemachine]

The sequence \(\displaystyle a_1,\;a_2,\;a_3,\cdots\) is defined by \(\displaystyle a_1=1\), \(\displaystyle a_{2n}=a_n\), \(\displaystyle a_{2n+1}=a_{2n}+1\).

Find the largest value in \(\displaystyle a_1,\;a_2,\;a_3,\cdots,\; a_{1989}\) and the number of times it occurs.

Denote $S_n=\{i:2^{n-1}\leq i<2^n\}$.
Let $f:\mathbb N\to \mathbb N$ be the function $f(k)=a_k$.
Now its not very hard to see that $[\max f(S_n)]+1=\max f(S_{n+1})$.
This easily leads to the answer.
The maximum achieved by the sequence given is $10$.

 

[Opalg]

The sequence \(\displaystyle a_1,\;a_2,\;a_3,\cdots\) is defined by \(\displaystyle a_1=1\), \(\displaystyle a_{2n}=a_n\), \(\displaystyle a_{2n+1}=a_{2n}+1\).

Find the largest value in \(\displaystyle a_1,\;a_2,\;a_3,\cdots,\; a_{1989}\) and the number of times it occurs.

Denote $S_n=\{i:2^{n-1}\leq i<2^n\}$.
Let $f:\mathbb N\to \mathbb N$ be the function $f(k)=a_k$.
Now its not very hard to see that $[\max f(S_n)]+1=\max f(S_{n+1})$.
This easily leads to the answer.
The maximum achieved by the sequence given is $10$.

That neatly answers the first part of the problem. But the question also asks for the number of times that this maximum value occurs. The value 10 occurs for the first time as $a_{1023}$. But to find out how many more times it occurs in $\{a_{1024},\ldots,a_{1989}\}$ it will be necessary to look more closely at the structure of the sequence $\{a_k\}$.

It looks to me as though $a_k$ ought to be the number of 1s in the binary representation of $k$. Maybe that will help to lead to an answer.

 

[caffeinemachine]

That neatly answers the first part of the problem. But the question also asks for the number of times that this maximum value occurs. The value 10 occurs for the first time as $a_{1023}$. But to find out how many more times it occurs in $\{a_{1024},\ldots,a_{1989}\}$ it will be necessary to look more closely at the structure of the sequence $\{a_k\}$.

It looks to me as though $a_k$ ought to be the number of 1s in the binary representation of $k$. Maybe that will help to lead to an answer.

It can be shown by induction that $\max f(S_n)$ occurs at $i=2^{n}-1$ and that it occurs exactly once in $S_n$.
This might settle second part of the problem. I will get back to this in a few hours. Have a test to write.

 

[Opalg]

It looks to me as though $a_k$ ought to be the number of 1s in the binary representation of $k$. Maybe that will help to lead to an answer.

In fact, it's obvious when you think about it. If $b_k$ is the number of 1s in the binary representation of $k$, then $b_{2k} = b_k$ (because the binary representation of $2k$ is the same as that of $k$ with an extra $0$ at the end), and $b_{2k+1} = b_{2k}+1$ (because the binary representation of $2k$ is the same as that of $2k$ with the final $0$ replaced by a $1$). Also, $b_1=1$. Therefore $b_k=a_k$.

So the first number with $a_k=10$ is $1023$ (whose binary representation consists of ten $1$s). In the range from $1024$ to $2047$, the numbers all have 11 binary digits, so the only ones with $a_k=10$ will be those with one binary digit $0$ and all the rest $1$s. Enumerating these, we get

$10111111111_2 = 1535_{10}$,
$11011111111_2 = 1791_{10}$,
$11101111111_2 = 1919_{10}$,
$11110111111_2 = 1983_{10}$,
$11111011111_2 = $ (greater than $1989$ in base 10, so we can stop there).​

So there are five numbers $\leqslant 1989$ for which $a_k=10$.