MHB Find the largest value in a sequence

  • Thread starter Thread starter anemone
  • Start date Start date
  • Tags Tags
    Sequence Value
AI Thread Summary
The sequence defined by \( a_1=1 \), \( a_{2n}=a_n \), and \( a_{2n+1}=a_{2n}+1 \) reaches its maximum value of 10 at \( a_{1023} \). This maximum occurs for the first time with the binary representation of 1023 containing ten 1s. To find how many times this maximum occurs up to \( a_{1989} \), it is noted that in the range from 1024 to 2047, numbers with 10 ones in their binary representation can be identified. Specifically, five numbers less than or equal to 1989 have \( a_k=10 \). Thus, the largest value in the sequence up to 1989 is 10, occurring a total of six times.
anemone
Gold Member
MHB
POTW Director
Messages
3,851
Reaction score
115
The sequence $$a_1,\;a_2,\;a_3,\cdots$$ is defined by $$a_1=1$$, $$a_{2n}=a_n$$, $$a_{2n+1}=a_{2n}+1$$.

Find the largest value in $$a_1,\;a_2,\;a_3,\cdots,\; a_{1989}$$ and the number of times it occurs.
 
Mathematics news on Phys.org
anemone said:
The sequence $$a_1,\;a_2,\;a_3,\cdots$$ is defined by $$a_1=1$$, $$a_{2n}=a_n$$, $$a_{2n+1}=a_{2n}+1$$.

Find the largest value in $$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$.
 
Last edited:
caffeinemachine said:
anemone said:
The sequence $$a_1,\;a_2,\;a_3,\cdots$$ is defined by $$a_1=1$$, $$a_{2n}=a_n$$, $$a_{2n+1}=a_{2n}+1$$.

Find the largest value in $$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.
 
Opalg said:
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.
 
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$.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Thread 'Imaginary Pythagoras'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...

Similar threads

Back
Top