How to calculate the sum of digits of $2^n$?

Question

How do I find the sum of digits of $2^n$ in general?

Sum of digits of $2^1=2$ is $2$.

Sum of digits of $2^{10}=1024$ is $7$.

I have check there is no obvious pattern or any recurrence that i can find. Any ideas?

** i don't need repeated sums , just single time**

Answer 1

$2^{1} = 2$

$2^{2} = 4$

$2^{3} = 8$

$2^{4} = 16 \rightarrow 7$

$2^{5} = 32 \rightarrow 5$

$2^{6} = 64 \rightarrow 10 \rightarrow 1$

Then..

$2^{7} = 128 \rightarrow 11 \rightarrow 2$

$2^{8} = 256 \rightarrow 13 \rightarrow 4$

$2^{9} = 512 \rightarrow 8$

$2^{10} = 1024 \rightarrow 7$

$2^{11} = 2048 \rightarrow 14 \rightarrow 5$

$2^{12} = 4096 \rightarrow 19 \rightarrow 10 \rightarrow 1$

If you keep this up, it seems you will find that

$2^{n} \equiv 2^{n+6}$

when summing the digits of the result of each.

Answer 2

$2^n$ has $d$ digits if and only if $10^{d-1} \leq 2^n < 10^d$. Taking $\ln$ gives $(d-1) \ln 10 \leq n\ln 2 <d \ln 10$ which gives $d-1 \leq n \frac{\ln 2}{\ln 10} < d$, showing that $d-1$ is equal to the integer part (so-called floor) of $n\frac{\ln 2}{\ln 10}$. The number of digits of $2^n$ is therefore equal to one plus the integer part of $n\frac{\ln 2}{\ln 10}$. This is a closed formula, by the way.

Now, how to calculate the sum $S = \sum_{i=0}^d a_i$ of digits of $2^n$ if we write if $2^n = \sum_{i=0}^d a_i 10^i$, with $0\leq a_i < 10$ ?

Consider $2^n / 10^d = \sum_{i=0}^d a_i 10^i / 10^d = a_d + \sum_{i=0}^{d-1} a_i 10^{i-d}$. Then $a_d$ is the integer part of $2^n / 10^d $. Can we iterate this to get all $a_i$'s ? Yes we can : what do we get if we take the integer part of $2^n / 10^{d-1}$ this time ? We get $10 a_d + a_{d-1}$ and we know $a_d$, so that if I note $F$ the integer part function, I have $a_{d-1} = F(2^n / 10^{d-1}) - 10 F(2^n / 10^{d})$.

You can trivially see that $F( 2^n / 10^{d-2})$ is but $100 a_d + 10 a_{d-1} + a_{d-2}$. Which gives us $a_{d-2} = F( 2^n / 10^{d-2}) - 10 ( F(2^n / 10^{d-1}) - 10 F(2^n / 10^{d})) - 100 F( 2^n / 10^{d})$ which you can simplify as $a_{d-2} = F( 2^n / 10^{d-2}) - 10 F(2^n / 10^{d-1})$.

More generally $a_{d-i} = F( 2^n / 10^{d-i}) - 10 F(2^n / 10^{d-i+1})$. And from this you get easily $S$ by summing all the $a_{d-i}$'s.

Of course, this method is not proper to $2^n$ and works with any integer instead of it.

Answer 3

Nobody in the world knows how to do this faster than calculating the decimal representation of $2^n$ and adding up all its digits. When $n$ gets big, the challenge is to calculate $2^n$ as fast as possible; Fast Fourier Trasforms are the way to go, but this is a deep subject. Start with Wikipedia's article on Karatsuba's algorithm for a gentle introduction and links to further study.

I won a prize (something grotty, like an internal disk drive mount) 30 years ago, when the ARM was brand new. The problem was to calculate the sum of the digits of the largest known prime, which was then (I think) $2^{216091}-1$. The winner was the program that ran fastest on the ARM-based Archimedes computer.

My winning program used Fast Fourier Transforms. It took three weeks to write, and 4 minutes 33 seconds to run. I remember this because it is the length (and indeed title) of John Cage's minimalist classic 4' 33''. Also it is 273 seconds, and -273 is absolute zero in degrees Celsius. Some have speculated that this is not a coincidence (I mean John Cage's title, not my program's running time).