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$.
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...

Similar threads

Back
Top