Let $S(n)$ be the sum of digits of $n$. How prove that for a given integer $k$ there exist infinitely many $n$ such that $S(2^n+n)+k<S(2^n)$?

I have modified this problem: Denote by $S(a)$ the sum of the digits in the decimal representation of $a$. Prove that there are infinitely many $n\in \mathbb{Z_{+}}$ such that: ${S(2^{n}+n})<S(2^{n})$.

This problem is also true that for every integer $k$ there exist infinitely many $n$ satisfying $S(2^n+n)+k<S(2^n)$.

  • 3
    $\begingroup$ $2^{4k}$ ends in a $6$, so I expect $S(2^{100\dots004}+100\dots004)<S(2^{100\dots004})$. $\endgroup$ – Gerry Myerson Jul 20 '15 at 7:17
  • $\begingroup$ @GerryMyerson This idea works for any base (instead 2) that is is not divisible by 10. $\endgroup$ – grizzly Jul 20 '15 at 8:59
  • 1
    $\begingroup$ Deleting my earlier comment. The idea was to make the remainder of $2^n$ modulo a power of ten as large as possible so that $2^n$ and $2^n+n$ would straddle a multiple of $10^k$. Basically a lot of 9s near the end of $2^n$ and a lot of zeros in $2^n+n$. We can reach the remainder $10^k-2^k$ when $n=2\cdot 5^{k-1}+k$, but that $n$ is too large in comparison to $10^k$ for the trivial estimates for $S(2^n), S(2^n+n)$ to give what is needed (the number of 0s in the bigger number is not high enough. Gerry's idea is more promising. $\endgroup$ – Jyrki Lahtonen Jul 20 '15 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.