[izmttkpa] Continuing factoring subpermutations

We continue this project of factoring total number of arrangements (A000522). The 74th entry required factoring a 106 digit number, which coincidentally makes this probably one of the largest "interesting" numbers less than the Pari/GP MPQS limit of 10^107. Here are some excerpts of logs after several attempts. An earlier attempt heartbreakingly failed after weeks of sieving at the Gaussian elimination step when it ran out of stack space.

GP/PARI CALCULATOR Version 2.5.1 (released)
amd64 running linux (x86-64/GMP-5.0.5 kernel) 64-bit version
compiled: Jun  4 2012, gcc-4.7.0 (Debian 4.7.0-11)
...
? allocatemem
  ***   Warning: new stack size = 1024000000 (976.563 Mbytes).
? a=2166690334049728637398152472258997933316264469602300239945569693840859184157823454814218981879047682695483
%1 = 2166690334049728637398152472258997933316264469602300239945569693840859184157823454814218981879047682695483
? \g5
   debug = 5
? factorint(a,2)
...
IFAC: trying MPQS
MPQS: number to factor N = 2166690334049728637398152472258997933316264469602300239945569693840859184157823454814218981879047682695483
MPQS: factoring number of 106 decimal digits
MPQS: found multiplier 3 for N
  *** factorint: Warning: MPQS: factoring this number will take many hours:
N = 2166690334049728637398152472258997933316264469602300239945569693840859184157823454814218981879047682695483.
MPQS: kN = 6500071002149185912194457416776993799948793408806900719836709081522577552473470364442656945637143048086449
MPQS: kN has 106 decimal digits
  *** factorint: Warning: MPQS: Gauss elimination will require more than
        128MBy of memory.
        (estimated memory needed: 671.2MBy)
MPQS: creating factor base and allocating arrays...
MPQS: precomputing auxiliary primes up to 2857698
MPQS: computing logarithm approximations for p_i in FB
MPQS: sieving interval = [-4000000, 4000000]
MPQS: size of factor base = 75001
MPQS: striving for 75071 relations
MPQS: coefficients A will be built from 10 primes each
MPQS: primes for A to be chosen near FB[2204] = 42239
MPQS: smallest prime used for sieving FB[23] = 151
MPQS: largest prime in FB = 2015677
MPQS: bound for `large primes' = 181410930
MPQS: sieve threshold = 137
MPQS: first sorting at 2%, then every 2.0% / 1.0%
MPQS: starting main loop
...
MPQS: passing the 94.9% sort point, time = 31162631 ms
MPQS: combined 1874 full relations
MPQS: done sorting and combining, time = 453 ms
MPQS: found 97.3% of the required relations
MPQS: found 73116 full relations
MPQS:   (43919 of these from partial relations)
MPQS: Net yield: 0.0484 full relations per 100 candidates
MPQS:            0.832 full relations per 100 polynomials
MPQS:  0.0% of the polynomials yielded no candidates
MPQS: next sort point at 98.2%

MPQS: passing the 98.2% sort point, time = 28315381 ms
MPQS: combined 1828 full relations
MPQS: done sorting and combining, time = 441 ms
MPQS: found 100.6% of the required relations
MPQS: found 75544 full relations
MPQS:   (45747 of these from partial relations)
MPQS: Net yield: 0.0489 full relations per 100 candidates
MPQS:            0.842 full relations per 100 polynomials
MPQS:  0.0% of the polynomials yielded no candidates
MPQS: next sort point at 100.8%

MPQS: starting Gauss over F_2 on 75544 relations
MPQS: allocating 177528402 words for Gauss
MPQS: Gauss done: kernel has rank 1223, taking gcds...
MPQS: splitting N after 37 kernel vectors

MPQS: time in Gauss and gcds = 3385143 ms
MPQS: found factors = 105813683306631260654781764176229625713668695827006873
        and 20476466429875651547352935271366523464249259799427571
IFAC: incorporating set of 2 factor(s)
IFAC: factor 105813683306631260654781764176229625713668695827006873
        is prime
IFAC: factor 20476466429875651547352935271366523464249259799427571
        is prime
IFAC: prime 20476466429875651547352935271366523464249259799427571
        appears with exponent = 1
IFAC: main loop: 1 factor left
IFAC: prime 105813683306631260654781764176229625713668695827006873
        appears with exponent = 1
IFAC: main loop: this was the last factor
IFAC: found 2 large prime (power) factors.
%2 =
[20476466429875651547352935271366523464249259799427571 1]

[105813683306631260654781764176229625713668695827006873 1]

The total CPU time (just for MPQS) was, according to 22730 minutes, or 15.78 days. ECM was done earlier but logs lost.

We continued the project beyond the 74th, with the results below omitting the largest factor, following the syntax of the earlier project. The factorization of the 75th entry took 138 hours. The factorization of the 76th entry took 5h 48min. We did not record the timing information for the 77th onward. Of particular note is the 40-digit factor discovered by ECM for entry 92.

74 [5, 1; 83, 1; 20476466429875651547352935271366523464249259799427571, 1;
75 [2, 3; 13, 2; 167, 1; 3682917197, 1; 260729064862210105030720490509777438225390260469, 1;
76 [31, 1; 271, 1; 2002688773377455707321, 1; 72381478872784439458747280290213204836701, 1;
77 [2, 1; 5, 1; 13, 1; 13151, 1; 96671, 1; 832639, 1; 24250670510794869309249314873258400378962665351, 1;
78 [41, 1; 203338256032829778169, 1; 40442480984938740185561, 1;
*** factorint: Warning: MPQS: factoring this number will take several hours:
N = 141526048519041406835843656481976641879132065425489424573484135185563746716849084962618073.
79 [2, 2; 5, 1; 9281, 1; 92570171423090362075199, 1; 1280082452540338514213384658213971, 1;
80 [461, 1; 286927, 1; 166082351, 1;
81 [2, 1; 29, 1; 31, 1; 71, 1; 293, 1; 60917, 1; 3695482147092585743609, 1;
82 [5, 4; 13, 1; 19, 1; 457, 1; 387464531, 1; 4583997233578942242071889781, 1;
83 [2, 5; 23, 1; 1699, 1; 2041627333, 1; 1751971722628997318165551, 1; 579103537312659330932244264229, 1;
84 [5, 1; 1106249, 1; 507771949, 1; 2305711211717, 1; 554288086949677841, 1; 110676906654036928151, 1;
85 [2, 1; 389, 1; 523, 1; 251071, 1; 3785634164408054311, 1; 9097035052266143874061234188799, 1;
86 [5849, 1; 20983, 1;
87 [2, 2; 5, 1; 23, 1; 109, 1; 5579152696711442312112543803, 1;
88 [13, 1; 1453, 1; 571759, 1; 1330113919, 1; 12333658903766491, 1; 89422417886020766951, 1;
*** factorint: Warning: MPQS: factoring this number will take many hours:
N = 18111446668644939704967262122398105418758136853800072226728808168278921610193458069388411928624121579.
*** factorint: Warning: MPQS: Gauss elimination will require more than
128MBy of memory.
89 [2, 1; 5, 1; 443, 1; 559282067879407901763648787150609, 1; 3559483372763450004281408085024350255426293003103, 1;
90 [13, 1; 19, 1; 37, 2; 1103000309, 1; 1475109780190215931873619047, 1;
91 [2, 3; 48419843, 1; 2434570736380921, 1; 5223088195992739489993, 1;
*** factorint: Warning: MPQS: number too big to be factored with MPQS,
giving up.
92 [5, 1; 2788081, 1; 53288831, 1; 493347709, 1; 8025614594640157860192422456065513857611, 1;
93 [2, 1; 17585891, 1; 141150887, 1; 675188392310644577, 1; 2501675799924537398585257259, 1;
94 [5, 2; 16759, 1;
95 [2, 2; 13, 1; 181, 1; 21486364354395307683881, 1;
*** factorint: Warning: MPQS: number too big to be factored with MPQS,
giving up.

The next unfactored item is the 96th entry, with 147-digit cofactor 114665026587413122476288423786085778256842237500279038484127423956844492554409197221213100215756613213045894816361223467579228544738231310494516733. (gmp ecm done up to B1=180255793.)