Results 1 to 4 of 4
Thread: Fibonacci summation problem
 11252009, 06:15 PM #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 evenvalued 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 evenvalued 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); } } }
Liberty has never come from the government.
Liberty has always come from the subjects of government.
The history of liberty is the history of resistance.
The history of liberty is a history of the limitation of governmental power, not the increase of it.
 11252009, 06:28 PM #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?
Liberty has never come from the government.
Liberty has always come from the subjects of government.
The history of liberty is the history of resistance.
The history of liberty is a history of the limitation of governmental power, not the increase of it.
 11252009, 10:06 PM #3Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,585
 Rep Power
 12
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 } }
Last edited by pbrockway2; 11252009 at 10:14 PM.
 12012009, 07:28 PM #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.
Liberty has never come from the government.
Liberty has always come from the subjects of government.
The history of liberty is the history of resistance.
The history of liberty is a history of the limitation of governmental power, not the increase of it.
Similar Threads

help with fibonacci problem
By thekrazykid in forum New To JavaReplies: 4Last Post: 12122008, 11:41 PM 
(Help) Quotient summation with prime numbers
By SapphireSpark in forum New To JavaReplies: 27Last Post: 10242008, 09:28 AM 
(Help) Fraction Summation and Exponents
By SapphireSpark in forum New To JavaReplies: 19Last Post: 10092008, 05:01 AM 
Printing Fibonacci Numbers
By Java Tip in forum java.langReplies: 0Last Post: 04092008, 07:43 PM 
Fibonacci Algorithm
By susan in forum New To JavaReplies: 1Last Post: 08072007, 05:25 AM
Bookmarks