/
larger_fermat_from_fermat_with_variations.sf
100 lines (69 loc) · 16.6 KB
/
larger_fermat_from_fermat_with_variations.sf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#!/usr/bin/ruby
# Generate larger Fermat base-2 pseudoprimes from a set of Fermat base-2 pseudoprimes.
# Algorithm:
# 1) Let n be a Fermat base-2 pseudoprime and L = lcm({znorder(2, p)}), where p are primes p|n.
# 2) Let d be the positive divisors of (n-1)/L.
# 3) If p = d*L+1 is prime and p does not divide n, then n*p is a Fermat base-2 pseudoprime.
#var z = 8360879247062142072476242452391089552717501127905
var prefix = 3*5*17*23*29
#var prefix = [3, 5, 17, 23, 29, 43, 53, 89].prod
#var prefix = [3, 5, 17, 23, 29, 53, 83, 89].prod
#var prefix = [3, 5, 17, 23, 29, 53, 83, 89, 113, 257, 353, 449].prod
func non_smooth_pomerance_condition(p) { # weaker condition
# p == 3 (mod 8) and (5/p) = -1
is_congruent(p, 3, 8) && (kronecker(5, p) == -1) &&
# (p-1)/2 and (p+1)/4 are squarefree
is_squarefree((p-1)/2) && is_squarefree((p+1)/4) &&
# all factors q of (p-1)/2 are q == 1 (mod 4)
factor((p-1)/2).all { |q|
is_congruent(q, 1, 4)
} &&
# all factors q of (p+1)/4 are q == 3 (mod 4)
factor((p+1)/4).all {|q|
is_congruent(q, 3, 4)
}
}
var psp = [
#3, 27, 83, 123, 227, 563, 707, 803, 843, 867, 923, 1083, 1203, 1227, 1283, 1323, 1467, 1523, 2067, 2147, 2187, 2387, 2427, 2523, 2603, 2723, 2763, 2867, 2907, 3243, 3867, 3947, 4163, 4227, 4307, 4323, 4347, 4547, 4563, 4683, 4707, 5163, 5243, 5267, 5427, 5603, 5627, 5883, 5907, 5987, 6003, 6123, 6243, 6267, 6507, 6563, 7067, 7083, 7187, 7347, 7467, 7587, 7763, 7787, 7923, 7947, 8043, 8307, 8403, 8523, 8843, 8987, 9147, 9243, 9267, 9443, 9867, 9987, 10203, 10307, 10427, 10563, 10643, 10667, 10827, 10883, 11003, 11027, 11043, 11163, 11403, 11603, 11867, 11883, 12227, 12267, 12683, 12747, 12963, 13043
#3, 83, 227, 563, 1283, 1523, 3947, 4547, 5987, 6563, 7187, 10427, 10667, 10883, 11003, 11027, 11867, 12227, 13043, 14243, 15683, 16187, 17483, 18947, 21107, 22907, 23627, 24923, 27803, 28163, 28643, 29363, 29867, 30467, 31547, 33203, 33827, 39107, 39827, 40763, 40883, 41243, 42467, 43427, 44867, 47963, 48947, 49307, 50627, 53003, 53147, 54347, 54563, 55667, 57587, 58043, 61283, 61547, 62003, 64283, 65027, 65867, 66107, 67307, 67763, 70067, 71843, 73883, 74027, 74507, 76403, 77747, 79907, 81563, 81707, 82883, 83243, 84443, 84467, 84947, 85523, 86027, 86627, 87323, 91283, 92243, 92363, 94547, 95027, 98867, 99707, 101027, 101603, 105683, 106907, 108203, 108707, 108803, 111467, 114827
#561, 645, 1905, 4371, 8481, 12801, 18705, 23001, 25761, 33153, 55245, 62745, 72885, 87249, 88561, 129921, 154101, 157641, 206601, 212421, 215265, 289941, 332949, 427233, 451905, 526593, 656601, 769757, 831405, 915981
#341, 561, 645, 18705, 2113665, 2882265, 81722145, 9234602385, 19154790699045, 43913624518905, 56123513337585, 162522591775545, 221776809518265, 3274782926266545, 4788772759754985, 38353281032877674865, 2638294879881771254145, 24773130788808935997465, 429388072625313108651345, 633708839387221385771985, 4426632427184293146004185, 30289748358904212366572385, 728017010426459878356936705, 34742187522900518220477982065, 296874628838164374175009735905, 282385466973939051351462060010785, 303874597856107607075523212740305, 95232935093163427870007414104051665, 3470207934739664512679701940114447720865, 35681625351759414447784656906886402710161726145, 18324199296528369643710689094829325758885303308048705, 3521782835397676946933688469202532605577443098683804760065, 4480869812756224982980361246336523683775981809514868335105
#561, 62745, 576480525985, 1886616373665, 3193231538989185, 11947816523586945, 101817952350880305, 171800042106877185
64075459460541239985, 14370921672011352376545, 100724996094964745183793345, 782779975977186433711807077553665, 71929175436933507317150019779789505, 871005264581548962932418919531990803260747265, 3316648905936338849447649810333831326868806545665, 610012201694720081796846702960249688144417680786846465
#141934960805533535384100259905, 6313931944389140773570151226945, 21481714221246334566521324297985, 362737226440313288709795480294465, 2609668563371076823446624111609234945, 39823778710699695742841310585748767105, 91517623383064245561364437489760682145, 283437449706067209889983933178767178305, 315102184724416411798661346600291716865, 487954732492026166035814706202314376705, 499412475213573176738355575538562510785, 1660636522047150213680847648152705371905, 1667290021770201095403065629700606750145, 24496848009559651796239676018610941626785, 73297250063765486245716204161838451864065, 31214532012520383045838858739096429870040705, 125365126527183302043148011968823435306857985, 189113722193582469015226874182815207467976705, 196815537559265035209874062742063577420856705, 214602304120888814092063010092195938453592065, 871005264581548962932418919531990803260747265, 78608978003846049041116965738897583982829325185, 406402829025353014759868508514893182061635216385, 1054353771375531219864416131622474190655479560385, 1495802867015723237589839615092213310803537834305, 2497529342332924877105134171746311085591402630465, 8321395327031499581392144057169057667676851380865, 16163138937411407201730795835385583884472576023745, 19944291043277491221878400955113092258507813067585, 64969883450324971076303393673011703445483161551745, 67313152631028760521480057555329912464497126382785, 74875990602425226938138664024259158432269224416705, 75989686810836033659430630396794739057812803595265, 438550573193178260751440867754887273727516317214465, 533076975052547554562094771803380614669259691657985, 6476034191965725664738875807983686448327824830485505, 41874469252684939188766205446627396186239168839365185, 48379566508488575622055850581588165632009391383215745, 59814998665432229834089744101334010488805635671365505, 72057216387777032608301187065391363788323269794759745, 411080929033363473555391879524806756034108137877793665, 610012201694720081796846702960249688144417680786846465, 1018329989576989704159754753835889677652405111555820545, 1027749515814195197950870615261518477976512598053404865, 1089308277895899597186417596452273942827827801935128705, 6792141007930247659612580831051940405232245489721132545, 7678739531271742330943794118368350987916932488808614145, 18862600423988271678875644986362750911465679136559134465, 29804948800058862908801313691702223480620573198093490385, 71637839226104625568428039749667176822512021882103384385, 73257149758147750501240531736307749308900399315221437505, 74649323981476700646735560483727039302457914252915024385, 131393938060059348352532655132697448960788060630502806785, 147722431492705339415781997425542771343697631011575451905, 159794689707372355333060022641622475669953737003517035905, 273144095679252939235857927245653370241323758698067030785, 301665440857953949041553259401389093093907522977903685185, 1172594855911332483974102491005975474562533545673609081345, 4168306949109111474379686622906580020615952735919579025665, 5349457805698512307106674655065437128438739335693225480385, 7583190872114539873321060125323684618509072354028159123265, 10283584008448773696475907793170493467187054108119687416065, 12234418303749373766457825700620527121617068058319432387585, 19810051926806549133247526622166712749924876567141948419585, 31181864586874200535646254647554630886806514113047859293185, 58772050807386648865843953171910036379257828942591085045505, 79615102993580263509479106446502418762547606112620185896705, 82635378868788575647430064182378545917770837975071035716865, 89435572021639193230723806578408893095083926585853507745345, 103461538776511821408206095140694645146310038396156492100545, 165502573617193579886078524884554371013787876466850820614145, 189077537770124861971835596817558772196854831488333103585345, 267784959963229866373534534278260976898219467353932511749185, 369070392893516565676954743410549284718528476924103461811265, 2849415592287421817408189356341963620880286613378173462928385, 8407202972124872375256931092471885668310030843991793216491905, 10649934519495512281862244386450879723780037980908499987548545, 34863998958891679307591791000688445434120146942577693602521345, 56511588686677123690238435995851357647525489518073167567656705, 58109424498388083084293446151725669510763856247238506839632385, 109400466503635187778688237536910752705181679671725472176533505, 131744238386784089467706889102713791921861242300675392358990945, 177522069189633774624742092488092110494776424024695013968133505, 463149379463251167706230703520995680069543921166639491398457345, 1690699446901876059668610579970439442290871886615097427974814465, 2019182716058354869029483021309602484127300150911463821791638785, 2845358328636614328617082131255054540223949221002124433109986305, 2963658210542356083852877246926416492931527804540089510269883905, 3375515690139528135588762816250286539261957483264055488240734465, 14701083488299057530174696885922722686956286485260401577115414785, 34876211029082329247213569555171852240834666838025652465732381185, 92912938629279819547534342645052548497217920713200285549935083265, 189340493048741310917683298328059020081147484104707189207601179585, 220258496540970105839863316321479368440458633091652250627182550785, 3532948147497062130419641306615234126132368249181291021381005926145, 5422804594921492404657864642128249347547602758471495039128383048065, 71967245196653338257378864734797608168672816153312963139871238665985, 92416232280435197831507380648275752039856138377924393874407818709505, 129959381219943649417033775959204959948797179242551459265680758859265, 158691907814457458479220201033582552840277423788671901979418171299585, 240154930013548185213396478754207126289092989564306489550025702395745, 2822536379201547782324198756261456747733576956713972970933683778969985, 7062833437200724142430664017877308496583276362473698642553317283474945, 46009993464351973747087455663482348080143005689116838928720068417823745, 155028067161627317530854052699444297997729264222942234687358807669181185, 22321294006753093794484119100782564881584237146952694846489144434824034305, 26323146142093761386080652469589506558048968348929832552142387819284363265, 644811775887535379664225513644980219319376317839497786625735944865592422785, 2320857066303242081875251854377026657518838750281130938639058373547664210945, 3975013805230187223393382482115938401564721846649947371792471394797770697985, 19666546275088335320957353962363201658812107005039715284928928608628170883585, 247268394706429287667926073879906993323506152529131362077041417598952609718785, 260349946905396900671119543882338184521094086965438750470975350786567337602945, 321030150905393790929751720043602006651739765349595158023943724894346115208705, 265254290756066930358119577715591455268521886989391944998212913199131074729078785, 1283186592486556731274818824677271745370779905816725683274659717405002608404148545, 2853450403236152332571821875265293508017495635204070217869999840422343584089739265, 7041424862546629180270002300894703395460587301981890560013629428631147034861539505, 10314769048017202862487190022261078137366617506364556874576731255559303133731265345, 11741457044150231137356174490544808074004327146682132288353157271768338063142288065, 19948738964527549499432007591778845447137932958457586625953063419475941273954097665, 997362021092818360309701053766942989875327615784875878312033397630934509999319468865, 10942279974204381948892416578336502353546209899163112324958466194102531779567054514945, 43542041386413044866032152197340430554853469459883291810228230406621749533949125497985, 61751285336040585295804391670071058142224865543324607243406589162503580666870926270465, 206506498518895650199577226124316092776953187049631892229044263107601141847713087538945, 382314270322310985139418831028955559235551077239363319937510690579825910692881422216705, 1692492088492238622532768569558090666689925078386295740708067178336619326186090793391105, 72148620605333310080719701812041760839024918297692839329815300886091224428394819515628545, 278162906898013748642772019172998608839057854602841254854175736240572851175099616062424065, 546231056648299309945879864873067527148520665055555595450356965014516409862017473033401345, 772459017179480479061611372132330246001039753130436193419524315193543873326133868681083905, 23016037591494880781207254677674405791538920089036061003925025850757168330033146229133479745, 2046678691220067222232384272594581706278851862800679089311751714768274691336039178249916698305, 15076244937897319383799036175429336548625369631595367899653198961989759434810928251355411574785, 72664438888083820643819682976576299583820992006550380566219911049269157831865133237087695622145, 369003864634310951251471583928101781391289349473480615361557117731115260969451004130994432230785, 9234108247613254525958449555178000383435906299253351774259045697386203488173058608909832628390785, 50288615560869993778808557399593955835579110574835306045039369638803685072626967951165243647931265, 54772208597990407430395018479557528859948250022718336556935666676225482342335045521290671839328385, 967037403232220731074074563038316755517610240570658812669537184604036430235566311331012838883641380865, 158187160409249161202798539163939228646964656295329913967778296913812576561852899807747016936421334492545, 7038527880875688243187405968342025621116861985452524313988100597854993262728273899976246451177104712146650851265, 9487965179774418042579206665231099348342080404211786655942396097049199839003663190769472893046724925469675490305, 14729027643613358325569388710368738033131494158337086811030693058208320405382207088349673589587156761538569200950785, 313054317133431867433948270450557453657381719414933829382581152745865152447507981090031656692076600547642476751365897345, 3717244910717158061241869794170130224455174443632345624307057397938775397436321031917968743482485623000552386373033202447105, 37839385943068863406967633413004957540054532539686888463944906014566240419460804270776358938980032660929917901837033235462145, 77921634020287997200599818673275408550456503578432198979868015119378470768178479816088971759820118556438222249261837640526049815870465, 41604760897693331902470165821292362461433951708063322154567188228941668682983586385358489704603458398732060344251877309069575573157372480292819346023961831997147106037750301707265
#537329970884826078063105, 5981802520294676451270038145, 141934960805533535384100259905, 2609668563371076823446624111609234945, 1660636522047150213680847648152705371905, 78608978003846049041116965738897583982829325185, 1495802867015723237589839615092213310803537834305, 74649323981476700646735560483727039302457914252915024385, 12234418303749373766457825700620527121617068058319432387585, 165502573617193579886078524884554371013787876466850820614145, 14701083488299057530174696885922722686956286485260401577115414785, 321030150905393790929751720043602006651739765349595158023943724894346115208705, 41604760897693331902470165821292362461433951708063322154567188228941668682983586385358489704603458398732060344251877309069575573157372480292819346023961831997147106037750301707265
#3470207934739664512679701940114447720865
#177467, 381443, 598187, 365147, 472643, 42083, 112067, 73883, 123323, 5003, 129083, 66587, 54323, 203627, 54347, 265163, 121403, 129443, 122267, 22283, 57203, 78203, 9803, 315083, 29867, 609443, 16763, 411347, 40427, 710987, 24923, 40763, 6563, 84347, 22907, 134507, 5987, 35747, 707027, 11867, 19403, 10427, 198827, 281867, 124067, 122363, 321947, 57347, 192323, 67307, 178187, 227147, 281243, 11027, 104003, 25667, 479027, 41243, 455627, 49307
#15841, 29341, 52633, 252601, 314821, 1909001, 3581761, 4335241, 5049001, 5310721, 5444489, 15247621, 29111881, 35703361, 36765901, 38624041, 53711113, 68154001, 99036001, 101649241, 104852881, 115039081, 133800661, 161035057, 172290241, 214852609, 238244041, 299736181
#1729
#4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100
].uniq.sort
for z in (psp) {
var arr = [
z.divisors(1e7).grep { is_coprime(_, prefix) }.map { z/_ }...
#z.factor.grep{ is_coprime(_, prefix) }.combinations(2).map{.prod}.map{z / _}...
].uniq
for n in (arr) {
#abundancy(n) > 1.9 || next
#n.len < 100 || next
var L = lambda(n)
#var L = n.factor.lcm {|p| znorder(2, p) }
#var L = n.factor.gcd{.dec}
#var L = znorder(2, n)
#var L = lcm(znorder(3, n), znorder(2, n))
#var L = lambda(n)
#sigma0((n-1)/L) <= 1e4 || next
for d in (divisors((n-1)/L, 1e7)) {
var p = (L*d + 1)
next if (n%p == 0)
p.len < 60 || next
p.is_prime || next
#non_smooth_pomerance_condition(p) || next
if (is_pseudoprime(n*p)) {
say n*p
#arr << n*p
arr << n*p if (len(n*p) <= 100)
}
}
}
}