\\ ---------------------------------------------------------------
\\ This PARI/GP script demonstrates that N-k factors for k=0..8
\\ 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..8
x = 2310*(10^30+40790547)+5;
t1 = 5*x*x*x - x*x - x - 1;
t2 = t1*(5*t1+9)/2 - 31;
t2 *= t2;
N = (t2-23*23) * (t2 - 24*24)/55440;


\\ List of prime factors needed for complete factorization...
factors = [2, 3, 5, 7, 11, 13, 17, 19, 19, 23, 29, 37, 43, 47, 53, 61, 71, 73, 79, 103, 113, 131, 157, 283, 313, 317, 331, 389, 419, 619, 643, 691, 727, 1093, 1433, 1579, 1901, 1913, 2011, 2423, 3547, 4261, 6689, 7451, 10601, 13309, 33569, 75337, 76757, 86851, 92627, 110917, 574283, 915283, 1319261, 2439953, 15755933, 255946099, 1114238843, 2653993787, 3079307041, 4719726079, 6361306879, 14266216717, 18290398183, 19750153781, 101557755913, 166880080123, 172788128959, 266403633889, 444546250219, 489625035961, 1270641752531, 1848987653587, 17346192250609, 52875541480393, 3354903562911899, 52004118381270427, 63033107717874313, 147279592197387043, 365172908112440801, 717795020292627461, 11349953878687101971, 2561508111902244874441, 1289593158350311282393141, 23659571581081290354933869, 3702831616477791607996624583, 79444083751332871206115014253, 257083647123710228163986163068933, 72995580604330472767675305956448577, 5650656063178953440230244461478711321, 103254525137730884356325462161948293611, 258152730541656904182113569565579770280957857, 1890907634926683857961173716314441547212123672350629, 32639399163965702665322588630095762611168465302871817, 290963797629785789829587858554435806099102183324391210019, 450306550911446554674008453280965308352893868510532064297, 1159459696029019298615512562569201052337715269676992150571, 344388126566808701830834392491420283719805371748824281502279, 101395877354331666235965890216235926227140750818573375760797579, 4799995106140499339265636929746263616111770974981245944687585577, 25680373978698894578006006245685748564269008939777185093119975580853, 61795841127498738668772363572553955238962417043039906825237172011091635954239597, 7423574759509261460819979768473950225646324801051680510010128954872507181358849536795703, 15516753433189944918910992099992845607888494478960888121798680997688704717693550507172185714219, 263835423801369863013730916110752495832191782138880338638851594918414481883131465152263052713273663, 61631955000000000000007542003471783026400000307642447106035732572941622967899510259568649113820727673, 3649682510725537007425276195322911915332208177782676302046766103340728769618932807593262154741181712973564003103, 329717977532262240764745389133388989475063541661399274000306678512865674777976547994209353911413438933330737758598303758122047, 5715444996056603421288522870733528787435898718545067670986221446315823787588705707749193186082986329937601489837900897917020845211645033463227, 36666734407117219300514766129735427723031863623789410226119966507111395237732790320214641435454433341255486268836866249362203194571981532931307, 54076763599622413525359748434676447007280788635568722994736593287262429063324143776398234293027462569762217074967207645461719612421989698929945491374185704164228447081879263525107032319, 2664914641306091964627031785119196954432860608080243452036752908413756944784596529845389045712478367349638745887511075198797942070842227861854986244093460207879225181432588869528135994031786533890846607816329968137156230887639274890029971843405782503151463765172704006292492194680767910484604218903271103363511107913815186955428508239077329525548290551800420587102457994497868558267749512441760387314913849510202739480659594073362319860892628415300410535542753623528358622686087930111261136748020975639435072772182562285610779184706453908575613024623172073515454294439951472858456800828690338413301011617084540911006143229535041809992666900542904750459920741447174572583571051478402091630389556647915559860381092179632617594621536600366765519372592603554753, 2237575564400110749619132565867838769005234741843560153907827491428440793090151792165298859823549972575569838295445187961097167625836448373198437800742535234610731137331560953844401429885246835870631595954193029567473732418716438794548709646495535566014201440738105529975366784029061114840588692814696979326687231489105741513025624741922300910896019750659175176680001174896238122062499679562424403071018781375622027595132085872976348829622631137770138140257064838285543676493281170254857472468930617536452015772900363304811047548557275047679003073726243268743379685336455599785756148953766110151689222604153712438041570744242667607202800092027001454653379005639157109052608298145911038714994154281043163675298088812157045630433073718082541926651040200587414435135313823407355217, 126867002279688864719252421530436950040307950678737241507016693983401281908908538370793188266203410076137097805007790470415182293137289776758356416310215331624722997890416771824336283890247394899550934118015972345510572400731524119246251043896452924834087622514654445719071615844159058070296673325537118888286621968419402108784776156441554230805054809112185755801306496565513493763811689922259402577035566496293116497404331711090047644921511202870644713991424286654340177641520937844376422546029216427439992425496049863424375716971985845916593909516792167319156107660144280666536037399049124649794945491940096551206683319205329328745718186384754361499349314527404528298446714607629018526270349331267090154449420101194924990272436794239684525235409772673180937709729024723458858038107, 3282635054478504343229035217779940195996432357557521617323827242013453044608277186427567555046137809372484146479721697276311820050593832011523576561428494206593460970632329531736741017653240187648459812986073485806431299433400252062572866815018280646778000858848311931487711300290439209269100449936499030534608887889793056286510756536299971743487315366945291939321659190240933572570802276266851404746442689130993843403339827322389427682931210441111617671998722806794834422055793552205638573737568959405255597520399287328887301929309724076206080254451194506455150820832478063192575373972378085783165713985757705527320602059132136773663386498558089828238856382612743869842153837704775747423273722169368778790063968411979743154810755486247143109534519713625020868874722319494237174914514596361097694001, 14668454740937196657718943870649662765810057989745785347011522030937114929832086607551585619723666801180945408544636404279199367896078538343493101864743226362162880347270564512565627237383503778507142674328269371326038261518149026341606855362909187070127496837763681865852837945347827606618975360541245917943899815535540272016273315582456423735773068717195037030858834091591611669032629971498425502109479156381845989247824018390097157601178113856107263567326292862162717614956313488030895966746326895102384637519904215429132908671120502034526869617015162652094841442889928225376023058595571476322075992945358307148832110301231953173114842568806824397485329745705045982389664423783790427360898627513824388023400842848931482287271860890295358984955001340333405752566696684659998816105508473839565045643469, 48894849136457322192396479568832209219366859965819284490038406769790383099440288691838618732412222670603151361815454680930664559653595127811643672882477421207209601157568548375218757457945012595023808914427564571086794205060496754472022851209697290233758322792545606219509459817826092022063251201804153059812999385118467573387577718608188079119243562390650123436196113638638705563442099904994751673698263854606153297492746727966990525337260379520357545224420976207209058716521044960102986555821089650341282125066347384763776362237068340115089565390050542173649471476299760751253410195318571587740253309817861023829440367670773177243716141896022747991617765819016819941298881412612634757869662091712747960078002809496438274290906202967651196616516671134444685841888988948866662720351694912798550152144897]
;


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

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

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