Define the sequence $(a_n)$ as $a_1 = 1$, $a_{2n} = a_n$ and $a_{2n+1} = a_n + 1$ for all $n\geq 1$. a) Find all positive integers $n$ such that $a_{kn} = a_n$ for all integers $1 \leq k \leq n$. b) Prove that there exist infinitely many positive integers $m$ such that $a_{km} \geq a_m$ for all positive integers $k$.
Problem
Source: Vietnam TST 2021 P1
Tags: number theory, inequalities
05.04.2021 05:44
any ideas?
19.04.2021 16:34
It’s 2^t-1
29.01.2022 15:11
First notice the following Lemma: $a_n=s_2(n)$, where $s_2$ is the sum of the digits of $n$ written in binary. So we basically work in binary from now on. a) The solution is all $n$ of the form $2^t-1$, and let $m=\lceil \log_2 (n)\rceil$ be the number of digits of $n$ in binary. First notice that the only power of $2$ that works is $2^1$, since $a_{n}=1\leftrightarrow n=2^k$, so we can consider $n>2^{l_n}$ Proof of necessity: Supose by contradiction that $n$ has a $0$ in it's binary representation. Let the rightmost such 0 be after $i$ $1$'s, so $n=\overline{a0 \underbrace{1\dots 1}_\text{i 1's} }$ for some $a$. Then since $2^{m-1}+1\leq n$ $$s_2(n)=s_2(n\cdot (2^{m-1}+1))=s_2(\overline{n \underbrace{0\dots 0}_\text{m-1 0's}}+\overline{\underbrace{n}_\text{m digits}})=s_2(\overline{a1\underbrace{0\dots 0}_\text{i 0's} \underbrace{(n-\lfloor \log_2(n)\rfloor)}_\text{m-1 digits} })=s_2(a)+1+s_2(n)-1>s_2(n)$$ a contradiction. So $n$ cannot contain any $0$'s. $\blacksquare$ Proof of sufficiency: It suffices to show that $s_2((2^t-1)k)=t$ for all odd $1\leq k\leq 2^t-1$. Even $k$'s are then implied. Write $k=\overline{c1}$ and calculate: $$s_2((2^t-1)k)=s_2(\overline{c1\underbrace{0\dots 0}_\text{t 0's}}-k)=s_2(\overline{c\underbrace{0\dots 0}_\text{t+1 0's} } + \overline{ \underbrace{1\dots 1}_\text{t 1's} } -\overline{c1}+1)=s_2(\overline{c\underbrace{0\dots 0}_\text{t+1 0's} }+\overline{\underbrace{2^t-1-k}_\text{t digits, ending in a 0}}+1)=s_2(c)+t-s_2(k)+1=t$$So we are done $\blacksquare$ b) Take $m=2^t$m so $a_km\geq 1=a_m$. Done