Project Euler, Problem 2 (in Groovy/Java)

Problem 2 in Project Euler is as follows:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

I found it fairly easy to code a basic solution to this problem:

 
	    def fibSeries = [0,1]
	    int sumOfEvenNums = 0  
	    int i = 0
	    while (fibSeries[i]<=4000000) {    
	       i = fibSeries.size
	       fibSeries[i] = fibSeries[i-1]+fibSeries[i-2]           
	       if (fibSeries[i]%2==0) {            
	    	   sumOfEvenNums+=fibSeries[i]
	       }           
	    }
	    println("Total = " + sumOfEvenNums)

This ran relatively quickly (~100ms), so I submitted my answer on projecteuler.net and it was confirmed as correct.

With heinsight, I realise that it is unnecessary for me to store the entire sequence of numbers (in fibSeries). I just need to store 3 numbers: the latest and the previous 2.

After checking the solution notes, there is of course a more 'perfect' solution. Reaching it involves making 2 breakthroughs, which I admit I didn't make on my own!

Breakthrough 1
The first breakthrough is to see the pattern (how could I have missed it!) that only every 3rd number is even, meaning we can safely ignore the rest. The provided solution says that this is easy to prove (I have no idea how to - perhaps a step for another day). But assuming this to be true, the code can be rewritten to

	    int a,b,c
	    b = 1 //1st seed value
	    c = 1 //2nd seed value
	    int sumOfEvenNums = 0
	    while (c<=4000000) {    
	       a=b+c
	       b=c+a
	       c=a+b          
	       sumOfEvenNums+=a
	    }
	    println("Total = " + sumOfEvenNums)

Breakthrough 2
The second, and waaay more difficult breakthrough is to spot (and prove!) that there is a pattern in the even numbers. If you look at them,
2, 8, 34, 144, 610, ...
They obey following recursive relation:
E(n)=4*E(n-1)+E(n-2).
e.g. 144=4(34) + 8
and 34 = 4(8) + 2
It can be proved that for the Fibonacci numbers, the formula F(n)=4*F(n-3)+F(n-6) holds true (I even managed to get the proof of this myself, after a little prodding).

So, this leaves the following 'ultimate' solution:

	    int a = 0
	    int b = 8 //1st seed value
	    int c = 2 //2nd seed value
	    int sumOfEvenNums = b+c
	    while (true) {    
	       a=(4*b)+c
	       if (a>4000000) break
	       sumOfEvenNums+=a
	       c=b
	       b=a	       
	    }
	    println("Total = " + sumOfEvenNums)

I am sure this could even be rewritten in a more elegant form. Especially if Groovy supported a do..while loop.

Anyway, on to Problem#3...

Tags: euler, groovy