Learning with GP: Factorization of F6=2^64+1 - Euler, Lucas

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

Euler showed that a divisor of a^2^n+b^2^n, (a,b)=1, has the form 2^(n+1)*m+1 [5, #29].
We need an ordered list of such prime trial divisors less than F(n-1)=sqrtint(F(n)).

F(n)  = 2^2^n + 1; 
E5 = [ 64*m+1 | m <- [1..F(4)\64], isprime(64*m+1) ];    \\also m!=2^k {2]
#E5 == 210                             \\divisions needed to prove F5 prime
factor(F(5)) == [ 641, 1; 6700417, 1 ] \\Euler, 1732 [5, #32]
E5[1..5] == [193, 257, 449, 577, 641]  \\Euler had to try only m=3,4,7,9,10

Landry estimated in 1867 that 3000 years of hand computations were needed
to prove F6 prime by testing all divisors of the form 128*m+1 [6, p. 292].
Next, Lucas showed in 1878 that F6 is composite and estimated that it 
would take 30 hours of hand computations to find one factor [6, p. 292].
He proved that every prime factor of Fn has the form 2^(n+2)*m+1; thus
187 divisions are needed to find a factor of F6 with m=1071 in 256*m+1,
and Landry would have needed twice more to discover m=2142 in 128*m+1.

L(n=5,M=F(n-1)\2^(n+2)) = [2^(n+2)*m+1 | m<-[3..M-1], isprime(2^(n+2)*m+1)];
#L(5) == 98 && L(5)[1] == 641       \\first Lucas trial divisor is factor of F5
setsearch(L(6,4000),274177) == 187  \\187th Lucas trial divisor is factor of F6
setsearch([128*m+1 | m<-[3..4000], isprime(128*m+1)],274177) == 369


?? Can one bound the number of prime trial divisors of the form 2^(n+2)*m+1
   less than F(n-1)\2^(n+2) for n=6,7,8 without triggering a stack overflow ??


------------------------------ Features used [4]
Operators: "\" (integer division), "|" (such that), "<-" (in), "," (and)
Constructors: "[... ; ...]" (matrix), "[ | , ]" (vector)
Functions: factor, isprime, setsearch

------------------------------ Links
[5] Euler, David Zhao: http://eulerarchive.maa.org/docs/translations/E134tr.pdf
[6] Lucas: Am.J.Math. 1(1878) 184-240, 289-321, http://www.jstor.org/journal/amerjmath

Jacques Gélinas                  Next: Factorization of F6=2^64+1 - Landry