Skip to content

Fibonacci sequence – How to calculate the sum of the first 100 even-values Fibonacci numbers?

Fibonacci sequence is defined as a sequence of integers starting with 1 and 1, where each subsequent value is the sum of the preceding two I.e.

f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) where n>=2

My goal is to calculate the sum of the first 100 even-values Fibonacci numbers.

So far I’ve found this code which works perfectly to calculate the sum of even numbers to 4million , however I’m unable to find edit the code so that it stops at the sum of the 100th value, rather than reaching 4million.

public class Improvement {
  public static int Fibonacci(int j) {
      
      /**
       * 
       * Recursive took a long time so continued with iterative 
       * 
       * Complexity is n squared.. try to improve to just n
       * 
       */
            int tmp;
            int a = 2;
            int b = 1;
            int total = 0;

            do {
              if(isEven(a)) total +=a;
              tmp = a + b;
              b = a;
              a = tmp;      
            } while (a < j);

            return total;

          }

          private static boolean isEven(int a) {
            return (a & 1) == 0;
          }

          public static void main(String[] args) {
            // Notice there is no more loop here
            System.out.println(Fibonacci(4_000_000));
          }
        }

Just to show the console from @mr1554 code answer, the first 100 even values are shown and then the sum of all is 4850741640 as can be seen below:

Any help is appreciated, thanks!

mr1554 code answer

Answer

You said.

My goal is to calculate the sum of the first 100 even-values Fibonacci numbers.

That number gets very large very quickly. You need to:

  • use BigInteger
  • use the mod function to determine if even

For this I could have started from (1,1) but it’s only one term so …

BigInteger m = BigInteger.ZERO;
BigInteger n = BigInteger.ONE;

BigInteger sumOfEven= BigInteger.ZERO;
int count = 0;
BigInteger t;
while( count < 100) {
    t = n.add(m);
    // check if even
    if (t.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
        sumOfEven = sumOfEven.add(t);
        count++;
    }
    n = m;
    m = t;
}
System.out.println(sumOfEven);

Prints

290905784918002003245752779317049533129517076702883498623284700

If, on the other hand, from your comment.

My aim is to calculate the sum of the first 100 even numbers

Then you can do that like so

sumFirstNeven = (((2N + 2)N)/2 = (N+1)N

so (101)100 = 10100 and the complexity is O(1)