Comp Sci Java Fibonacci Sequence: Finding the Sum of Even-Valued Terms Under 4 Million

  • Thread starter Thread starter Robben
  • Start date Start date
  • Tags Tags
    Java Sequence
AI Thread Summary
The discussion centers on solving the problem of finding the sum of even-valued Fibonacci terms that do not exceed four million. Participants identify that the original code produces negative results due to exceeding integer limits, suggesting the use of long data types for variables. A critical misunderstanding is noted regarding the problem statement, clarifying that it asks for terms not exceeding four million rather than the four millionth term. Additionally, it is pointed out that every third Fibonacci number is even, which can simplify calculations. The conversation concludes with suggestions for alternative coding approaches to efficiently calculate Fibonacci numbers.
Robben
Messages
166
Reaction score
2

Homework Statement



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.

Homework Equations



None

The Attempt at a Solution



I am not sure what is wrong with my code? The code produces a negative number when I type in 4000000 into the fib method parameter.

Java:
public static void fib(int k) {
    
    int result = 0;
    int[] array = new int[k];
    array[0] = 1;
    array[1] = 2;
    
    for (int i = 2; i < k; i++) {
        array[i] = array[i - 2] + array[i - 1];      
    }
    
    for (int even: array) {
         
         if (even % 2 == 0) {
             result += even;
         }
    }        
    System.out.println(result);
}
 
Last edited:
Physics news on Phys.org
Does it work for smaller numbers? If so then your algorithm is correct but you are exceeding the limit of integers. Try long instead of int for all variables.
 
scientific601 said:
Does it work for smaller numbers? If so then your algorithm is correct but you are exceeding the limit of integers. Try long instead of int for all variables.

It does work for smaller numbers but for large numbers it doesn't. I tried with long and double and it still produces different negative numbers?
 
You sure? If result is also long... (I said all variables).

Also I wonder if "find the sum of the even-valued terms" meant you are to find some shortcut formula.
 
scientific601 said:
You sure? If result is also long... (I said all variables).

Also I wonder if "find the sum of the even-valued terms" meant you are to find some shortcut formula.

Yup, I changed all the int to long and the method produced a different negative number.
 
It may be in the System.out.println statement. Try using formatting and use ll for "long long" sized integers.
Something like
System.out.printf("%ll", result)
 
Robben said:
The code produces a negative number when I type in 4000000 into the fib method parameter.

You may want to re-read the problem statement:)). There is a VERY significant difference between the 4 millionth term in the Fibonacci Sequence and the highest term that does not exceed 4 million: so significant that using long or double can't possibly save you in the case of the former. Try adding a println to print the last term (array[k-1]) to see how quickly the series grows... compare for example k=10 ,20,30,40...can you imagine how large the 4 millionth term in the sequence must be?
 
  • Like
Likes Robben
You are correct. The OP and I did not read the problem statement carefully.
The problem statement does not ask to go to the 4 millionth term but the term that does not exceed 4 million.
So the loop limit should check the value of
Code:
array[i] = array[i - 2] + array[i - 1];
instead of the index.
 
  • Like
Likes Robben
Fibonacci numbers, fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3, ...
max values for 32 bit signed, unsigned, and 64 bit signed, unsigned integers:

fib(46) = 1836311903 = hex 6D73E55F
fib(47) = 2971215073 = hex B11924E1

fib(92) = 7540113804746346429 = hex 68A3DD8E61ECCFBD
fib(93) = 12200160415121876738 = hex A94FAD42221F2702

every 3rd fibonacci number is even (since pattern is even+odd, odd+even, odd+odd)
fib(0) = 0
fib(3) = 2
fib(6) = 8
fib(9) = 34
fib(12) = 144
fib(15) = 610
fib(18) = 2584
 
Last edited:
  • Like
Likes Robben
  • #10
That's a good observation! Using that sequence according to other sources we only have to go as high as about fib(33) which is well below our integer limits. Anything beyond that and the terms are above 4,000,000 anyway.
 
  • #11
On a side note, Fibonacci for negative numbers can be determined by noting:

fib(i-2) = fib(i) - fib(i-1)

fib(6) = 8
fib(5) = 5
fib(4) = 3
fib(3) = 2
fib(2) = 1
fib(1) = 1
fib(0) = 0
fib(-1) = 1
fib(-2) = -1
fib(-3) = 2
fib(-4) = -3
fib(-5) = 5
fib(-6) = -8

You can also calculate fibonacci sequence using only two local variables:

Code:
unsigned int fib(unsigned int n)
{
unsigned int f0, f1;
    f0 = n & 1;         /* if n even, f0=0=fib(0), f1=1=fib(-1) */
    f1 = 1 - f0;        /* else       f1=0=fib(0), f0=1=fib(-1) */
    switch(n%2){
        do{
            f1 += f0;
          case 1:
            f0 += f1;
          case 0:
            continue;
        }while(0 <= (int)(n -= 2));
    }
    return f0;
}
 
  • #12
scientific601 said:
Does it work for smaller numbers? If so then your algorithm is correct but you are exceeding the limit of integers. Try long instead of int for all variables.
I'm more familiar with the sizes of types for C and C++ than with Java, but it seems likely to me that a long and an int are the same size (i.e., 32 bits).
 

Similar threads

Replies
4
Views
5K
Replies
7
Views
2K
Replies
2
Views
1K
Replies
3
Views
1K
Replies
1
Views
2K
Replies
5
Views
2K
Replies
1
Views
2K
Back
Top