Let $t(n)$ be the sum of the digits in the binary representation of a positive integer $n,$ and let $k \geq 2$ be an integer. a. Show that there exists a sequence $(a_i)_{i=1}^{\infty}$ of integers such that $a_m \geq 3$ is an odd integer and $t(a_1a_2 \cdots a_m)=k$ for all $m \geq 1.$ b. Show that there is an integer $N$ such that $t(3 \cdot 5 \cdots (2m+1))>k$ for all integers $m \geq N.$
Problem
Source: Turkish TST 2011 Problem 6
Tags: floor function, limit, number theory, greatest common divisor, induction, prime factorization, number theory proposed
24.07.2011 14:01
crazyfehmy wrote: Let $t(n)$ be the sum of the digits in the binary representation of a positive integer $n,$ and let $k \geq 2$ be an integer. a. Show that there exists a sequence $(a_i)_{i=1}^{\infty}$ of integers such that $a_m \geq 3$ is and odd integer and $t(a_1a_2 \cdots a_m)=k$ for all $m \geq 1.$ b. Show that there is an integer $N$ such that $t(3 \cdot 5 \cdots (2m+1))>k$ for all integers $m \geq N.$ Hint: a,Use lemma: Prove that for any positive integer $n$ there are infinitely many numbers $m$ such that $s_2(n) = s_2(mn)$ with $s_2(m)$ is sum all digit of $m$ in base $2$. Applying lemma with $n=2^k-1$ b,Use remark :Let $p$ be an odd prime. Prove that the exponent of $p$ in the prime factorization of $1 . 3. 5 . . . (2m+ 1)$ is $\sum_{k>0}^{} \left ( \left \lfloor \frac{2m+1}{p^k} \right \rfloor - \left \lfloor \frac{m}{p^k}\right \rfloor \right )$ we will prove $\lim_{n \to +\infty }t(1.3.5..(2m+1))=+\infty$
25.07.2011 18:51
a. Sorry, We will construct sequence a1,a2,... By prove that for k,p : exist q, 2^(p(k 1))-1|2^(q(k 1))-1 and gcd(2^q-1,2^(p(k 1))-1)=1 (1), if it true then 2^pk 2^p(k-1) ... 1|2^qk ... 1 and we be going to sequence by induction. Now chose q , p|q,gcd(q,k 1)=1, gcd (2^q-1, 2^p(k 1)-1)=2^p-1,and gcd (2^p-1,2^q-1)=2^p-1,so (1) true. Dear jejungcn,I not agree your solution,is it true? Not accept. I need a fully done solution, please.!
24.03.2012 11:31
$a.$ Try induction with $a_{k+1}=\frac{(a_1a_2\cdots a_k-1)(2^{\phi(a_1a_2\cdots a_k)}-1)}{a_1a_2\cdots a_k}+1$. $b.$ Try $N=2^{k}-1$. Easier than 1,2.
17.12.2013 08:42
@Bigwood: can you explain part b of your solution? i can't understand
17.12.2013 09:47
Lemma If $n$ is divisible by $2^k-1$, then $s_2(n) \geq 9k.$ part b is trivial if you know this lemma which is proved easily.
01.02.2022 22:32
Here is a solution. a. Define $b_i=\left(\underbrace{1\underbrace{00\cdots 0}_{i-1\; \text{times}}1\underbrace{00\cdots 0}_{i-1\; \text{times}}\cdots 1\underbrace{00\cdots 0}_{i-1\; \text{times}}1}_{k\; \text{times}\; 1}\right)_2=2^0+2^i+2^{2i}+\cdots +2^{(k-1)i}$ where $i\in\mathbb{Z^+}$. Clearly, $t(b_i)=k$. We are trying to find an infinite subsequence of $(b_i)_{i=1}^{\infty}$; $\{b_{j_1}, b_{j_2}, \cdots\}$ such that $b_{j_n}|b_{j_{n+1}}$ for all $n\ge 1$. Because, if such subsequence exist, then we can let $a_1=b_{j_1}$ and $a_i=\frac{b_{j_i}}{b_{j_{i-1}}}$ for all $i\ge 2$ and finish the proof. See that $b_{r}|b_{r(k+1)}$ for all $r\in\mathbb{Z^+}$. Hence, $\{b_1, b_{k+1}, b_{(k+1)^2}, b_{(k+1)^3}, \cdots\}$ is a subsequence which satisfies our condition, done. b. We will prove the following lemma, which clearly finishes the proof. Lemma: If a positive integer $n$ is divisible by $2^k-1$ where $k\in\mathbb{Z^+}$, then $t(n)\ge k$. Proof: For the sake of contradiction, assume that $n_0$ is the smallest positive integer such that $2^k-1|n_0$ and $t(n_0)<k$. Let $n_0=2^{\alpha_1}+2^{\alpha_2}+\cdots +2^{\alpha_{\ell}}$ where $0\leq \alpha_1<\alpha_2<\cdots<\alpha_{\ell}$ and $\ell<k$. If $\alpha_{\ell}\ge k$, then the number $n_1=2^{\alpha_1}+2^{\alpha_2}+\cdots +2^{\alpha_{\ell}-1}+2^{\alpha_{\ell}-k}$ meets the conditions of our assumption and smaller than $n_0$, contradiction. (Check that $n_1\equiv n_0\equiv 0\pmod{2^k-1}$ and $t(n_1)\leq t(n_0)<k$). Hence, we must have $\alpha_{\ell}\leq k-1$. Then, $n_0=2^{\alpha_{\ell}}+2^{\alpha_{\ell-1}}+\cdots +2^{\alpha_{1}}\leq 2^{k-1}+2^{k-2}+\cdots +2^{k-\ell}\leq 2^{k-1}+2^{k-2}+\cdots +2^1<2^k-1$. But $2^k-1|n_0\Rightarrow n_0\ge 2^k-1$, contradiction. Hence completes the proof.