Robert Eisele
Engineer, Systems Architect and DBA

Project Euler 16: Power digit sum

Problem 16

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

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:

  413*549
+  206500
+   16520
+    3717
=  226737

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);

« Back to problem overview