Sequence A057207
 

The seventeenth element of OEIS sequence [URL="http://oeis.org/A057207"]A057207[/URL] is 6143090225314378441493352126119201470973493456817556328833988172277, which is the smallest factor of this [URL="http://factordb.com/index.php?query=%282*5*101*1020101*53*29*2507707213238852620996901*449*13*8693*1997*6029*61*3181837*113*181*1934689%29%5E2%2B1"]C141[/URL].

Thereafter, the sequence continues 4733, 3613, 41, 68141, 37, 51473, 17, 821.

Thereafter the sequence probably continues [URL="http://factordb.com/index.php?query=(2*5*101*1020101*53*29*2507707213238852620996901*449*13*8693*1997*6029*61*3181837*113*181*1934689*6143090225314378441493352126119201470973493456817556328833988172277*4733*3617*41*68141*37*51473*17*821)^2%2B1"]598201519454797[/URL]*, 157, 9689, 2357, 757, 149, 293, 5261, [URL="http://factordb.com/index.php?query=(2*5*101*1020101*53*29*2507707213238852620996901*449*13*8693*1997*6029*61*3181837*113*181*1934689*6143090225314378441493352126119201470973493456817556328833988172277*4733*3617*41*68141*37*51473*17*821*598201519454797*157*9689*2357*757*149*293*5261)^2%2B1"]1774915226229214328737[/URL]*, 233, 73, 13989077153, 11689487473519919005062249197**, 353, 4021, [URL="http://factordb.com/index.php?query=(2*5*101*1020101*53*29*2507707213238852620996901*449*13*8693*1997*6029*61*3181837*113*181*1934689*6143090225314378441493352126119201470973493456817556328833988172277*4733*3617*41*68141*37*51473*17*821*598201519454797*157*9689*2357*757*149*293*5261*1774915226229214328737*233*73*13989077153*11689487473519919005062249197*353*4021)^2%2B1"]24891406347771253321[/URL]*.

*Not proven to be the smallest factor. Cofactor has had ECM to t35 or better.
**Cofactor is prime.

Computation of the next element requires the factorisation of a [URL="http://factordb.com/index.php?query=(2*5*101*1020101*53*29*2507707213238852620996901*449*13*8693*1997*6029*61*3181837*113*181*1934689*6143090225314378441493352126119201470973493456817556328833988172277*4733*3617*41*68141*37*51473*17*821*598201519454797*157*9689*2357*757*149*293*5261*1774915226229214328737*233*73*13989077153*11689487473519919005062249197*353*4021*24891406347771253321)^2%2B1"]C572[/URL], (ECMed to >t35).

I will continue with ECM on these numbers. If anyone else would like to have a go, please let me know.

TF using gmp-ecm 6.3 has proven that 13989077153 is correct (assuming that the previous elements are).

I checked that 598201519454797 is correct using Pollard-Strassen. The next asterisk is probably infeasible without a full factorization.

[QUOTE=arbooker;334171]I checked that 598201519454797 is correct using Pollard-Strassen. The next asterisk is probably infeasible without a full factorization.[/QUOTE]
Strangely I have never heard of this method. It doesn't have a wikipedia page. Could someone more knowledgeable than I write one?

Anyone have good code for it?

I'll help with some ECM. Is the C373 cofactor with 1774915226229214328737 the current target?

What t-level should I start at?

Nice sequence BTW.

[QUOTE=swellman;334177]I'll help with some ECM. Is the C373 cofactor with 1774915226229214328737 the current target?[/QUOTE]
A P42 factor was just reported, so it's down to a C331. (Is there any way to tell who reported the factor on factordb?)

Thanks for the note on the p42. The C331 seems like the place to focus efforts.

I am currently running this C331 up to t35 just as a double check for missed small factors, but I am willing to take it up to t50+ if that would be helpful and not too duplicative of the OP's effort.

[QUOTE=henryzz;334175]Strangely I have never heard of this method. It doesn't have a wikipedia page. Could someone more knowledgeable than I write one?[/QUOTE]

See [url]http://arxiv.org/pdf/1201.2116.pdf[/url].

Basically, Pollard-Strassen follows a baby step/giant step approach, using FFTs to evaluate polynomials at many points simultaneously. Montgomery's P-1 stage 2 is based on similar ideas. Curiously, everywhere I have seen it mentioned (including the paper above) describes it as a theoretical result only, with no chance of implementing it in practice. However, on modern machines with large memory, it gives some improvement in speed over trial division.

Theoretically, it finds all prime divisors of the input number up to some bound B in essentially square root time (i.e. sqrt(B)*log(N)^c). However, it also uses about sqrt(B) memory, and that is the bottleneck. In a world like ours where both CPUs and memory chips cost money, it gives at best a constant factor speedup (which may nevertheless be significant).

[QUOTE]Anyone have good code for it?[/QUOTE]
I wrote some code for it using the FLINT library that I could make available if there's some interest. However, running P-1 on gmp-ecm with a large B2 is almost certainly faster, so I doubt it would be all that useful.

[QUOTE=arbooker;334171]I checked that 598201519454797 is correct using Pollard-Strassen. The next asterisk is probably infeasible without a full factorization.[/QUOTE]

Pollard-Strassen is interesting and brand new (to me). Google describes it as the fastest deterministic primality method in existence.

Does your statement mean you checked the the C243 cofactor of 598201519454797 to the P15 level? Or am I badly contorting your meaning?

At what max size cofactor would Pollard-Strassen be practical for proving that 1774915226229214328737 is the smallest prime factor? <C250?

Hoping someone peels off another factor from the C331.

[QUOTE=arbooker;334187]A P42 factor was just reported, so it's down to a C331. (Is there any way to tell who reported the factor on factordb?)[/QUOTE]

That was mine.

[QUOTE=swellman;334177]I'll help with some ECM. Is the C373 cofactor with 1774915226229214328737 the current target?

What t-level should I start at?[/quote]

I've given it a t40 and am part-way to t40 on the others, including the C572. I'll complete these, then quit. My resources are extremely limited. If other people with bigger guns than I are taking these on (and anyone who even mentions t50 has bigger guns :smile:) , then my efforts are redundant.

[QUOTE]Nice sequence BTW.[/QUOTE]

Thanks.

[QUOTE=swellman;334210]Pollard-Strassen is interesting and brand new (to me). Google describes it as the fastest deterministic primality method in existence.[/QUOTE]
It is one of the factoring methods with the fastest theoretical worst-case running times that we can prove at present. For actually factoring something in real life, other methods are much better, but P-S is potentially useful in these cases when we want to prove that we haven't missed any small prime factors. (ECM gives this with a high probability much more quickly, but you never know...)

[QUOTE]Does your statement mean you checked the the C243 cofactor of 598201519454797 to the P15 level? Or am I badly contorting your meaning?[/QUOTE]
No, you got it. :smile:

[QUOTE]At what max size cofactor would Pollard-Strassen be practical for proving that 1774915226229214328737 is the smallest prime factor? <C250?[/QUOTE]
Unfortunately it doesn't work that way. Much like ECM, it depends mainly on the size of the factor we're looking for (or ruling out in this case), and is insensitive to the size of input number. If we had computers with many terabytes of memory then ruling out P20s might be feasible. (It is in principle possible to write something using disks for memory, but it's probably not worth that level of effort.) Without that, our only viable option is to factor the number completely.