What is Sum of Even Terms In Fibonacci (<4million)? [Large Value Datatype Confusion]

By starting with 1 and 2, the first 10 terms of Fibonacci Series 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 4 million.

Now, I got the idea for how to do this. But I'm confused about the data types to hold such big data. I'm getting weird results with int. :(

MORE: Its Project Euler 2nd question. But I can't get it. I get crazy values as answer. Can someone please post the ideal program?

EDIT: Here's what I wrote for just printing Fibonacci to screen. Bare Basic. My variable goes crazy even when I give 100 for the limit. Is my code wrong?

// Simple Program to print Fibonacci series in Console
#include <stdio.h>
int main() {
    int x=1,y=2,sum=0,limit=0,i=0,temp=0;
    printf("Enter Limit:");
    scanf("%d",&limit);

    if(limit==1)
        printf("%d",x);
    else if(limit>1) {
        printf("%d %d",x,y);
        if (limit>2) {
            while (i<limit-2) {
                temp=y;
                s开发者_StackOverflow社区um=x+y;
                x=temp;
                y=sum;
                printf(" %d",sum);
                i++;
            }
        }
    }      

    printf("\n");
    return 0;
}

SOLVED: Actually, I managed to get the solution myself. Here's my program. It works.

#include <stdio.h>
int main() {
    int x=1,y=2,sum,limit;     //Here value of first 2 terms have been initialized as 1 and 2
    int evensum=2;             //Since in calculation, we omit 2 which is an even number
    printf("Enter Limit: ");   //Enter limit as 4000000 (4million) to get desired result
    scanf("%d",&limit);
    while( (x+y)<limit ) {
        sum=x+y;
        x=y;
        y=sum;
        if (sum%2==0)
            evensum+=sum;
    }
    printf("%d \n",evensum);
    return 0;
}

Since you only want up to four million, it's likely that int is not your problem.

It's quite possible that your program is buggy and that the data storage is just fine, so you should test your program on smaller values. For example, it's clear that the sum of the first three even terms is 44 (hint: every third term is even) so if you run your program with a cap of 50, then you should instantly get 44 back. Keep running small test cases to get confidence in the larger ones.

For security, use the 'long' data type; the C standard requires that to hold at least 4 billion, but on most machines, 'int' will also hold 4 billion.

enum { MAX_VALUE = 4000000 };
int sum  = 0;
int f_n0 = 0;
int f_n1 = 1;
int f_n2;

while ((f_n2 = f_n0 + f_n1) < MAX_VALUE)
{
    if (f_n2 % 2 == 0)
        sum += f_n2;
    f_n0 = f_n1;
    f_n1 = f_n2;
}
printf("%d\n", sum);

I am not a programmer, but here's an adaptation to Leffler's code without the IF-criterion. It should work for MAX_VALUES above 2 (given there are no mistakes in programming syntax), based on a pattern I found in the even-only fibonacci series: 0,2,8,34,144,610,2584... so interestingly: f_n2 = 4*f_n1 + f_n0. This also means this program only needs 1/3rd of the calculations, since it doesn't even consider/calculate the odd fibonacci numbers.

enum { MAX_VALUE = 4000000 };
int sum  = 2;
int f_n0 = 0;
int f_n1 = 2;
int f_n2 = 8;

while (f_n2 < MAX_VALUE)
{
    sum += f_n2;
    f_n0 = f_n1;
    f_n1 = f_n2;
    f_n2 = 4*f_n1 + f_n0;
}
printf("%d\n", sum);

Try changing this:

while (i<limit-2)

to this:

while (y<limit)

As written, your program is cycling until it gets to the 4 millionth Fibonacci number (i.e. when i gets to 4 million, though overflow obviously happens first). The loop should check to see when y (the larger Fibonacci number) becomes greater than 4 million.

Guys, I got the answer. I confirmed the result and int can handle it. Here's my program:

#include <stdio.h>
int main() {
    int x=1,y=2,sum,limit;     //Here value of first 2 terms have been initialized as 1 and 2
    int evensum=2;             //Since in calculation, we omit 2 which is an even number
    printf("Enter Limit: ");   //Enter limit as 4000000 (4million) to get desired result
    scanf("%d",&limit);
    while( (x+y)<limit ) {
        sum=x+y;
        x=y;
        y=sum;
        if (sum%2==0)
            evensum+=sum;
    }
    printf("%d \n",evensum);
    return 0;
}

Thx for all the replies and help. "Thinking on my feet" to the rescue :)

An amusing solution is to use the closed form for Fibonacci sequences and the closed form for geometric progressions. The end solution looks like this:

  sum = ( (1-pow(phi_cb, N+1)) / (1-phi_cb) - (1-pow(onephi_cb,N+1)) / (1-onephi_cb)) / sqrt(5);

where

  double phi       = 0.5 + 0.5 * sqrt(5);
  double phi_cb    = pow(phi, 3.0);
  double onephi_cb = pow(1.0 - phi, 3.0);
  unsigned N = floor( log(4000000.0 * sqrt(5) + 0.5) / log(phi) );
  N = N / 3;

with all the caveats regarding double to int-type conversions of course.

int is big enough for values in the millions on almost every modern system, but you can use long if you are worried about it. If that still gives you weird results, then the problem is with your algorithm.

Use BigInt.

Then again, unsigned int stores values up to over 4 billion, so you shouldn't be having any problems even with "sum of all fibonacci numbers up to 4 million" (which, obviously, has to be less than 8 mil)?

Your program prints F_1 + ..+ F_limit and not F_1 + ... F_n with F_n < limit as you described.

Check the Wikipedia article on Fibonacci Numbers and Sloane A000045: Fibonacci numbers grows exponentially. Checking this table F_48 = 4807526976 which exceeds int. F_100 is 354224848179261915075 which surely overflows even int64_t (your stack doesn't, though).

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.

   int main()

  {  
     long first = 1, second = 2, next, c;

     int sum=0;
     for ( c = 1 ; c <100000000; c++ )

  {

     next = first + second;
     if(next>=4000000)
     {
     next=  next-second;
     break;
     }

     first = second;
     second = next;    

  if(next%2==0){

     sum=sum+next;
  }

 }

  printf("the sum of even valued  term is %d\n",sum+2);


 }  

Here's my program:

#include <iostream>

long int even_sum_fibonacci(int n){
    int i = 8;
    int previous_i = 2;
    int next_i = 0;
    long int sum = previous_i + i;;
    while(n>next_i){
        next_i = i*4 + previous_i;
        previous_i = i;
        i = next_i;
        sum = sum + i;
    }
    return sum - next_i; //now next_i and i are both the bigger number which
                         //exceeds 4 million, but we counted next_i into sum
                         //so we'll need to substract it from sum
}



int main()
{
   std::cout << even_sum_fibonacci(4000000) << std::endl; 

   return 0;
}

Because if you look at the fibonacci series (at the first few even numbers) 2 8 34 144 610 2584 ... you'll see that it matches the pattern that next_number = current_number * 4 + previous_number.

This is one of solutions. So the result is 4613732

You can try the below code.

public static void SumOfEvenFibonacciNumbers()
{
    int range = 4000000;
    long sum = 0;
    long current = 1;
    long prev = 0;
    long evenValueSum= 0;
    while (evenValueSum< range)
    {
        sum = prev + current;
        prev = current;
        current = sum;
        if (sum % 2 == 0 )
        {
            evenValueSum = evenValueSum+ sum;
        }
    }

    Console.WriteLine(evenValueSum);
}

You can use the above code.

import numpy as np
M = [[0,1],[1,1]]
F = [[0],[1]]
s = 0
while(F[1][0] < 4000000):
 F = np.matmul(M, F)
 if not F[0][0]%2:
   s+=F[0][0]

print(s)

We can do better than this in O(log n) time. Moreover, a 2 × 2 matrix and a two dimensional vector can be multiplied again in O(1) time. Therefore it suffices to compute Mⁿ. The following recursive algorithm computes Mⁿ

1. If n = 0, return I₂
2. If n = 1, return M.
3. If n = 2m.
4. Recursively compute N = M^m, and set P = N².
5. If n = 2m+1, set P = PM.
6. Return P. We have T(n) = T(n/2) + O(1), and by master's theorem T(n) = O(log n)

You can also use recurrence for Even Fibonacci sequence is: EFn = 4EFn-1 + EFn-2 with seed values EF0 = 0 and EF1 = 2.

SIMPLE SOLUTION WOULD BE:-

#include <iostream>
using namespace std;

int main(int argc, char** argv) {   
int n1=1;
int n2=2;
int num=0,sum;

for (int i=1;i,n1<4000000;i++)
{

    cout<<"    "<<n1;
    num=n1+n2;
    if(!(n1%2))
    {
        sum+=n1;
    }
    n1=n2;
    n2=num;     
}
cout<<"\n Sum of even term is = "<<sum;
return 0;
}

Here's my offer, written in Java. I had been using a for loop whose exit value was 4000000 but realized early on there was a serious overflow for the sum of the numbers. Realizing the Fibonacci Number has to be less than 4 million (and not the sum), I changed to a while loop and got it:

class Main {
  public static void main(String[] args) {
    int counter = 0; 
    int fibonacciSum = 0, fibonacciNum = 0;
    int previous = 1, secondPrevious = 0; 
    fibonacciNum = previous + secondPrevious;
    
    while (fibonacciNum <= 4000000){
        if (fibonacciNum % 2 == 0 ){
            counter++; 
            fibonacciSum += fibonacciNum;
            secondPrevious = previous;
            previous = fibonacciNum; 
        }//ends if statement
        else {
            secondPrevious = previous;
            previous = fibonacciNum;    
        }//ends else statement 
        
        fibonacciNum = previous + secondPrevious;//updates number
        
    }//ends loop
         
    System.out.println("\n\n\n" + fibonacciSum);
 }//ends main method
}//ends Main