TST

a) We prove by induction on $n$ that $a_n=s_2(n)$ for all $n\ge 1$ where $s_2(n)$ is the sum of the digits of $n$ in binary representation.

The base case $n=1$ is trivial. Now, we assume that $a_n=s_2(n)$ is proved for $n=1,2,\dots ,k$, and prove it for $n=k+1$.

We shall prove the statement for $k$ with some cases as follows.

• $2\mid k+1$, let $k+1=\overline{x_1{x}_2...x_{m-1}{x}_m}(2)$ with $x_1=1,x_m=0$. It follows $\frac{k+1}{2}=\overline{x_1{x}_2...x_{m-1}}(2)$, so $$a_{k+1}=a_{\frac{k+1}{2}}=s_2\left(\frac{k+1}{2}\right)=s_2(k+1).$$ • $2\mid k$, let $k+1=\overline{x_1{x}_2...x_{m-1}{x}_m}(2)$ with $x_1=1,x_m=1$. It follows $\frac{k}{2}=\overline{x_1{x}_2...x_{m-1}}(2)$, so $$a_{k+1}=a_{\frac{k}{2}}+1=s_2\left(\frac{k}{2}\right)+1=s_2(k+1).$$ Therefore in all cases, we always have $a_{k+1}=s_2(k+1)$. So that $a_n=s_2(n)$ for all positive integers $n$. We distinguish two cases regarding the value of $n$.

Case 1. $n<3$, it is easy to see that $n\in \{1,2\}$ satisfied.

Case 2. $n\ge 3$, we investigate three subcases

Subcase 1. if $n=\overline{\mathrm{100...0}}(2)$ then choose $k=3$, so $kn=\overline{\mathrm{1100...0}}(2)$, which is not satisfying $a_n=a_{kn}$.

Subcase 2. if $n=\overline{\mathrm{111...1}}(2)$ then we will prove $n$ in this case satisfied. Assume that $n=2^t-1$, with $k<n$ and $k$ is odd, expand $k=\overline{x_1{x}_2...x_t}(2)$. We have $$kn=\overline{x_1{x}_2...x_t\overline{\mathrm{00...0}}(2)}-\overline{x_1{x}_2...x_t\overline{0}(2)}=\overline{x_1{x}_2...x_{t-1}\overline{0y_1{y}_2...y_{t-1}}\overline{1}}$$ with number $\overline{x_1{x}_2...x_t\overline{\mathrm{00...0}}(2)}$ have $t$ digits 0 after $x_t$ and $y_i=1+x_i(\mathrm{mod}2)$ for all $i<t$ because $$\overline{y_1{y}_2...y_{t-1}}\overline{1}(2)+\overline{x_1{x}_2...x_{t-1}}\overline{1}=\overline{\mathrm{100...0}}(2)(\mathrm{mod}2)\text{ (t numbers 0).}$$ Thus, $s_2(kn)=1+0+{\sum }_{i=1}^{t-1}(x_i+y_i)=t$ for all $k$ odd.

On the other hand, if $k$ is even then $s_2(kn)=s_2\left(\frac{k}{2^{v_2(k)}}\cdot n\right)=t$.

Thus, $s_2(kn)=t$ for all $k<n+1$.

Subcase 3. $n$ does not have the form of $2^t$ or $2^t-1$. Let $n=2^p\cdot q$ where $q$ is odd and greater than 1, we have

$p>0$, let $n={\overline{x_1{x}_2\dots x_{m}00\dots 0}}_{(2)}$ with $p$ digits 0, so $x_m=1$. Choose $k=\overline{100\dots 01}$ with $k-1$ digits 0, so $$nk=2^p({\overline{x_1\dots x_{m}0\dots 0}}_{(2)}+{\overline{x_1\dots x_m}}_{(2)})=2^p\overline{x_1\dots x_m{x}_1\dots x_m}.$$ Therefore, $s_2(kn)=2s_2(n)$, which is not satisfied.

$p=0$, let $n=\overline{x_1{x}_2\dots x_k{x}_{k+1}{x}_{k+2}\dots x_t}$, with $x_1=1=x_{k+1}=1$ and $x_{k+2}=\cdots =x_t=0$ because $t$ does not have the form of $2^t-1$. Choose $k={\overline{100\dots 01}}_{(2)}$ with $t-2$ digits 0. It follows that $$\begin{array}{rl}kn& =2^{t-1}n+n={\overline{x_1{x}_2\dots x_{t}00\dots 0}}_{(2)}+{\overline{x_1{x}_2\dots x_t}}_{(2)}\\ & ={\overline{x_1{x}_2\dots x_{k}100\dots 0x_2{x}_3\dots x_t}}_{(2)}\end{array}$$ with ${\overline{x_1{x}_2\dots x_{k}100\dots 0x_2{x}_3\dots x_t}}_{(2)}$ have $t-k+1$ digits 0 from $t^{th}$ in the left to $k^{th}$ in the right and ${\overline{x_1{x}_2\dots x_{t}00\dots 0}}_{(2)}$ have $t-1$ digits 0 at the end. Thus, $s_2(kn)=s_2(n)+x_1+x_2+\cdots +x_k>s_2(n)$ since $x_1=1$, which do not satisfied $a_{kn}=a_n$ for all $k\le n$.

Hence, there are only $n=2$ and $n=2^t-1$ satisfied.

b) Choose $m=2^p$, so $a_m=1\le a_{km}$ for all positive integers $k$.

$\square$