\\ \r c:\tx\VERIFY_703.gp
\\ ---------------------------------------------------------------
\\ This PARI/GP script demonstrates that N-k factors for k=0..9
\\ and proves primality of all factors (APRCL test from IsPrime)
\\ ---------------------------------------------------------------

\\ Ensure enough stack for primality proving...
allocatemem(20*10^6);

\\ Subroutine used to print ~# decimal digits...
digits(n)= #Str(n);

\\ Subroutine used to verify primality of factors
checkprimes(pset)=
{
   for(i=1,length(pset),
	print1("Testing prime #", i, "/",length(pset),"\t ", digits(pset[i])," digit(s)...\t");

\\ switch this line for following line if proving primes...
\\	if(!isprime(pset[i], 2), 
	if(!ispseudoprime(pset[i]), 
		print("\n*************FOUND NON-PRIME************ : ", pset[i]),
		print("VERIFIED!");
	);
   );
   print("Finished checking primes.");
}

\\ Subroutine used to verify a number factors completely with the given factors...
verifyCompletelyFactors(lbl, n, pset)=
{
   for(i=1,length(pset),
        while(n%pset[i]==0, n=n/pset[i]);
   );
   if(n==1, print(lbl, " completely factors."));
   if(n!=1, print(lbl, " DID NOT COMPLETELY FACTOR: Digits Left=",digits(n)));
}

\\ Subroutine used to print factorization...
printFactorization(lbl, n, pset)=
{
   print("---------------------------------------------");
   print1(lbl, " = ");
   fCount=0;
   for(i=1,length(pset),
	expCount = 0;
        while(n%pset[i]==0, 
		n=n/pset[i];
		expCount = expCount+1;
	);
	if(expCount > 0,
		if(fCount > 0, print1(" * "));
		fCount = fCount+1;
		if(digits(pset[i]) > 20, print1("p", digits(pset[i])), print1(pset[i]));
		if(expCount > 1, print1("^", expCount));
	);
   );
   if(n==1, print(" [complete]"));
   if(n!=1, print(" DID NOT COMPLETELY FACTOR: Digits Left=",digits(n)));
}

\\ Define starting N such that N-k factors for k=0..9
x = (887040*(90^12 + 111833012))^3;
N = ((x*(5*x + 9)/2 - 31)^2 - 23^2)*((x*(5*x + 9)/2 - 31)^2 - 24^2)/55440+1;


\\ List of prime factors needed for complete factorization...
factors = [2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 41, 53, 59, 83, 89, 103, 137, 157, 163, 173, 197, 239, 241, 257, 269, 293, 449, 463, 487, 641, 677, 1237, 1319, 4079, 4133, 4721, 4861, 6961, 7573, 8429, 10753, 11839, 16001, 46499, 55609, 70507, 87049, 116293, 274973, 313933, 392159, 392443, 906823, 2351263, 2485073, 3057007, 7446793, 14237603, 57482213, 68584667, 303775457, 425585317, 981742453, 12390250603, 13728113437, 68219878477, 131679928339, 381488038681, 462620692403, 9654557976929, 12435367768589, 12683050903123, 140477207564839, 630259423347317, 901218628584317, 164149758593811967, 411332105162957519, 1988600182502075783, 3276055668231296267, 6870702102249368659, 9323568482800743161, 7795461012843187990059199, 33149325702335458851579341, 260172449926811929035350826091, 1269872752096078507979335383599, 9669550233544435375557769567153, 2360578532615379194929178201025349, 367976472250843280791966711358177953, 3892682480172514970480939619480019223, 58130123165064994906452158476554824029, 15223909874348358974851188325731198722002409, 15108855722066292086389891853338191325033709928096121, 499524512241167061789413229003729509184108096802211073409, 10494347741384920661144877561340083568978429272003460742633, 42823638155592295501589956561528346972325869068174232243623637347, 16951154355788530178104217461024513706300145304574366796538557804121, 1829055837237982915251619336597180975905571357734604112099369675323879, 2369898157201664369071987219354981398749094340205776257348069340155257087, 8586003417616576718090324916324707595976594797359752098641043332748650167, 9867819978384278619956294537368978925192159544086646398961374957292063727, 3935161077451634316971150930230328910277288574512329708155729392891380404108714093, 8735493552188193449423855866811330500338440890721691851514216931005883399263423037440001, 3170970794225727329321200288517180338107872852190460711796341512855639339227445852183298386837309339215974029658316649854721145406061361, 23986911952889385545207942919750495805093443987293237095248265406287411769986943478571076469349420621340301274180158830039251291653843647, 1153403655532048033020388150472523156118899935315742577335109467337017712352307759295113803534362481448755802478888663421616880604044232388184863656791, 37680223587148534204317012443876372557929839640420906180155846961328886566664252556913281856156597565057740680394042206583621688028269799636710358518080817004999965407, 3821691982051600908550832698944079871545343197796709741025297253386559858539056411899210719359774555813556150911338576285470270244458494223845010546328544227056086367938941720916304066123186240359988395423497203981091804053945169466714151778668151242304195070279354417046054127802589696443260708711951325480769157920346231785507778558650871135035502143499595244981882361516864355508373118746863294925147985486449060279120281935951816355789661224984787226558054181052031485508848819323159427672904130399263122589613768698143988498168879428000960439070803202137304692931501638825233162127917299231843962612092344569776460391027267841, 297724548843662715330657987830844575554467037547368503221091233441679026707233489179628481590625773278331221896175237070796989187639858464083059271946977738525910493626497825833676375874891283441788314813476278779238813532054837419152538717972423919962901885543208422042864105892941536809794767734496923596104500260847828443903390384379830031379830581129698464625017621613375663567083031498394230928058062295105679019832833072732480278602726324976764440758933485507390763527007465482780013450110630271047095661051392760769264022196156385134438294638336134513824857570191552148285364381789626980197614628822069060746299498780733208008889008291213910865092855613238835640529, 320115121452623167851298285373614783057048592964653596097839429880586327981792422762439160698996087468464242689491412643032508537272285684660853433453282553597137067612575625198856390511117663299708119574579815915034514380597400151447278262158232779309590063988637110219007847377681493030586258845431947558063335998078531464384905074289162813787758813463170270891364932704690300459208898578996889279747026913446143848844205476478374579399360572801138112948274658984620871224257665881479331188102046777000142147347397608268074788146998843212307083762433825745596927417168873146551978808347719103889205386949654972982574109795105977271672537880411708209497242698273556684570255380105339872068337793, 287140505834747473085107717987925620444940446233841750055297825368622595996820103185036487219668786926557827734662425145860821127703722916947625075295516491222096648761977838968998491411075840054066487660028982452898263061012612706857919111028035304688693839626506898671149864420068134689819949185503205228329994525346368756491891500944733298099772645866641114334150220104567918179841860103341697223004617658197687679227075118352389838097300973066962550537317723706428197194470968769718518929783173426337937298816526828745478988784166871412741256702291381166781804766003843118992343923760402730723549367852857958388570457197882674397922629644778756672802378180101280704770601958474390800805349889329, 877597099332933193572450888743763337953219650506031668752341920268300194231614508701199850439047702443202907499706592054132622973305145141830924771794863569338468057499524935168915722582718125818578541784935246703541391335474881969726753443005351902896877938511813917971924368955868242323653038027292962912852573267633618376091384390720753203425605129983744125776607789379594413930323338429180007279243113102671532776944350586724354141838050874016993208625555402888080046692034770883183033355727305715364182364282911497589098949387342014661141527567769891306074122633163079186013600478986377546001408051280951540154934174015795413851517530404325473310975001844449547594013883119083896417528084378419199]
;



\\ Verify primality of factors...
checkprimes(factors);

\\ Verify we can completely factor N-k for k=0..9 using these prime factors...
for(k=0,7,verifyCompletelyFactors(Str("N-",k), N-k, factors));

\\ Verify we can completely factor N-k for k=0..9 using these prime factors...
for(k=0,7,printFactorization(Str("N-",k), N-k, factors));