HINT for summing digits of a large power

In this case, I'm afraid you just have to go ahead and calculate $2^{1000}$. There are various clever ways to do this, but for numbers this small a simple algorithm is fast enough.

The very simplest is to work in base 10 from the start. Faster is to work in binary, and convert to base 10 at the end, but this conversion is not completely trivial. A compromise (on a 32-bit machine) would be to work in base 1000000000, so that you can double a number without overflow. Then at the end the conversion to base 10 is much simpler.


Just note that no problem in Project Euler requires you to use bigger numbers than $2^{64}-1$ (or $2^{63}-1$ for signed). However sometimes it is just too painful to avoid big numbers, so it is just easier to use them.

That being said, I don't think there is a mathematical trick for this problem, although I think the problem really just asks you to implement your own multiplication in terms of base $10$ digits. You know already how to do that on paper! Try $2\cdot 2$, $4 \cdot 2$, $8 \cdot 2$, $\dots$ by hand, notice how digits are carried over. Try to formalize this into an algorithm that uses array for digits. Test it for small values, then use it for $2^{1000}$ (just repeat $1000$ times). Finally it is only about the sum.

It might feel a bit unsatisfactory that all you are required to do is multiplication, but hey, it is just $16$-th problem yet!