Project Euler problem 16 -What is the sum of the digits of the number 2^1000?

215 = 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?


The problem no. 16 in Project Euler required us to find the sum of all the digits of the number 2^{1000}. Well, a no brainer would be to use the BigInteger and find the number by multiplication. I wanted a better solution.

But my knowledge and wits failed me. I must accept taking help on this one. I googled up a bit and found a very neat way of exponentiation. The basic funda is this:

2^n = 2 * 2^{n-1}

=> 2^n = 2^{n-1} + 2^{n-1}

So at any given time, if we have an array of digits of say 2^p, then getting 2^{p+1} is as simple as doubling all the digits and adjusting the carry-overs. The same principle can be easily extended to deal with any base.

class Problem_16 {
public long sumOfDigits(int base, int exp) {
int numberOfDigits = (int) Math.ceil(exp * Math.log10(base));
System.out.println(numberOfDigits);
int[] digits = new int[numberOfDigits];
digits[0] = base;
int currentExp = 1;


while (currentExp < exp) {
currentExp++;
int carry = 0;
for (int i = 0; i < digits.length; i++) {
int num = base * digits[i] + carry;
digits[i] = num % 10;
carry = num / 10;
}
}

long sum = 0;
for (int digit : digits)
sum += digit;


return sum;
}

public static void main(String[] args) {
int base = 2;
int exp = 10;
System.out.println(new Problem_16().sumOfDigits(base, exp));
}
}


Run here https://ideone.com/pYciv