# Fibonacci summation problem

• 11-25-2009, 06:15 PM
xcallmejudasx
Fibonacci summation problem
Hello all,

I'm slowly working my way through project euler and I'm having trouble with this question.

/* 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.
*/

Here is my code. The answers I've received from different code tweaks have been.
19544084, using the current code
82790068, using repeated terms(when term2 becomes term1 on it's next iteration)

Code:

``` public class Problem2 {         /*  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.         */         public static int term3 = 0;         public static int sum = 0;         public static void main(String[] args) {                 int term1 = 1, term2 = 2;                 System.out.println(fib(term1, term2));         }                 public static int fib(int term1, int term2){                 if(term2 > 40000000){                         //System.out.println("sum: "+sum+", a: "+term1+", b: "+term2);                         return sum;                 }else{                         term3 = term1+term2;                         System.out.println("a: "+term1+", b: "+term2);                         if(term2 % 2 == 0){                                 System.out.print("Adding "+term2+" to "+sum+" = ");                                 sum += term2;                                 System.out.print(sum+"\n");                         }                         return fib(term2, term3);                 }         } }```
Can someone tell me where I might be going wrong? Or a more efficient way to do this. I know I'm doing extra computations since term2 ends up as term1 on the next call. I've noticed that an even answer only appears every 3rd call but I don't know how to incorporate this into some optimization. Any help would be appreciated.
• 11-25-2009, 06:28 PM
xcallmejudasx
Wow. So I was using 40 million instead of 4 million, so disregard pretty much everything except the optimizations. Any advice on a more efficient algorithm?
• 11-25-2009, 10:06 PM
pbrockway2
My first thought would be to just use a for loop and accumulate the sum of the even valued terms. I wouldn't test for evenness since it's clear right from the start which ones are even...

Code:

```public class FibSum {     public static void main(String[] args) {         int o = 1;         int e = 2;         int sum = 0;         while(e <= 40000000) {             // o e o+e o+2*e 2*o+3*e             //    odd odd  even             sum += e;             /*             int newO = o + 2 * e;             int newE = 2 * o + 3 * e;             o = newO;             e = newE;             */             o += 2 * e;             e = 2 * o - e;         }         System.out.println(sum); // 40M limit gives 19544084     } }```
I'm not familiar with the "ethos" of project Euler. Are you supposed to use clever calculating or mathematical insight? Or both? I'd be looking for a "closed form" for the subsequence of even terms.
• 12-01-2009, 07:28 PM
xcallmejudasx
Ya Project Euler has alot of math related questions for people to solve either using upper level mathematics or programming techniques. Your code is great. Aside from removing the recursive overhead in mine the only other way I thought to improve it would be a loop that doesn't bother to calculate if the number is even(thus removing a modulus calculation) and just added every third term, but your's essentially removed the need for a counter also. Very nice.