Euler Project Problem 2

Problem 2:

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, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution:

It it useful to tackle this problem from a more generic setting, in order to gain more insights into workings of Fibonacci sequences. 

The basic definition remains:  F(n) = F(n-1) + F(n-2)   n>=3 element of N

In this formulation, the first 2 numbers must be defined separately. Here we define them as follows:
F(1) = A and

F(2) = B

For F(k) to be even,

1) Both A and B are even; or

2) If both A and B are odd, F(k) will be even for all k of the form 3n element of N

3) If A is odd and B is even; F(k) will be even for all k of the form 3n+2 element of N 

4) If A is even and B is odd; F(k) will be even for all k of the form 3n+1 element of N

For case 1 (Both A and B even): All nos in F(x) as even, and the sum of evens is simply the sum of the series.


For the rest 3 cases:

Now that we have seen that evens occur every 3rd number in the series:

F(i) = F(i-1) + F(i-2)
=> F(i) = 2F(i-2) + F(i-3)                                                                       -(1)
=> F(i)= 3F(i-3) + 2F(i-4)
=> F(i)= 3F(i-3) + { 2F(i-5) + F(i-6) } + F(i-6)

=> F(i)= 3F(i-3) + { F(i-3) } + F(i-6)                                                     - Using (1)

=> F(i)= 4F(i-3) + F(i-6)                                                                         

Defining E(k) as even numbers in the the Fibonacci series

E(i) = 4E(i-1) + E(i-2)                                                                            -(2)

Now, sum of all evens in the Fib series is the same as the sum of all nos in this E(k) series. Defining S(R) = Sum ( E(j) ) for all j from 0 to R

Rewriting (2);

4 E(R) = E(R+1) - E(R-1)

4 E(R-1) = E(R) - E(R-2)

4 E(R-2) = E(R-1) - E(R-3)

......

4E(2) = E(3) - E(1)

4E(1) = E(2) - E(0)

Summing both sides;

4(S(R) - E(0)) = E(R+1) + E(R) - E(1) - E(0)

=> S(R) = [ E(R+1) + E(R) - E(1) + 3E(0)]/4                                     -(3)

For the case of A = 1 and B = 2;

E(0) = 2

E(1) = 8

Simply enumerating the series in excel, I see that E(10) =  3,524,578 and E(11) = 14,930,352

So the required sum S(R) = [ 14,930,352 + 3,524,578 - 8 + 3*2]/4 = 4,613,732

Euler Project Problem 1

I recently came across Project Euler. This is a collection of problems needing some combination of maths and programming to solve.

I will try to solve one problem everyday and post the solutions here. The first few problems are hopefully relatively straightforward - fingers crossed.

Problem 1:

" If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000."

Solution:

To get this, one just needs to sum all the multiples of 3 and 5 and subtract the double countings (multiples of 15). 

So for the sum for all such numbers below N; 

S = Sum_i (1 to int[N/3]) 3i + Sum_i (1 to int[N/5]) 5i - Sum_i (1 to int[N/15]) 15i
=> S = 3* ( int[N/3] * (int[N/3] +1)/2 ) + 5* ( int[N/5] * (int[N/5] +1)/2 ) - 15* ( int[N/15] * (int[N/15] +1)/2 )

Plugging N = 999;
S = 3*333*334/2 + 5*199*200/2 - 15*66*67/2
= 233168