Learning with GP: Factorization of F6=2^64+1 - Landry

[Jacques Gélinas <jacquesg00@hotmail.com>]

Landry, then aged 82, found the factor 274177 of F6 after six months of work [7].
As discussed in [9], his method is probably modified from the one of Fermat [1, p. 367]
presented in [Knuth, II.4.5.4]: if N=uv, then (u-v)^2=(u+v)^2-4N, and digits of perfect
squares are very special.

------------------------------ Start cut

Knuth454C(N=377) ={ my( x=2*sqrtint(N)+1, y=1, r=sqrtint(N)^2-N );
  while(r,
    while(r>0, r-=y; y+=2); if(r==0,break);
    r+=x;x+=2 );
  return((x-y)/2);
}

F(n)  = 2^2^n + 1;
Knuth454C() == 13
Knuth454C(F(4)) == 1
Knuth454C(F(5)) == 641

------------------------------ End paste

Landry used this method until 1867 to find the factors of many numbers of the form 2^n-1,2^n+1 [see 6],
but noted that it became unusable when two factors were widely separated. He then shortened the
"while" loops by predicting the final values of "y" and "x" [8,9]. Unfortunately, he started by
looking for a large factor of F6 and only found 274177 when "there was not much left to do".


------------------------------ Features used [4]
Operators: +=, -=
Functions: sqrtint, break

------------------------------ Links
[7] Fortuné Landry, C.R.Acad.Sc. 91(1880)138, Nouv.Corresp.Math. 6(1880)417
[8] Fortuné Landry, Journal de Mathématiques Élémentaires, 5(1881)3-9.
[9] H.C. Williams, How was F6 factored ?, Math.Comp. 61(1993)463-474,
    http://www.ams.org/journals/mcom/1993-61-203/ (References for Landy and Lucas)

Jacques Gélinas