11 modular 100 Fibonacci? Sounds Crazy!

Computer Science Level 3

Find the sum of all the Fibonacci numbers less than 1 billion which have their last 2 digits same in decimal representation.

Details and assumptions :

Fibonacci sequence is defined as F 0 = 0 , F 1 = 1 F_0=0,F_1=1 and for n ≥ 2 n\geq 2 , F n = F n − 1 + F n − 2 F_n=F_{n-1}+F_{n-2} . Thus, the Fibonacci sequence is 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , … 0,1,1,2,3,5,8,13,\ldots .

  • 12344 has the last 2 digits same (each being 4), and 12345 does not have it's last 2 digits to be the same.
This problem is a part of the set Crazy Fibonacci


The answer is 804079219.

Aditya Raut by Aditya Raut , 23, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

8 solutions

Nafees Zakir
Sep 25, 2014

Wrote this Code on Python 2.7 and Save it as ModFib.py and Ran it 

1
2
3
4
5
6
7
 
fibo1, fibo2 = 0, 1
sum = 0
while fibo1 <= 1000000000:
    if (fibo1 % 100) % 11 == 0:
        sum += fibo1
    fibo1, fibo2 = fibo2, fibo1 + fibo2  #Formula for Fibonacci Series
print sum

So it Prints on Screen the value of sum = 804079219

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Here's a C++ solution .

Prasun Biswas - 5 years, 10 months ago
Nitish Joshi
Feb 7, 2016

Here is a solution in turbo C++ 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include<iostream.h>
#include<conio.h>
void main()
{
 clrscr();
 long long sum=0;
 long long a,b,p,fib[45];
 fib[0]=0;
 fib[1]=1;
 for(int i=2;i<45;i++)
 fib[i]=fib[i-1]+fib[i-2];
 for(int j=7;j<45;j++)
 {
  a=fib[j]%10;
  p=fib[j];
  p=p-a;
  b=p/10;
  if((b%10)==a)
  { sum=sum+fib[j];
  }
 }
 cout<<sum;
  getch();
}

Note:

1.I first found out that fib[45]>1,000,000,000

2.The first seven fibonacci numbers are single digit numbers.

0 Helpful 0 Interesting 0 Brilliant 0 Confused
David Holcer
Apr 4, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
 
from math import *
fib=[0,1]
n=10**9
while fib[-1]<n:
    test=fib[-1]+fib[-2]
    if test<n:
        fib.append(test)
    else:
        break
summ=0
for i in fib:
    try:
        if str(i)[-1]==str(i)[-2]:
            summ+=i
    except(IndexError):
        pass
print summ

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Kartikay Shandil
Oct 11, 2014

My cute solution in java to the question : class q5{ 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(check(c)){
            sum=sum+c;
        }
        a=b;
        b=c;
    }
    System.out.print(sum);
}

public static boolean check(long no){
    if(no<10)return false;
   long a=no%10;
    no=no/10;
    if(a==(no%10))return true;
    return false;
}

}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

Java Solution: public class Fibo3 { 

int Fn,Fn1,Fn2;
int dig10,dig100;
long tot;
Fibo3()
{
Fn=0;
Fn1=1;
Fn2=1;
tot=0;
for(int i=0;i<100000000;i++)
{
 if (Fn<1000000000)   
 {    

    Fn=Fn1+Fn2;
    dig100=Fn%100;
    dig10=dig100%10;
    dig100-=dig10;
    dig100=dig100/10;
    if(dig100-dig10==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
    Fibo3 f= new Fibo3();
}

}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

run: 0 0 0 0 0 0 0 55 55 199 432 809 809 809 809 809 809 809 809 18520 18520 18520 18520 18520 18520 336331 336331 336331 336331 336331 336331 336331 336331 336331 336331 336331 336331 102670486 102670486 102670486 102670486 804079219 804079219

Vijesh Balasubramanian - 6 years, 8 months ago
Kenny Lau
Aug 29, 2014

Here is the java solution: 

public class brilliant{
    public static void main(String args[]){
        long previous=1, current=1, next;
        long sum=0;
        while(current<1000000000){
            next = previous + current;
            previous = current;
            current = next;
            if((current%100)%11==0) sum += current;
        }
        System.out.println(sum);
    }
}
0 Helpful 0 Interesting 0 Brilliant 0 Confused
Edward Jiang
Aug 28, 2014

PARI/GP code: 

a(n)=m=Vec(Str(n));m[#m]==m[#m-1]
answer=0;for(i=7,44,if(a(fibonacci(i)),answer=answer+fibonacci(i)));return(answer)
0 Helpful 0 Interesting 0 Brilliant 0 Confused
Aditya Raut
Aug 28, 2014

Python

This is the solution using Python img img

As the pic shows, sum(num) \textbf{sum(num)} , i.e. the answer is 804079219 \boxed{804079219}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...