There is a certain theorem (I forgot what the name is) saying that $F_m | F_n$ if and only if $m | n$ .

$3$ is the fourth Fibonacci number or $F_4$ .

Therefore $3$ divides all Fibonacci numbers in the form $F_{4k}$ where $k$ is a positive integer.

$F_{44}$ is the highest Fibonacci number less than $1$ billion.

Therefore the answer is $F_4 + F_8 + F_{12} + ... + F_{44}$ which is equal to $\boxed{821223648}$

There isn't a need to write a C++ code to solve this problem.

First, we consider the Fibonacci sequence modulo 3. It is (starting with 0)

$0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, \ldots$

where the pattern repeats every 8 terms. Hence, we want the sum of every 4th term, till the fibonacci sequence hits 1 billion.

We can apply the Fast Fibonacci Transform, to find every 4th term. It starts off as

$0, 3, 21, 144, 987, 6765, 46368, 317811, 2178309,\\ 14930352, 102334155, 701408733, \ldots$

Alternatively, if $G_k$ is the above sequence, you can prove that $G_n = 7 G_{n-1} - G_{n-2}$ , which is an easy way to obtain the next term. (Why does this work? Can you generalize? Hint: $\phi^6 - 7 \phi^3 + 1 = 0$ .)

This gives us the sum of 821223648.

I solved it using C++. Here is my code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
using namespace std;
int main()
{
long int prevf,prevprevf,f,sum;
int i;
prevf=0;
prevprevf=1;
sum=0;
for(i=2;f<1000000000;i++)
{
f=prevf+prevprevf;
prevprevf=prevf;
prevf=f;
if(f%3==0){sum=sum+f;}
else{continue;}
}
cout<<"The sum is: "<<sum;
return 0;
} 

First, consider the Fibonacci sequence modulo $3$ : $0,1,1,2,0,2,2,1,0,1,\dots$ . This shows that the sum is simply $F_0+F_4+\dots+F_{44}$ , which is a geometric series by Binet's formula.

Note: this is a mathematician's solution, not a computer scientist's. This can be solved using Wolfram Alpha purely

Easy one :)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <iostream>
using namespace std;
int main()
{
int Fn_2 = 0;
int Fn_1 = 1;
int Fn,som;
som = 0;
i = 2;
while(Fn < 1000000000){
Fn = Fn_2 + Fn_1;
if(Fn % 3 == 0){
 som += Fn;
}
Fn_2 = Fn_1;
Fn_1 = Fn;
}
cout<<som<<endl;
}

Precious, brute force and easy. #include <stdio.h> #include <string.h>

main(){
    int i = 0, j = 1, k = 0, sum =0;
    for (k=0; k<=1000000000; k=i+j){
        i = j;
        j = k;
        if(k%3==0)
            sum = sum + k;
    }
    printf("%d\n", sum);

}

I solved this using python. here is my code img

So the answer is $\boxed{821223648}$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import math
def fib(n):
    return math.floor((1/math.sqrt(5)*((1+math.sqrt(5))**n - (1-math.sqrt(5))**n)/2**n)) #Binet's formula for nth fibonacci number
i=1
s=0
while fib(i)<=10**9:
    if fib(i)%3 == 0:
        s += fib(i)
    i += 1
print(s)

$i=0$ has been excluded because $F_0 = 0$ even being divisible by $3$ doesn't alter the sum since adding $0$ to number doesn't change its value.

long l = 1000000000; long[] ls = new long[60]; Arrays.fill(ls, -1); ls[0] = 0; ls[1] = 1; for (int i = 2; i < ls.length; i++) { ls[i] = ls[i - 1] + ls[i - 2]; } BigInteger bgInt = BigInteger.ZERO; for (long m : ls) { if (m < l && m % 3 == 0) { bgInt = bgInt.add(BigInteger.valueOf(m)); } }

    System.out.println(bgInt);

This is a C code.

#include   <stdio.h>

int fibonacci(int term)
{
    if(term == 0)
        return 0 ;
    else if(term == 1)
        return 1 ;
    else
        return(fibonacci(term-1)+fibonacci(term-2)) ;
}

int main(void)
{
    int number = -1, term = 0, sum = 0 ;

    while(number < 1000000000)   {
        number = fibonacci(term) ;
        if(number % 3 == 0)
            sum += number ;
        term++ ;
    }
    printf("%d", sum) ;
    return 0 ;
}

To see which terms satisfy the conditions, add the line of code

printf("%d, " number) ;

within the if condition.

Brute force algorithm for c++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

main() {
    int Fprev = 0;
    int Fcurr = 1;
    int sum = 0;
    while(true) {
        Fcurr = Fcurr + Fprev;
        Fprev = Fcurr - Fprev;
        if(Fcurr >= 1000000000) break;
        if(Fcurr % 3 == 0) sum += Fcurr;
    }
    cout << sum << endl;
}

My cute solution for the question :

class q4{ public static void main(String as[]){ int a=0; int b=1; int c=0; long sum=0;

    for(;c<1000000000;){
        c=a+b;
        if(c%3==0){
            sum=sum+c;
        }
        a=b;
        b=c;
    }
    System.out.print(sum);
}

}

I wrote a small Java program for the same: public class Fibo {

int Fn,Fn1,Fn2,tot;

Fibo()
{
Fn=0;
Fn1=1;
Fn2=1;
tot=0;
for(int i=0;i<100000000;i++)
{
 if (Fn<1000000000)   
 {    


    Fn=Fn1+Fn2;
    if(Fn%3==0)
    {
        tot+=Fn;
    } 
    System.out.println(""+tot);

 Fn2=Fn1;
 Fn1=Fn;
 }
} 
}

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    // TODO code application logic here
    Fibo f= new Fibo();
}

}

My C code for the problem

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <stdio.h>
#define limit 1000000000
// Fibonacci Numbers 0 1 1 2 3 5 8 13 21 34 55...
// sum of the Fibonacci numbers less than the limit and are divisible by 3
int main()
{
        long long int i=0,j=1,num=0,sum=0;
        while(num<limit)
        {
                num = i +j;
                i = j;
                j = num;
                if(num%3==0)
                        sum +=num;
        }
        printf("The Sum: %lld", sum);
        return 0;
}

public class fib { static double sum; public static void main(String[] args) {
sum = 0; fib(0,1); System.out.printf("dexp: %.0f\n", sum); }
public static void fib(double i, double j) {
if(i % 3 == 0)
{
sum+=i; }
if(i > 1000000000) {
return; }
fib(j, i+j); }
}