Project Euler Solution #16: Power digit sum

Problem 16

Solution

The problem can be solved quite quickly with python, which allows arbitrary large integers:

sum(map(int, str(2**1000)))

However, that's wasn't really challenging. Let's figure out, how we can solve the problem without the power of python. As every normal built-in data type can't store such a large number, an array must hold the digits, we can sum over. How large does the array have to be? With Problem 25, I've proven that the length \(L(n)\) of a numer \(n\) is

\[L(n) = \lfloor 1+\log_{10}(n)\rfloor\]

So the number of digits we need to store then is:

\[d = \lfloor 1+\log_{10}(2^{1000})\rfloor = \lfloor 1+1000\cdot \log_{10}(2)\rfloor = 302\]

Based on the 302 elements array, we can construct the number by multiplying 1000 times two. In primary school, we learned how to do long multiplication. A quick reminder with the example 413 times 549:

With this mechanism, we can multiply 1000 times two quite quickly. We don't even need 1000 arrays, one array is enough when we sum the result directly. When implemented, the solution can then look as follows:

function solution(exp) {

    var order = 0;
    var digits = Math.floor(1 + exp * Math.LN2 / Math.LN10);

    var number = new Uint8Array(digits);

    number[0] = 1;

    for (var i = 0; i < exp; i++) {

        var carry = 0;

        for (var j = 0; j <= order; j++) {

            var product = 2 * number[j] + carry;
            number[j] = product % 10;
            carry = product / 10 | 0;

            if (j === order && carry > 0) {
                order++;
            }
        }
    }
    return number.reduce((p, x) => x + p, 0);
}

solution(1000);