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 21000}?

You probably can compute the direct value of 2^1000. For example, in Python, you can obtain value of (2**1000) and convert it to string. In Java, you can use BigInteger to compute the value of two to the power of 1000.

We can use an array, or hash map to store the digits of any big number. Each time we multiple each position (the values) of the array/hashmap by two, then we need to start from the ‘One’ position to carry over the digits.

The following Javascript code first computes the value of 2¹⁰⁰⁰ (values store in a dictionary), then compute the sum of all the digits using reduce() method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

let arr = {
    0: 1
};
 
for (let i = 1; i <= 1000; ++i) {
    // multiple each digit by two
    Object.keys(arr).map(x => {
        arr[x] *= 2;
    });
    let c = Math.floor(arr[0] / 10);
    let j = 1;
    arr[0] %= 10;
    // highest position
    const maxKey = Math.max(...Object.keys(arr));
    while ((c > 0) || (j <= maxKey)) {
        if (typeof arr[j] === 'undefined') {
            arr[j] = c;
        } else {
            arr[j] = arr[j] + c;
        }
        c = Math.floor(arr[j] / 10);
        arr[j] %= 10;
        j ++;
    }
}
 
// sum up all the digits
console.log(Object.values(arr).reduce((a, b) => a + b));

let arr = {
    0: 1
};

for (let i = 1; i <= 1000; ++i) {
    // multiple each digit by two
    Object.keys(arr).map(x => {
        arr[x] *= 2;
    });
    let c = Math.floor(arr[0] / 10);
    let j = 1;
    arr[0] %= 10;
    // highest position
    const maxKey = Math.max(...Object.keys(arr));
    while ((c > 0) || (j <= maxKey)) {
        if (typeof arr[j] === 'undefined') {
            arr[j] = c;
        } else {
            arr[j] = arr[j] + c;
        }
        c = Math.floor(arr[j] / 10);
        arr[j] %= 10;
        j ++;
    }
}

// sum up all the digits
console.log(Object.values(arr).reduce((a, b) => a + b));

The answer is 1366.

Based on the same algorithm, we can solve another math puzzle: Compute Factorial Digit Sum: Find the sum of the digits in the number 100!

–EOF (The Ultimate Computing & Technology Blog) —