Problems & Puzzles: Puzzles

Puzzle 1177  Golden Ratio Primes Sebastián Martín Ruiz sent the following puzzle: Let: F(n)=Round(GoldenRatio^(2n + 1)) where GoldenRatio=(1+Sqrt(5))/2 Conjecture: If F(n) is prime then 2n+1 is prime   The first values are:   F(n)                      2n+1 11                            5 29                            7 199                         11 521                         13 3571                        17 9349                        19 3010349                   31 Q. Prove the conjecture or find a counterexample

---

From May 25 to May 31, contributions came from Alejandro Casini, Emmanuel Vantieghem, Giorgos Kalogeropoulos

***

Alejandro Casini wrote:

Considering Binet's Formula for Lucas numbers L(n) = phi^n + 1/(-phi)^n, then the puzzle's sequence is F(n) = L(2n+1) (a subsequence of OEIS A000032). Thanks to Carlitz, if a Lucas number is prime then its index is a prime number or a power of two (it's related to the fact that the Lucas numbers resemble a divisibility sequence). Since the index here is always odd, it follows that it must necessarily be prime. The following puzzle's terms are related to OEIS A005479.

 ***

Emmanuel Vantieghem wrote:

Put  t = (1 + Sqrt(5)) / 2  and  u =  (1 - Sqrt(5)) / 2.

First observation : for all  m  > 1  we have :
     Round(t^m) = t^m + u^m.
Proof :
   *  u^m  is a number < 0.5  in absolute value.
   * t^m + u^m  is always an integer (follows from the basic theory on algebraic integers).
   * Thus : Round(t^m)  must be equal to  t^m + u^m.

Next, let  F(n) = Round(t^(2n + 1)).
Suppose  2n + 1  is not prime.  Let  p  be a prime divisor of  2n + 1, i.e. : 2n + 1 = k p.
Let  T = t^k  and  U = u^k.
Then we have
     t^(2n+1) + u^(2n+1) = T^p + U^p = (T + U) G(t , u)  
where  G(t, u) = T^(p-1) - T^(p - 2) U + ... -T U^(p-2) + U^(p - 1),
Also by the theory of algebraic integers we have that  G(t, u)  is an integer.
Thus : 2n + 1 not prime  ==>  F(n)  is divisible by the integer T + U, i. e. : F(n)  is not prime.
With a simple logic turn we then find :
     F(n)  prime  ==>  2n + 1  is prime.
So, the conjecture is true !

***

Giorgos Kalogeropoulos wrote:

In  the "formula" section of A000032 it is stated about Lucas numbers L(n): 

For n >= 2, a(n) = round(phi^n) where phi is the golden ratio. - Arkadiusz Wesolowski, Jul 20 2012
 

So, we are searching for odd indices of the prime Lucas numbers (A001606).

In the "comments" section of A001606 we find:

"...L(n) cannot be prime unless n is itself prime..." - John Blythe Dobson, Oct 22 2007

which proves the conjecture.

***