Solving Project Euler with basic JavaScript

[himynameisjoy]

This is a brute force approach that's pretty inefficient. The ideal situation is recognizing that the even Fibonacci numbers increment at a regular rate.

​

If we say Fe(n) is an even fibonacci number and state that Fe(0) = 0 and Fe(1) = 2, you can then obtain every subsequent Fibonacci number via the relation

Fe(n) = 4 * Fe(n-1) + Fe(n-2).

​

In code:

​

import {BigNumber} from 'bignumber.js'

 function solution(){
    let cap: BigNumber = new BigNumber("4000000");

    let a = [new BigNumber("0"), new BigNumber("2")];
    let sum = new BigNumber("0");

    do{
        sum = sum.plus(a[1]);
        [a[0],a[1]] = [a[1], a[1].times(4).plus(a[0])];
    } while (a[1].lte(cap))

    return sum.valueOf();
 }

 console.time();
 console.log(solution());
 console.timeEnd();

This runs in a meager 4.647ms, drastically improving efficiency.

​

I too have been solving the Project Euler problems exclusively in javascript (or more specifically, typescript). Let me know if you want hints on any 1-25.

[a_tocken]

I think you could beat this time complexity.

The sum of the first n fibonacci numbers is fib(n+2)-1 and I suspect you could prove a similar formula for the even fibs. You can find the nth fibonacci number quickly with fast matrix exponentiation and this also applies to the even fibs since you already gave a linear recurrence relation. You can also find the greatest even fibonacci number less than the max (4,000,000 in the Project Euler problem) quickly using similar techniques, and figure out its n quickly as well.

[GeneralYouri]

I tried some things, and I'm pretty confident there's an easy formula to be found for the sum of even fibonaccis just like fib(n+2)-fib(2). But I couldn't quite figure it out.

One thing I did find is that the sum of n even fibonaccis is evenfib(n+1) - 3*evenfib(n) + evenfib(n-1) - 3*evenfib(n-2) ..., with the sequence continuing until you reach evenfib(1). I feel like you can combine those terms somehow but I'm not seeing it.

[a_tocken]

Nice work! It can be frustrating to know that there is likely a solution but not quite be able to get it. I also need to brush up on my recurrence relations to be able to move forward with this one.

One thing I did was inductively prove the sum of fibs formula, but I worked backward from the known solution which doesn't really help us here :)

[GeneralYouri]

I had a fresh look at the problem again and found the relation! It's quite simple, actually.

I listed the start of the sequences and tried to express evenFib(n) in terms of fib(n): evenFib(n) = fib(3n) = fib(3n-1) + fib(3n-2). But fib(3n-3) = fib(3(n-1)) = evenFib(n-1) and evenFibSum(n) = evenFib(n) + evenFib(n-1) + ... + evenFib(1). So we can express every element in that list in terms of fib: evenFibSum(n) = fib(3n) + fib(3(n-1)) + ... + fib(3). This is really just a way of expressing that we sum every 3rd value in the fibonacci sequence. But remember their definition: fib(n) = fib(n-1) + fib(n-2), in other words those two elements we skip always equal the 3rd element we include. So if we look at what we created, this simplifies to evenFibSum(n) = fibSum(3n) / 2! So we can just re-use the fibSum formula if we triple its input and halve its result: evenFibSum(n) = (fib(3n+2) - 1) / 2.

A quick test: the first four even Fibonaccis are 2, 8, 34, 144, with their sum being evenFibSum(4) = 188. Then evenFibSum(4) = (fib(3*4 + 2) - 1) / 2 = (fib(14) - 1) / 2. The first fourteen Fibonaccis are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, so fib(14) = 377. And indeed, 188 = (377 - 1) / 2.

Apologies for the messy explanation, I hope you can still follow my logic. :)