[ywpmmgro] Factoring numerators of sqrt 2 approximants

Consider the sequence r[1]=3/2, r[n]=(r[n-1]+2/r[n-1])/2.  This is Newton's method for finding the square root of 2: r converges quadratically to the square root of 2.  The sequence is also related to the Pell equation.  The sequence begins 3/2, 17/12, 577/408, 665857/470832...

The numerators (probably) follow the recurrence x[1]=3, x[n]=x[n-1]^2*2-1 .  The sequence begins 3, 17, 577, 665857, 886731088897, 1572584048032918633353217...

The first 4 numerators are prime.  Then

x[5] = 257 * 1409 * 2448769
x[6] = 11777 * 2393857 * 55780318173953
x[7] = 7681 * 1492993 * 431302713980890947612633357964569696769
x[8] = 7460967982148609 * P82
 where P82 = 6557680819899992376836645547305255477821013861491335119444201774860496852003279873
x[9] = 79873 * 719073884161 * C179
 where C179 = 83358018910805180047726643478925646913648467524836786442630545765268960638662906295877791791858969509238950792476217547984778257700960243269775361892921744818484916563400063848449

We did a long search for a factor of the 179-digit (595-bit) cofactor C179 of x[9] using the elliptic curve method but did not find any.

GMP-ECM 7.0.4 autoincrementing B1.  4 processes corresponding to the 4 physical cores on the machine:

for i in 1 2 3 4 ; do nice -19 ecm -c 0 -I 4 -one $b1start < n > ecm$i.out & done

Final completed iteration by the process which made the least progress:

Using B1=1001133571, B2=1001133571-19071176724616, polynomial Dickson(30), sigma=1:1452557145
Step 1 took 1936164ms
Step 2 took 390095ms

Peak memory usage during Step 2 was about 2.7GB.

In total, about 1.67 core-years of computing.  Each core was Intel(R) Core(TM) i7-4790K CPU @ 4.00GHz.  This is probably more than enough to proceed on to the general number field sieve (GNFS), but that is a project for another day.

Incidentally, from x[8], P82-1 = 2^10 * 11 * 197 * 14268312047910853080882581 * 207118459764708621027403333949253228941663842143239 .

The denominators of the r sequence are the product of all the previous numerators and some power of 2, so they are easy to factor once the factors of the numerators are known.  If r[n-1]=p/q, then the denominator of r[n] is 2*p*q.