Problems & Puzzles: Puzzles

 Puzzle 789. Almost primes Fibonacci numbers. Claudio Meller posted the following interesting question in his always interesting site, as entry 1397: Other than 2, 3 & 8, are there Fibonacci numbers almost prime numbers, that is to say Fibonacci numbers that differ one unit from prime numbers? Q1. Find more terms or show that they do not exist.

Contribution came from Emmanuel Vantieghem and Dmitry Kamanetsky.

***

Emmanuel wrote:

About puzzle 789, there are indeed no more Fibonacci near primes. In october 2014 I submitted the comment to A000045 (the Fibonacci numbers) that  3  and  8  are the only Fibonacci numbers of the form  prime+1.
(I was lead to that as a 'spin-off' of your puzzle 756). Now I shall prove that  2  is the only Fibonacci number of the form  prime-1.

...

Let  F(n)  stand for the  nth Fibonacci number, i.e. : F(0) = 0, F(1) = 1  and  F(n) = F(n-1)+F(n-2).
I shall prove that  F(n)+1  and  F(n)-1  factor in two integers (of which some can be +1  or  -1  when  n  is small).

I shall use following abbreviations : w = Sqrt[5]  and  f = (1+w)/5.
As anybody knows, F(n)  equals (f^n - (-1/f)^n)/w = (f^(2n) - e(n))/(w*(f^n)), where  e(n) = (-1)^n.
Thus, F(n) + 1 = (f^(2n) + w*f^n - e(n))/(w*f^n).
The numerator of the right hand side of this equation is a quadratic function in  f^n  and can be written as  (f^n - a(n))(f^n - b(n))  where
a(n) = (-w + Sqrt[5+4e(n)])/2  and  b(n) = ( -w - Sqrt[5+4e(n)])/2.
Thus, F(n) + 1 = (f^n - a(n)) (f^n - b(n)) / (w*f^n).
If  n = 2m  is even, we have
a(n) =(-w+3)/2 = (1/f^2) ; b(n) = (-w-3)/2 = -f^2.
So, we can write :
F(2m) + 1 = [1/w]*[(f^(2m+2) - 1)/(f^(m+1))]*[(f^(2m-2) + 1)/(f^(m-1))].
At first sight this is a product of rational numbers.  But it is easy to write every factor in the form  a + b*f  with integer  a, b.
When such a factor stays unaltered when  w  is changed in  -w, b  will be zero.  With that in mind and with some tricky manipulations we can get the following decompositions :
m = 2k => F(4k) + 1  is the product of  (f^(4k+2) - 1)/(f^(2k+1))  with the integer (f^(4k-2)+1)/(w*f^(2k-1))
m = 2k+1  => F(4k+2) + 1  is the product of the integer (f^(4k+4) - 1)/(w*f^(2k+2))  with the integer (f^(4k)+1)/(f^(2k)).
If  n = 2m+1  is odd, we have :
a(n) =(-w+1)/2 = -1/f ; b(n) = (-w-1)/2 = -f
and thus : F(2m+1) + 1 = [1/f]*[(f^(2m+2) + 1)/(f^(m+1))]*[(f^(2m) + 1)/(f^m)]
and we can get in the same way :
m = 2k  =>  F(4k+1) + 1  is the product of the integer  (f^(4k+2) + 1)/(w*f^(2k+1))  with the integer  (f^(4k) + 1)/(f^(2k))
m = 2k+1 =>  F(4k+3) + 1  is the product of the integer  (f^(4k+4) + 1)/(f^(2k+2))  with the integer  (f^(4k+2) + 1)/(w*f^(2k+1))

For the decomposition of  F(n) - 1  the work is analoguous.
Thus, F(n) - 1 = (f^(2n) - w*f^n - e(n))/(w*f^n) = (f^n - a(n))(f^n - b(n))/(w*f^n), where
a(n) = (w + Sqrt[5+4e(n)])/2  and  b(n) = ( -w - Sqrt[5+4e(n)])/2.
If  n = 2m  is even, we have
a(n) =(w+3)/2 = (1/f^2) ; b(n) = (w-3) = -(1/f^2)
so we can write  F(2m) - 1 as follows :
F(2m) - 1 = [1/w]*[(f^(2m-2) - 1)/(f^(m-1))]*[(f^(2m+2) + 1)/(f^(m+1))].
m = 2k  \[Implies]  F(4k) - 1   is the product of the integer  (f^(4k+2) + 1)/(w*f^(2k+1))  with the integer  (f^(4k-2) - 1)/(f^(2k-1))
m = 2k+1  \[Implies]  F(4k+2) - 1  is the product of the integer   (f^(4k+4) + 1)/(f^(2k+2))  with the integer  (f^(4k) + 1)/(w*f^(2k))
If  n = 2m+1  is odd, we have :
a(n) =(w+1)/2 = f ; b(n) = (w-1)/2 = 1/f
and thus : F(2m+1) - 1 = [1/f]*[(f^(2m) - 1)/(f^m)]*[(f^(2m+2) - 1)/(f^(m+1))]
and we can get in the same way :
m = 2k =>  F(4k+1) - 1  is the product of the integer  (f^(4k) - 1)/(w*f^(2k))  with the integer  (f^(4k+2) - 1)/(f^(2k+1))
m = 2k+1  =>  F(4k+3) - 1  is the product of the integer  (f^(4k+2) - 1)/(f^(2k+1))  with the integer  (f^(4k+4) - 1)/(w*f^(2k+2)).

With some supplementary manipulations we can write the factors in function of the Fibanacci number.  This is what I finally found :
F(4n) + 1 =  F(2n-1) ( F(2n) + F(2n+2) )
F(4n+1) +1 = F(2n+1) ( F(2n-1) + F(2n+1) )
F(4n+2) +1 = F(2n+2) ( F(2n-1) + F(2n+1) )
F(4n+3) +1 = F(2n+1) ( F(2n+1) + F(2n+3) )
F(4n) - 1 = F(2n+1) ( F(2n-2) + F(2n) )
F(4n+1) - 1 = F(2n) ( F(2n) + F(2n+2) )
F(4n+2) - 1 = F(2n) ( F(2n+1) + F(2n+3) )
F(4n+3) - 1 = F(2n+2) ( F(2n) + F(2n+2) )

Remains only to see for which  n  the factors are +1 or -1, which give the exceptional near-prime Fibonacci numbers.
__________________________

The last formulas can also be 'verified' with a computer.
(No doubt they must have been discovered already during the centuries in which mankind studied these remarkable Fibonacci numbers.

So, for secutity and to avoid being accused of plagiarism, I do not claim them).

...

The question of puzzle 789 has been posed in :

As can be seen there, the eight last relations I submitted are indeed known (Lucas numbers can be expressed as sums of Fibonacci numbers).

So, my feeling was right.

***

Dmitry wrote:

I searched through the first 26,000 Fibonacci numbers, but didn't find any more solutions.

***

 Records   |  Conjectures  |  Problems  |  Puzzles