(No) Primes in the CF Convergents of Sqrt(5)

Conjecture? Or con?

Brief Background Overview

Don't ask why, I was looking at the convergents of sqrt(23) (blame Dr. Heath-Brown), and for no good reason at all I just wondered whether primes were dotted throughout them or not:

apply((x)->if(ispseudoprime(x),x,0),contfracpnqn(contfrac(sqrt(23)),99999))
      %17 =
      [0 5 19 0 211 0 0 1151 0 0 0 0 0 0 0 0 0 0 101170579 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 536123334577939 0 0 0 0 0 0 0 0 0 0]

      [0 0 0 5 0 0 191 0 2111 2351 0 0 0 112799 0 0 4859521 0 0 0 0 259663249 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

Nothing to see here. But why 23? Ask Roger! I wonder if other numbers have any interesting properties amongst their convergents...

apply((x)->if(ispseudoprime(x),x,0),contfracpnqn(contfrac(sqrt(2)),99999))
      %18 =
      [0 3 7 17 41 0 239 577 0 0 0 0 0 0 0 665857 0 0 9369319 0 0 0 0 0 0 0 0 0 63018038201 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 489133282872437279 0 0 0 0]

      [0 2 5 0 29 0 0 0 0 0 5741 0 33461 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 44560482149 0 0 0 0 0 0 0 0 0 0 0 1746860020068409 0 0 0 0 0 0 0 0 0 0]

Yup, nothing special...

apply((x)->if(ispseudoprime(x),x,0),contfracpnqn(contfrac(sqrt(3)),99999))
      %19 =
      [0 2 5 7 19 0 71 97 0 0 0 0 3691 0 0 0 0 0 191861 0 0 0 0 0 0 0 0 0 138907099 0 0 708158977 0 0 0 0 26947261171 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

      [0 0 3 0 11 0 41 0 0 0 571 0 2131 0 0 0 0 0 110771 0 0 0 1542841 0 0 0 0 0 0 0 0 0 0 0 0 0 15558008491 0 0 0 0 0 808717138331 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

Snore... is this going anywhere, Phil?!

apply((x)->if(ispseudoprime(x),x,0),contfracpnqn(contfrac(sqrt(5)),99999))
      %20 =
      [2 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

      [0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

Waaaaat!??!??!?!?! Are 2 and 17 the *only* primes in these sequences?

There's got to be something going on...

Let's Investigate...

Clearly, these sequences are OEIS:A001077 Numerators and OEIS:A001076 Denominators of continued fraction convergents to sqrt(5).

Every time I see something lacking primes, I go in search of algebraic relations between terms and/or a covering set.

The Numerators

For the numerators, from the OEIS link:

A001077(n) = ((2 + sqrt(5))^n + (2 - sqrt(5))^n)/2

Conjecture (that 2's the only prime): Proven.

The Denominators

For the denominators, from the OEIS link:

A001076(n) = a(n) = ((2+sqrt(5))^n - (2-sqrt(5))^n)/(2*sqrt(5))

Dr. Sardonicus on Mersenne Forums points out that because the Fib/Lucas numbers satisfy L_n² - 5·F_n² = 4 · (-1)ⁿ And the CF convergents I'm looking at satisfy x² - 5·y² = &pminus;1 Then my convergents will correspond to both-even L/F pairs, which are the terms with 3|n. And because of L/F divisibility rules, that means they're definitially composite, apart from trivial small prime cases. Thus proving the assumption made above.

Conjecture (that 17's the only prime): Proven.

Auxiliary Guff

Before I asked on Mersenne Forums, I was just trying to gather data to try and detect patterns, and did a bunch of gmp-ecm runs. Here's the data I accumulated. It's a subset of the known Lucas/Fib factorisations, and more annoyingly two substreams of that data interleaved (due to the now-known divisibility properties), it's not particularly useful. Use FactorDB instead - it knows every factor of all these numbers, and more. However, it's left here as a testament to how amazing GMP-ECM is - these were almost all found in just a single day. (After some prep-work in Pari/GP - also amazing software.

? A001077(n)=([4,1;1,0]^n*[1;-2])[1,1]
      (n)->([4,1;1,0]^n*[1;-2])[1,1]

Credits: P25₍₁₇₎ Paul Leyland; most of the rest on inz's machine.

A001076(n)=([4,1;1,0]^n)[1,2]
forprime(p=2,500,a=A001076(p);f=factorint(a,if(p>150,15,8))~;bf=f[1,#f];c=if(ispseudoprime(bf),0,f[1,#f]=Strprintf("C%d",ceil(log(bf)/log(10)));bf);print(p" "f[1,]);if(c,write("dcomps",c" // "p)))

#include <stdfooter.h>