Solving Project Euler 16 with Javascript

Question

I'm working on Project Euler, writing solutions in JavaScript. However, it seems Problem 16 cannot be solved with Javascript:

2¹⁵ = 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¹⁰⁰⁰?

Because JavaScript's 64bit precision isn't big enough to hold the number, calculating Math.pow(2, 1000) gives 1.0715086071862673e+301. Obviously, I can't use this value to solve the problem because it doesn't contain all the digits of 2¹⁰⁰⁰.

Is there another way to solve this problem? Note that I am not asking how to get around the precision issue; however, if that's the only solution, so be it.

Ideally, I'd like to find an alternate solution (maybe a super-epic math approach?) to the problem.

_{(as an side note, i'm not trying to cheat and wean the answer out of SO. I've solved it, but I had to use Python)}

score 3 · Accepted Answer · answered Mar 23 '12 at 04:46

It is possible to solve this by a naive approach of storing 2^1000 in an array (of digits). Runs in less than a second. Original idea from here.

var number = [1],
    sum = 0;

for(var i = 0; i < 1000; i++)
{
    var overflow = 0,
        count = number.length + 1

    for(var j = 0; j < count; j++)
    {
        var digit = number[j] || 0;

        digit = 2 * digit + overflow;

        if(digit > 9)
        {
            digit -= 10;
            overflow = 1;
        }
        else
        {
            overflow = 0;
        }

        number[j] = digit;
    }
}

for(var i = 0; i < 1000; i++)
{
    sum += number[i];
}

console.log(sum);

score 1 · Answer 2 · edited May 23 '17 at 11:59

1

check out a question I asked earlier: summing exponents in javascript

The response talks about BigNumber in JavaScript. That should help you get around the precision shortfalls in JavaScript when dealing with large numbers.

edited May 23 '17 at 11:59

Community

1
1

answered Mar 23 '12 at 04:12

Nic Meiring

882
5
16
33

Like I (sort of) mentioned in my question, i'd like to avoid this kind of solution if possible, but if that's the only way, so be it. +1 for now, if nothing better crops up after a day or so i'll mark as answered – Thomas Shields Mar 23 '12 at 04:17

Solving Project Euler 16 with Javascript

2 Answers2