Results 1 to 4 of 4
  1. #1
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

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

  2. #2
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    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.

  3. #3
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    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.

  4. #4
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    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

  1. help with fibonacci problem
    By thekrazykid in forum New To Java
    Replies: 4
    Last Post: 12-12-2008, 10:41 PM
  2. (Help) Quotient summation with prime numbers
    By SapphireSpark in forum New To Java
    Replies: 27
    Last Post: 10-24-2008, 08:28 AM
  3. (Help) Fraction Summation and Exponents
    By SapphireSpark in forum New To Java
    Replies: 19
    Last Post: 10-09-2008, 04:01 AM
  4. Printing Fibonacci Numbers
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-09-2008, 06:43 PM
  5. Fibonacci Algorithm
    By susan in forum New To Java
    Replies: 1
    Last Post: 08-07-2007, 04:25 AM

Posting Permissions

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