Fibonacci sequence is defined as F 0 = 0 , F 1 = 1 and for n ≥ 2 F n = F n − 1 + F n − 2
So the Fibonacci sequence is 0 , 1 , 1 , 2 , 3 , 5 , 8 , 1 3 , . . .
Find the sum of all the terms in the Fibonacci sequence which are less than 1 billion and are perfect squares .
Details and assumptions :-
Perfect square means square of an integer.
This problem is a part of the set Crazy Fibonacci
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.
I missed 1 and 1 as I carried the code from an earlier problem.
public class Fibo2 {
int Fn,Fn1,Fn2,tot;
int num,sqr;
Fibo2()
{
Fn=0;
Fn1=1;
Fn2=1;
tot=2;//Starting 1,1 are perfect squares ,I missed these as I carried used code for another problem
for(int i=0;i<100000000;i++)
{
if (Fn<1000000000)
{
Fn=Fn1+Fn2;
sqr=(int) Math.sqrt(Fn);
num=sqr*sqr;
if(Fn-num==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
Fibo2 f= new Fibo2();
}
}
Here's a C++ solution (kinda messy)
Actually, 1 and 144 are the ONLY fibonacci numbers which are perfect squares.
This is the source code in C to find such numbers.
#include <stdio.h>
#include <math.h>
int fib(int term)
{
if(term == 0)
return 0 ;
else if(term == 1)
return 1 ;
else
return(fib(term-1)+fib(term-2)) ;
}
int main(void)
{
int term = 0, number = -1, i ;
while(number < 1000000000) {
number = fib(term) ;
printf("%20d", number) ;
for(i = 0; i <= ceil(sqrt((double)1000000000)); i++)
if(number == i*i) {
printf("%6s", "CHECK") ;
break ;
}
printf("\n") ;
term++ ;
}
return 0 ;
}
The four numbers found are 0, 1, 1 and 144, giving the sum 0 + 1 + 1 + 144 = 146 .
Here is the VB.NET code:
Module Module1
Sub Main()
Dim previous As uInt64= 0
Dim current As uInt64= 1
Dim sum As uInt64= 0
While current < 1000000000
Console.WriteLine(current)
If perfect_squares(current) = True Then
sum = sum + current
End If
Dim temp As BigInteger
temp = current
current = current + previous
previous = temp
End While
Console.WriteLine()
Console.WriteLine(sum)
Console.ReadLine()
End Sub
Public Function perfect_squares(ByVal a As UInt64) As Boolean
Dim b As Double = Math.Sqrt(a)
Dim c As Double = Math.Ceiling(b)
Dim d As Int64 = Math.Floor(Math.Sqrt(a))
If (d = c) Then
Return True
Else
Return False
End If
End Function
End Module
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
Java solution -
Please note that I haven't added 0 and 1 to the perfect squares, so after getting the answer, add 2
public static void main(String args[]) throws java.lang.Exception{
int a = 1, b = 1;
double n = 0;
for(;a < 1000000000 && b < 1000000000;){
a += b;
b += a;
if(Math.round(Math.sqrt(a))==Math.sqrt(a)){
n += a;
}else if(Math.round(Math.sqrt(b))==Math.sqrt(b)){
n += b;
}
}
System.out.println(n);
}
Output is 144 but on considering 0 and 1, answer is 146.
But I think it should be given in the question whether to assume 0 as a perfect square or not.
It has been proven by Yann Bugeaud, Maurice Mignotte, and Samir Siksek that the only perfect powers in the Fibonacci sequence are 0 , 1 , 8 , 1 4 4 , thus the only perfect squares in the Fibonacci sequence are 0 , 1 , 1 4 4 . Since 1 appears twice (as F 1 and F 2 ), the sum of all perfect squares in the entire Fibonacci sequence (not only among those less than 1 billion!) is 1 4 4 + 1 + 1 + 0 = 1 4 6 .
My cute java code for the question :
class q3{ 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(perfect_sq(c)){
sum=sum+c;
}
a=b;
b=c;
}
System.out.print(sum+1);//missed the first "1" so adding 1 to
//final answer
}
public static boolean perfect_sq(long no){
double t=Math.sqrt(no);
int a=(int)t;
if(t-a==0)return true;
return false;
}
}
Python solution:
import math
count = 0
sumsqrt = 0
a = 0
b = 1
while count < 23:
print a
print b
if math.sqrt(a) % 1 == 0:
sumsqrt += a
if math.sqrt(b) % 1 == 0:
sumsqrt += b
a = a + b
b = a + b
count += 1
print "Sum : "
print sumsqrt
On a side note, here's a code for generating the first 2 n terms of the sequence :
count = 0
a = 0
b = 1
while count < n:
print a
print b
a = a + b
b = a + b
count += 1
#include<iostream.h>
#include<math.h>
int main()
{
long int a,b,f,h,sum;
int i;
a=0;
b=1;
sum=0;
for(i=2;f<1000000000;i++)
{
f=a+b;
b=a;
a=f;
h=floor(sqrt(f));
if(f==(h*h)){sum=sum+f;}
}
cout<<"The sum is: "<<sum;
return 0;
}
Java code:
public class brilliant{
public static void main(String args[]){
long previous=-1, current=1, next; //these are the -2th and the -1th term
long sum=0;
while(current<1000000000){
next = previous + current;
previous = current;
current = next;
if(Math.sqrt(current)-((int)(Math.sqrt(current)))==0) sum += current;
}
System.out.println(sum);
}
}
So answer is 1 + 1 + 1 4 4 = 1 4 6
Note: It is a fact that the only Fibonacci numbers that are squares are 0, 1 and 144. It had been a long-standing conjecture, that was proven in 1964 by John HE Cohn. You can read this proof here .
It is also true that the only Fibonacci numbers that are cubes are 0, 1 and 8. This requires significantly more work though, where the algebraic structure of Q [ 3 5 ] is studied.
Log in to reply
What does that mean? Why is the answer 146?
Log in to reply
The question has been edited to reflect "sum of all the terms", hence the answer is 0 + 1 + 1 + 1 4 4 = 1 4 6 .
Previously, it only asked for "sum of all Fibonacci numbers", which would have been 0 + 1 + 1 4 4 = 1 4 5 . Those who previously answered 145 have been marked correct.
Log in to reply
@Calvin Lin – Yeah, i got that from the report, so edited the wording... Sorry for the previous bug ;)
(C++. This uses the fact that F 1 0 0 > 1 0 9 and that F n = ⌊ 5 ϕ n + 2 1 ⌋ = ⌊ 2 5 2 ϕ n + 5 ⌋ ) (I know I could've used recursion, but I'm just sharing a different approach)
for (n=0;n<=100;n++)
for (k=0;k<=100000;k++)
if (int(floor((2*pow(((1+sqrt(5))/2),n)+sqrt(5))/(2*sqrt(5))))==k*k) {
sum=sum+int(floor((2*pow(((1+sqrt(5))/2),n)+sqrt(5))/(2*sqrt(5))));
cout << int(floor((2*pow(((1+sqrt(5))/2),n)+sqrt(5))/(2*sqrt(5)))) << " " << sum << endl; }
return 0;
Log in to reply
Instead of using two nested for loops, which is very slow, you could have only used one for loop. Instead just take the square root of the Fibonacci number in question and test whether it is an integer or not.
Log in to reply
You're right, when I use
for (n=0;n<=100;n++)
if (floor(sqrt(F(n)))==sqrt(F(n))) {
sum=sum+F(n);
cout << F(n) << " " << sum << endl; }
return 0;
instead of
for (n=0;n<=100;n++)
for (k=0;k<=100000;k++)
if (F(n)==k*k) {
sum=sum+F(n);
cout << F(n) << " " << sum << endl; }
return 0;
the running time is 0 . 0 5 1 s instead of 3 6 . 0 5 6 s (I've made a function F ( n ) that uses the previous formula). The former code uses the fact that a is an integer if and only if ⌊ a ⌋ = a .
Problem Loading...
Note Loading...
Set Loading...
PARI/GP code: