Square Fibonacci ? Sounds Crazy !

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}

So the Fibonacci sequence is 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , . . . 0,1,1,2,3,5,8,13,...

Find the sum of all the terms in the Fibonacci sequence which are less than 1 billion \textbf{1 billion} and are perfect squares \textbf{perfect squares} .


Details and assumptions :-

Perfect square means square of an integer.


This problem is a part of the set Crazy Fibonacci


The answer is 146.

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.

13 solutions

Edward Jiang
Aug 27, 2014

PARI/GP code:

answer=0;for(n=1,44,if(issquare(fibonacci(n)),answer=answer+fibonacci(n)));return(answer)

I missed 1 and 1 as I carried the code from an earlier problem.

Vijesh Balasubramanian - 6 years, 8 months ago

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();
}

}

Vijesh Balasubramanian - 6 years, 8 months ago
Poca Poca
Jun 3, 2018

Actually, 1 and 144 are the ONLY fibonacci numbers which are perfect squares.

Jaydee Lucero
May 27, 2015

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 .

My Solution in C++ : My Solution

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
David Holcer
Apr 4, 2015
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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:
    if sqrt(i).is_integer():
        summ+=i
print summ

Aryan Gaikwad
Feb 28, 2015

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.

Ivan Koswara
Feb 15, 2015

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 , 144 0, 1, 8, 144 , thus the only perfect squares in the Fibonacci sequence are 0 , 1 , 144 0, 1, 144 . Since 1 1 appears twice (as F 1 F_1 and F 2 F_2 ), the sum of all perfect squares in the entire Fibonacci sequence (not only among those less than 1 billion!) is 144 + 1 + 1 + 0 = 146 144+1+1+0 = \boxed{146} .

Kartikay Shandil
Oct 11, 2014

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;
} }

Tan Li Xuan
Sep 24, 2014

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 2n 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
Debjit Mandal
Sep 19, 2014

Here is a C++ programme

#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;
}
Kenny Lau
Aug 29, 2014

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);
    }
}
Aditya Raut
Aug 27, 2014

Python

img img

So answer is 1 + 1 + 144 = 146 1+1+144=\boxed{146}

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 [ 5 3 ] \mathbb{Q} [ \sqrt[3]{5} ] is studied.

Calvin Lin Staff - 6 years, 9 months ago

Log in to reply

What does that mean? Why is the answer 146?

Ivan Martinez - 6 years, 9 months ago

Log in to reply

The question has been edited to reflect "sum of all the terms", hence the answer is 0 + 1 + 1 + 144 = 146 0+ 1 + 1 + 144 = 146 .

Previously, it only asked for "sum of all Fibonacci numbers", which would have been 0 + 1 + 144 = 145 0 + 1 + 144 = 145 . Those who previously answered 145 have been marked correct.

Calvin Lin Staff - 6 years, 9 months ago

Log in to reply

@Calvin Lin Yeah, i got that from the report, so edited the wording... Sorry for the previous bug ;)

Aditya Raut - 6 years, 9 months ago

(C++. This uses the fact that F 100 > 1 0 9 F_{100}>10^9 and that F n = ϕ n 5 + 1 2 = 2 ϕ n + 5 2 5 F_n=\lfloor \frac{\phi^n}{\sqrt{5}} + \frac{1}{2} \rfloor=\lfloor \frac{2\phi^n+\sqrt{5}}{2\sqrt{5}} \rfloor ) (I know I could've used recursion, but I'm just sharing a different approach)

int n, sum=0,k;

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;

mathh mathh - 6 years, 9 months ago

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.

Daniel Liu - 6 years, 9 months ago

Log in to reply

You're right, when I use

int n,sum=0,k;

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

int n, sum=0,k;

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.051 s 0.051\text{ s} instead of 36.056 s 36.056\text{ s} (I've made a function F ( n ) F(n) that uses the previous formula). The former code uses the fact that a a is an integer if and only if a = a \lfloor a \rfloor = a .

mathh mathh - 6 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...