# Project Euler

## Power digit sum

### Problem 16

2^{15} = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^{1000}?

In additional to use recursion, a very fundamental strategy call divide & conquer method can be used in here to minimize the number of time to do multiplication. Note that , splitting the exponent each time and multiply itself will cut the multiplication by half. However, the number of digits for the answer is long (> 300 digits), using an array of integer (or char) is a must without special library and cause the multiplication of two long digits values quite cumbersome at each stage. Therefore, the solution seems to be easier to iteratively multiply 2 for 1000 time onto the interim result.