Quadratic Residue of Fibonacci? Sounds Crazy!

Computer Science Level 3

Find the sum of all the Fibonacci numbers $F_n$ less than 1 billion which follow the condition $13 \mid (4 F_n^2 -22F_n+11)$

Details and assumptions :

Fibonacci sequence is defined as $F_0=0,F_1=1$ and for $n\geq 2$ , $F_n=F_{n-1}+F_{n-2}$ . Thus, the Fibonacci sequence is $0,1,1,2,3,5,8,13,\ldots$ .
$F_n$ denote the $n$ -th Fibonacci number.

This problem is a part of the set Crazy Fibonacci .

The answer is 44795300.

4 solutions

Edward Jiang
Aug 27, 2014

PARI/GP code:

i=1;while(fibonacci(i)<1000000000,i++);i=i-1
answer=0;for(n=1,i,m=fibonacci(n);if((4*m^2-22*m+11)%13==0,answer=answer+m));return(answer)

So, I don't want to post an official solution since it won't get any upvotes now, which is why I'm posting my solution (which uses a bit of number theory) here in the comments for the sake of variety.

We first reduce the given modular condition as follows:

$13\mid (4F_n^2-22F_n+11)\iff 4F_n^2-22F_n+11\equiv 0\pmod{13}\\ \iff 4F_n^2+4F_n-2\equiv 0\pmod{13}\\ \iff 2F_n^2+2F_n-1\equiv 0\pmod{13}\\ \iff 2F_n^2+2F_n+12\equiv 0\pmod{13}\\ \iff F_n^2+F_n+6\equiv 0\pmod{13}\\ \iff F_n(F_n+1)\equiv -6\equiv 7\pmod{13}$

From the last conclusion, it's easily obtainable that the given condition in the problem is equivalent to $F_n\equiv\{4,8\}\pmod{13}$ by listing out the $12$ possible modular results for $n(n+1)$ in $\Bbb Z/13\Bbb Z$ . Hence, we have,

$13\mid (4F_n^2-22F_n+11)\iff F_n\equiv\{4,8\}\pmod{13}$

Using the equivalent and simpler modular condition, here 's a C++ solution.

Prasun Biswas - 5 years, 10 months ago

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((4*current*current-22*current+11)%13==0) sum += current;
        }
        System.out.println(sum);
    }
    }

David Holcer
Apr 4, 2015

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 ((4*i**2)-(22*i)+11)%13==0:
            summ+=i
    except(ValueError):
        pass
print summ

Elmokhtar Mohamed Moussa
Jan 27, 2015

C++

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main()
{
 long int Fn_2 = 0;
 long int Fn_1 = 1;
 long int Fn,i,x,som;
 som = 0;
 i = 2;
        while(Fn < 1000000000)
        {
                Fn = Fn_2 + Fn_1;
                x = (4 * (Fn * Fn) - 22 * Fn + 11);
                if(x % 13 == 0)
                {
                         som += Fn;
                }
                Fn_2 = Fn_1;
                Fn_1 = Fn;
                i++;
        }
 cout<<"Somme"<<som<<endl;
}

Quadratic Residue of Fibonacci? Sounds Crazy!

This problem is a part of the set Crazy Fibonacci .

The answer is 44795300.

4 solutions

0 pending reports