1. ## 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)

Java 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.  Reply With Quote

2. ## 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?  Reply With Quote

3. Moderator   Join Date
Feb 2009
Location
New Zealand
Posts
4,716
Rep Power
18

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

Java 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.
Last edited by pbrockway2; 11-25-2009 at 09:14 PM.  Reply With Quote

4. ## 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.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•