Question 17
(SWE 1) Let $\alpha(n)$ be the number of digits equal to one in the binary representation of a positive integer $n$. Prove that:
(a) the inequality $\alpha(n^2)\le\frac12\alpha(n)(\alpha(n)+1)$ holds;
(b) the above inequality is an equality for infinitely many positive integers;
(c) there exists a sequence $(n_i)_1^\infty$ such that $\alpha(n_i^2)/\alpha(n_i)\to0$ as $i\to\infty$.
Alternative parts: Prove that there exists a sequence $(n_i)_1^\infty$ such that $\alpha(n_i^2)/\alpha(n_i)$ tends to
(d) $\infty$;
(e) an arbitrary real number $\gamma\in(0,1)$;
(f) an arbitrary real number $\gamma\ge0$.
(a) the inequality $\alpha(n^2)\le\frac12\alpha(n)(\alpha(n)+1)$ holds;
(b) the above inequality is an equality for infinitely many positive integers;
(c) there exists a sequence $(n_i)_1^\infty$ such that $\alpha(n_i^2)/\alpha(n_i)\to0$ as $i\to\infty$.
Alternative parts: Prove that there exists a sequence $(n_i)_1^\infty$ such that $\alpha(n_i^2)/\alpha(n_i)$ tends to
(d) $\infty$;
(e) an arbitrary real number $\gamma\in(0,1)$;
(f) an arbitrary real number $\gamma\ge0$.