Project Euler no. 16

Question

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?

I would like to solve the Project Euler problem No. 16. I am trying to save the power of 2's in an array. Suppose 2 ^ 6 = 128. Then

int arr[1000];
arr[0] = 1 // or 8 (In other way also)
arr[1] = 2
arr[2] = 8 // or 1
// and so on....

But now the problem is how to solve this.

I am fetching problem in shifting the digit to next array location. Suppose now,

arr[0] = 8;

In next iteration

arr[0] = 1; and array[1] = 6;

Here arr[0] contains 1 and arr[1] contains 6. Next

arr[0] = 3;
arr[1] = 2;
....
....
//2 ^ 6
arr[0] = 1;
arr[1] = 2;
arr[2] = 8;
...
...
//2 ^ 10
arr[0] = 1;
arr[1] = 0;
arr[2] = 2;
arr[3] = 4;
.....
.....

and so on. Please help me.

Answer 1

You should go over each digit, starting with the least significant one, double it and add the carry from the previous one, store the result modulo 10 as the new digit value and if the result is more than 9, set the carry to 1 otherwise set it to 0 (or just perform integer division of the result by 10):

carry = 0
for i = 0 to MAX_DIGITS-1:
   tmp = 2 * digits[i] + carry
   digits[i] = tmp % 10
   carry = tmp / 10

(this is pseudocode - translate it to C for your own use)

---

Just as a side note, computing 2^1000 is extremly easy in binary - it is just 1 followed by 1000 0. Converting the result to decimal representation is a bit tricky but an efficient binary to BCD conversion methods exist. But I would still recommend that you use the GNU MP library instead. It only takes 6 lines to compute 2^1000 using GNU MP (the #define line and all whitespace lines are not counted):

#include <gmp.h>

#define MAX_DIGITS 302

mpz_t bignum;
char str[MAX_DIGITS+2];

mpz_init2(bignum, 1001);
mpz_ui_pow_ui(bignum, 2, 1000);  // set the integer object to 2^1000
mpz_get_str(str, 10, bignum);    // convert to base 10

Note that 2^1000 is 1001 binary digits and about 302 (equal to 1001*log(2)) decimal digits. Add two characters for a possible sign character and a NULL terminator character as requried by mpz_get_str().

Now you only have to go over the resulting digits in str, convert them to integers and sum them all up.