# Fibonacci Sequence 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, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

wrote this code, but as always... the code is never returning an answer ...

donno why though, any help would be appreciated.

Originally posted by Sam Benry:

...the code is never returning an answer...

You can add some code to the end of your while loop to display progress...

This will show you that your code runs

**very**slowly, so waiting for it to reach 4000000 will require a bit of patience.

To test the logic during development, you might want to lower your end point. For example, enter a modest 10 rather than 4000000.

[ March 22, 2008: Message edited by: marc weber ]

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

[ March 22, 2008: Message edited by: marc weber ]

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

Originally posted by marc weber:

Your cumulative sum probably needs to be a BigInteger, because this gets big fast...

Whoops, I need to take that back.

I based this on output from running a modified version of your code, but after thinking about it, that's just not right. Adding even numbers in the sequence that

*don't exceed*4 million is one thing. But adding even numbers from the first 4 million in the sequence is quite another.

If I'm reading the problem correctly, your code should run in the blink of an eye.

[ March 22, 2008: Message edited by: marc weber ]

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

The sum of all Fibonacci numbers in that series F1 + F2 + F3 . . . F

*n*= F(

*n+2*) - 1.

Fibonacci numbers in that series run odd-odd-even-odd-odd-even. You should be able to prove that easily from simple addition.

Suggest you use a long rather than a BigInteger; you won't run out of space before 4000000. You can probably actually get away with an int. You can get the first 46 members of that Fibonacci series into an int without overflow, and the first 92 into a long. At least that is what happened when I tried it a few months ago as far as I remember.

You can work out the

*n*th member of the common Fibonacci series by calculating

**round(phi^n/sqrt5)**where phi is the Golden ratio (1.618... = (1+sqrt5)/2) and sqrt5 is the square root of 5 and round means round to the nearest whole number.

A quick way to work out whether a number is odd or even is to use the bitwise and operator: if(x & 1 == 0). . . or if(x & 1 != 0). . .

You are comparing the number of iterations

*i*with the last term of 4000000, which means you will iterate approx 4000000 times, rather than finding the last Fibonacci number before 4000000. You will have your app running for years like that!

You can Google for Fibonacci algorithms. There is one in Anne Kaldewaij, Programming : the derivation of algorithms (Prentice Hall International series in computer series) Hemel Hempstead : Prentice Hall International, 1990, ISBN 0132041081, I think page 98, which runs in logarithmic time, but that is really complicated.

You will also find the standard recursive algorithmBut this is given as an example of exponential complexity; if you count the number of iterations it turns out to be 2F

*n*- 1, and its complexity is O(1.618^

*n*). Ouch. It can take ages to run. But since 4000000 is above the 31st Fibonacci number in that series and below the 32nd, even that is not too bad.

It is quite easy to write a Fibonacci algorithm which runs in linear time. You have to pass the current Fibonacci number and the previous one and add them. You end up with a method with this sort of signature: public long fibonacci(long current, long previous, int count).

Write that, get it running, test it. Marc Weber is right; it will produce a result in a few milliseconds. Then create a sum variable, and put a statement in the fibonacci method to add to sum if the value is an even number.

Easy-peasy. And did you get the prime numbers thing to work?

[ March 23, 2008: Message edited by: Garrett Rowe ]

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Yes, there is a pattern to even and odd numbers.

As written, I think that code will produce erroneous results for any value of n, such that:

Try it with just n == 11, and check the result by hand. The fix for that seems to be:

Originally posted by marc weber:

...If I'm reading the problem correctly, your code should run in the blink of an eye...

And won't need any BigIntegers, by the way.

*~Joe Strummer*

sscce.org

That is a linear complexity non-recursive Fibonacci algorithm. Put in a for loop rather like this:Originally posted by Sam Benry:

This is resulting in negative though it is BigInteger

for(int i = 0; i < 50; i++)

System.out.printf("The %dth Fibonacci number is %d.%n" i, fib1(i));

and you should get

The 0th Fibonacci number is 0.

The 1th Fibonacci number is 1.

The 2th Fibonacci number is 1.

The 3th Fibonacci number is 2.

The 4th Fibonacci number is 3.

The 5th Fibonacci number is 5

etc etc.

Try adding

**&& fibA < 4000000**to the middle part of the heading of your for loop, then it ought to stop at 4000000.

That is the exponential complexity Fibonacci recursive algorithm; it is virtually identical to what I quoted earlier. In all the computer science books as an example of an inefficient use of recursion. Don't use it.Originally posted by Sam Benry:

and I found this code

which seems pretty simple but I cant figure out how to display the numbers, for example if I want to display the first 10 values in the sequence, how can I do that using this code?

Your problem, which people have already told you about, is the middle part of your for-loop. YOu know I said to add "fibA < 4000000"? Well delete the bit about k < n. That means you are not going on until the Fibonacci number reaches 4000000, ie about 31-32 passes. What you are actually doing is organising 4000000 passes which will give you a result about 1.627477199E835950. If you are lucky your JVM will crash before you get to 8 million digits.

To display the numbers from this 2nd algorithm, use exactly the same for-loop as in my post of 10 minutes ago. Remember the 0th number should be 0 and the 1th(!) and 2th(!) should both read 1.

And Marc Weber is correct. You can do everything with int arithmetic and not bother with BigIntegers.

**not**the sum of the even Fib numbers from fib(1) to fib(4000000). As Campbell and marc both tried to point out, the fib numbers start exceeding 4000000 at about fib(31). You were looping about 3,999,969 more times than you needed to.

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions