Project Euler no. 16

c

Solution

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.

Problem

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.

Original source