Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 11 of 11

Thread: find the sum of even number not exceed four million

  1. #1
    Junior Member
    Join Date
    May 2010
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default find the sum of even number not exceed four million

    Hai all

    i try to solve the this problem:
    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.


    and here is my code:

    public class Fibonacci {
     
    	public static void main(String[] args) {
    		int firstNum = 1;
    		int seqNum = 0;
    		int secNum = 1;
    		long length = 1000 * 4000;
    		int sumEvenNum = 0;
    		System.out.println("length " + length);
     
    		while (seqNum < length) {
    			seqNum += firstNum;
     
    			if (seqNum % 2 == 0) {
    				//System.out.println("seqNum: " + seqNum);
    				//System.out.println("sumEvenNum: " + sumEvenNum);
    				sumEvenNum += seqNum;
    				//System.out.println("even number: " + sumEvenNum);
    			}
     
    			firstNum = secNum;
    			secNum = seqNum;
    		}
     
    		System.out.println("sumEvenNum: " + sumEvenNum);
    	}
    }

    But the result is: 4613732, exceed four million, while the question require the value not exceed four million. can you help me to solve this problem??.


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: find the sum of even number not exceed four million

    You're condition is testing for until your computed result is greater than or equal to 4000000. So naturally the result you have will be the very first fibonacci number larger than 4 million.

    The easiest way to fix this is to keep a second variable which will keep track of the fibonacci number after the current one and stop when that number first gets larger than 4 million.

    also, if I'm reading the original problem statement right, you're adding up fibonacci numbers less than 4 million. There are quite a few and it's possible that their sum (even with only ever other one) could add up to be over 4 million.
    Last edited by helloworld922; January 5th, 2011 at 04:58 AM.

  3. #3
    Junior Member
    Join Date
    Dec 2010
    Posts
    3
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find the sum of even number not exceed four million

    i guess the answer is :

    public class Fibonacci {
     
        public static void main(String[] args) {
            int firstNum = 1;
            int seqNum = 0;
            int secNum = 1;
            long length = 1000 * 4000;
            int sumEvenNum = 0;
            System.out.println("length " + length);
     
            while (seqNum < length) {
                seqNum += firstNum;
     
                if (seqNum % 2 == 0) {
                    //System.out.println("seqNum: " + seqNum);
                    //System.out.println("sumEvenNum: " + sumEvenNum);
                    sumEvenNum += seqNum;
                    //System.out.println("even number: " + sumEvenNum);
                }
     
                if(sumEvenNum > length)
                    break;
     
                firstNum = secNum;
                secNum = seqNum;
            }
     
            System.out.println("sumEvenNum: " + seqNum);
        }
    }
    Last edited by aydea; January 23rd, 2011 at 08:13 AM.

  4. #4
    Forum VIP
    Join Date
    Jun 2011
    Posts
    317
    My Mood
    Bored
    Thanks
    47
    Thanked 89 Times in 74 Posts
    Blog Entries
    4

    Default Re: find the sum of even number not exceed four million

    This is the second Project Euler Challenge. Well I can tell you that the answer is indeed 4613732. You are asked to find the SUM of all the even valued numbers in the Fibonacci sequence below 4 million. That doesn't mean that the answer has to be below 4mil.

    Your first answer looks correct to me. Here is my answer which was also correct:

    int total = 0;
    int max = 4000000;
    int next = 1;
    int last = 1;
     
    while (next < max) {
    	int temp = next;
    	next = next + last;
    	last = temp;
     
            if (next % 2 == 0) {
    		total += next;
    	}
    }
     
    return total;

  5. #5
    Junior Member Mrc0d3r's Avatar
    Join Date
    Jun 2011
    Location
    TCP/IP Layer 3
    Posts
    25
    My Mood
    Bored
    Thanks
    0
    Thanked 6 Times in 5 Posts

    Default Re: find the sum of even number not exceed four million

    Quote Originally Posted by ChristopherLowe View Post

    int total = 0;
    int max = 4000000;
    int next = 1;
    int last = 1;
     
    while (next < max) {
    	int temp = next;
    	next = next + last;
    	last = temp;
     
            if (next % 2 == 0) {
    		total += next;
    	}
    }
     
    return total;
    That piece of code would certainly do the job, but it can be made more efficient by implementing recursion also you can fix the swap part to a 2 variable one. A little bit of threading should make it even more efficient.

  6. #6
    Forum VIP
    Join Date
    Jun 2011
    Posts
    317
    My Mood
    Bored
    Thanks
    47
    Thanked 89 Times in 74 Posts
    Blog Entries
    4

    Default Re: find the sum of even number not exceed four million

    Thanks Mrc0d3r,

    It takes about 0.0004 seconds to execute this code and it's a one of solution to a one of problem so I am not really interested in making it more efficient. But now that you mention it .. how would I 'fix the swap part to a 2 variable one'.

  7. #7
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: find the sum of even number not exceed four million

    Quote Originally Posted by Mrc0d3r View Post
    That piece of code would certainly do the job, but it can be made more efficient by implementing recursion also you can fix the swap part to a 2 variable one. A little bit of threading should make it even more efficient.
    Recursion definitely looks more elegant, but it is by no means more efficient. Fibonacci number computation is highly repetitive, so a dynamic programming solution (implemented iteratively) is the best way to compute Fibonacci numbers. Because computing Fibonacci numbers is very sequential (even with an iterative solution), I don't see any benefit of using a multi-threaded solution. If anything, the overhead from creating new threads, managing synchronization and data safety will far out-weigh any small, if any, benefit of a multi-threaded solution.

    Honestly, I don't see how an iterative method can perform a swap without at least 3 variables.

  8. #8
    Junior Member Mrc0d3r's Avatar
    Join Date
    Jun 2011
    Location
    TCP/IP Layer 3
    Posts
    25
    My Mood
    Bored
    Thanks
    0
    Thanked 6 Times in 5 Posts

    Default Re: find the sum of even number not exceed four million

    Quote Originally Posted by helloworld922 View Post
    Recursion definitely looks more elegant, but it is by no means more efficient. Fibonacci number computation is highly repetitive, so a dynamic programming solution (implemented iteratively) is the best way to compute Fibonacci numbers. Because computing Fibonacci numbers is very sequential (even with an iterative solution), I don't see any benefit of using a multi-threaded solution. If anything, the overhead from creating new threads, managing synchronization and data safety will far out-weigh any small, if any, benefit of a multi-threaded solution.
    Completely agree ! And regarding the multi-threading part, I thought we could split up the work to threads :S

    Quote Originally Posted by ChristopherLowe View Post
    how would I 'fix the swap part to a 2 variable one'.
    Quote Originally Posted by helloworld922 View Post
    Honestly, I don't see how an iterative method can perform a swap without at least 3 variables.
    This can do the job I suppose..
    next = next + last;
    last = next - last;
    Last edited by Mrc0d3r; June 28th, 2011 at 10:58 AM.

  9. #9
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: find the sum of even number not exceed four million

    Quote Originally Posted by Mrc0d3r View Post
    This can do the job I suppose..
    next = next + last;
    last = next - last;
    Ahh, that's a very interesting solution. There's not any significant performance boost (or ding), but it does look cool.

  10. #10
    Forum VIP
    Join Date
    Jun 2011
    Posts
    317
    My Mood
    Bored
    Thanks
    47
    Thanked 89 Times in 74 Posts
    Blog Entries
    4

    Default Re: find the sum of even number not exceed four million

    Quote Originally Posted by Mrc0d3r View Post
    This can do the job I suppose..
    next = next + last;
    last = next - last;
    Haha! That's brilliant! Great logic my friend.

  11. #11
    Junior Member Mrc0d3r's Avatar
    Join Date
    Jun 2011
    Location
    TCP/IP Layer 3
    Posts
    25
    My Mood
    Bored
    Thanks
    0
    Thanked 6 Times in 5 Posts

    Default Re: find the sum of even number not exceed four million

    Quote Originally Posted by helloworld922 View Post
    Ahh, that's a very interesting solution. There's not any significant performance boost (or ding), but it does look cool.
    Yeah right, a few micro-seconds difference.(and space isn't quite a big problem these days though !)

    Quote Originally Posted by ChristopherLowe View Post
    Haha! That's brilliant! Great logic my friend.
    Thanks !

Similar Threads

  1. Replies: 5
    Last Post: April 22nd, 2013, 07:27 AM
  2. Find total number less than average
    By maximus20895 in forum Collections and Generics
    Replies: 2
    Last Post: December 1st, 2010, 01:46 PM
  3. [ask] about sorting number.
    By bontet in forum What's Wrong With My Code?
    Replies: 1
    Last Post: October 30th, 2010, 02:07 PM
  4. letter to number
    By silverspoon34 in forum Java Theory & Questions
    Replies: 1
    Last Post: November 27th, 2009, 07:01 AM
  5. Help With Odd/Even number program
    By JonoScho in forum What's Wrong With My Code?
    Replies: 7
    Last Post: November 23rd, 2009, 10:53 AM