-
Notifications
You must be signed in to change notification settings - Fork 0
/
fermat_p==3_mod_80_db.pl
417 lines (394 loc) · 13.2 KB
/
fermat_p==3_mod_80_db.pl
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
#!/usr/bin/perl
# Let p_1..p_k be distinct prime numbers and let n = p_1 * ... p_k.
# If the following conditions hold:
# a) k == 1 (mod 4) or k == 3 (mod 4)
# b) p_i == 3 (mod 80) for every i in {1..k}.
# c) (p_i-1) | (n-1) for every i in {1..k}.
# d) (p_i+1) | (n+1) for every i in {1..k}.
# Then n is a counter-example to Agrawal's conjecture.
# Carmichael numbers with all prime factors p == 3 (mod 80):
# 330468624532072027
# 1358406397003392026912594827
# 194462892367341977828363075381947
# A Fermat pseudoprime to base 2 with 5 prime factors satisyfing p == 3 (mod 80):
# 121831680646636291086639154608688151372970242384165493441043 = 120163 * 365412643 * 10977269855203 * 450068064063283 * 561608103061989523
use 5.020;
use strict;
use warnings;
use Math::GMPz;
use ntheory qw(:all);
use Math::Prime::Util::GMP;
use experimental qw(signatures);
eval { require GDBM_File };
my $cache_db = "cache/factors.db";
dbmopen(my %db, $cache_db, 0444)
or die "Can't create/access database <<$cache_db>>: $!";
my @results;
while (my ($n, $value) = each %db) {
my $rem = Math::Prime::Util::GMP::modint($n, 80);
($rem == 27) || ($rem == 3) || next;
Math::Prime::Util::GMP::is_pseudoprime($n, 2) || next;
my @factors = split(' ', $value);
if (scalar(@factors) % 2 and vecall { Math::Prime::Util::GMP::modint($_, 80) == 3 } @factors) {
push @results, Math::GMPz->new($n);
}
}
dbmclose(%db);
@results = sort { $a <=> $b } @results;
foreach my $n (@results) {
say $n;
}
__END__
# Large terms:
68435117188079800987
9045346861220750863147
70335238158892421125867
87593819813773272093547
143568240855485868765547
164853581396047908970027
243481000190529373149067
267760547914370791374667
335097805698069475078907
470361680578357464725947
522925572082528736632187
832560021348422127426667
1820034970687975620484907
2149046746349460801430267
2605157947467797996807947
3365304608236039495951387
3859353924864097020236107
4263739170243679206753787
4360728281510798266333387
7900613872696016787189547
8595345112954412159554507
11704521751549958367277627
21515574392553806900834347
28541906071781213329174507
29431237363857685816007227
33833150661360980271172507
34429703849971249127950027
36100943328465990644496427
43238240218100484201369547
50018650056282930301051147
57666364049186913724122907
59539711277327870923212187
71003662684346882190762667
84444874320158644422192427
171707422464325875666659707
175352076630428496579381067
176672022178655724505204267
221081948731696270871926027
228523370315602155990347467
264079793768034374742613387
270136290676063386556053067
482001813895761038535119227
533966734737182516824412107
560066203274245940869779547
596059132007430984588188347
615437738523352001584590187
706818890274970430908597627
801739996004369134619912107
894445412046708642512902507
1358406397003392026912594827
1536486018499606762223955307
1815321619539652382319497227
1837130267804044793751812107
2023623971222499551187256027
2619423481524457814188669387
2651791873888228770082194427
3408560627000081376639770587
3688651964985680019488420827
4081749303988487175194521387
4391047159586605999625716027
4655359269748391913551305387
4687822090078157049203939707
4813941200693026259680403467
5762886571360861608394936747
5976660612741013874144163787
6967854626910554277690123787
7561949388208160365888616107
9537445336204414055092159387
9759314949604031643356504827
10211424373781434897965039067
10626456842160791277843447067
11260257876970792445537580187
11274104579369110225450868347
12059880431783093979950989627
12189191505056700686401395547
12551094196754024921403049867
13250862924216177986720216587
15229587851188341554449842427
17222637016345201396446167707
18038503407552250665853993387
18197727922992935751648749947
18887237172079478887827208987
19470491687991007084482569467
23976880743114436461734144827
25102486204818068120581383787
25556087928963002195904211387
26877586214793730440180570907
28260047594389449657211294987
30405738236455014764072059627
32206753839720498687161984747
33946276393541598133240210987
39323404773648619691409896347
41613809868072287191858769947
42269387393663773527797627947
45381726063201413635153012267
46722900381132133533985498747
47097215087330707651150269787
47524395368130435867023008507
50178655544981494493786731867
52926825724005241779868963867
63039498314030423521426642267
70144196069941598894345272987
74495465218970377841884647067
80539013839535604667400412187
98840688110829294801402891067
105559187481858803791971361627
113889468211854482561385198187
124356070720998450755736937147
130797127166536351738398670987
132673467351775248997835724107
134565051916597463481553434667
138107551003803043541406862027
152678824206282525141363852907
162533798411310644354045772907
175634237891853205103641114267
207482761595366334653921884267
220047152103707967097522147147
223292473863558018144247048027
239439709215397066278294864187
241274292415248018981040091227
278046325191879738622053799147
286407527500073729283719401387
289090629579189923807673057547
344180551486551582621442189147
350457393954193118938048081627
353697287363995486032595122587
471869696049612105211164125467
488473581221954149139141030747
676094606135994032744383760827
749577176988878124111649022747
789987760288757621810609174107
825895112165258493827896680427
1309063472737604026836834163867
1333005715546010658798779135707
2011438193706072134526587366347
2091644105799146658205529323627
2635198530795581839200883036267
2698268508615793452681755158747
2744049657285237394380190449547
2858314843683020711670415037227
2999407457050751993383031840107
3486656945342977784275232731147
3729254181470993091190597868107
4323790077931048637049074997067
4337152602903217144146045747547
4395952000092233206483760166907
4589810969811252566116702180267
4923936964099170022827875218747
5167062603096851770111656563707
5269928298507102691486455889867
5551440642398572994697586118587
5931532300859929362677162828587
6698308804555252158866602377067
7392486814714101714348005738587
8020055409838101367610661280027
8416251237903450514903799333467
8705236063214661889238549798827
10395360055073001859500069701227
10400512181722974650313557649067
11177615882646176430262251642187
13585739431928040667999968107707
14941624360783434580315298403067
15821284354583979879248800820347
17063871452163574624071849818827
17334361425463050679308487636267
18254110716595561191226116391867
21391062724320944516838477402427
21783266194855114941625027041467
22067497585080878986240641017227
24590164743081668680873294621867
25717575862911759354809431930027
27261546377394857453758963557787
27912168181207186826086081681067
30584381350090257406561923257467
33276534739605513690592051070587
33591100158409322318627953353547
35225328892327637079553516870507
35799318224506829477121174403867
37607874227403633801327635087707
38430913622093366764535981012587
42160816133924659750814184485467
48670924289653500120090032644027
51635062785591698017010519603227
54925014586258353195676075467547
55248286671934178004267936963787
68474933133835163056391395969147
91458408296024784603898764567547
92629371670327517380545995358667
96723114302350464224055267330187
98667106058556213022561527071227
99196504799303045899264041291307
126577200747167414902299139123627
142167805304648854052568799097227
150014534289349754528191947506347
162129839319011256486903911835307
173568145669586946466122338156587
194462892367341977828363075381947
206304054386579576341643791463227
229429513691051285547355487700907
280476977578312307236053465624427
300768869523987466561946236669147
345717376986053822401713912849307
414658275351086022782355397982107
442839655570295024700970861576027
458282251188485385511385408778907
546419472269316354956578263798427
612606598789553280523019043968587
628863569813718332078636698983787
640000037564716254836036890329067
710022669285258155894084780199067
738947918193649829329769905130107
747592822470126405563625924591547
755185965886577202237505993992667
786210379368657981081111058822987
797894105629283052815217244970827
845079274754923357898882440148827
1094219379605472528291464401109227
1251862366501925028458085888089227
1345456455021991863849834333685387
1408863049077559019701009279150027
1612656512173149658186839806008267
1808495952522729686238988884752107
1881750082592741664546466488481627
1944508311495820139081874649530667
2426506221045160095747173061601627
2566012354758286283788792633730347
2742412319560898898218756902912267
2946568408002988456887449819182027
2967365938620486959145141445227307
4469121796803755539832113113728107
4538205195003463689143207571318427
4893963115775302956048297406740667
5487159270130488510568295190835387
5489862206694866351393724555420187
6727113172793111588530087835299627
7600338228772653307104492177864907
8266927603234967224161673658298427
15773525900163441781756393474200907
18690220442873831573763412305318667
25518910755983539249209123460138907
27571841024909344138702942089621787
35767515776336486441794927621359787
36020629240784273504534127669074107
43695897287642288996190843022354747
51136900301252933411702510323585627
58528991918330191797325764864970987
66592847798631095322810098574100267
83494712161500444107047218738656827
86480491452525098398572600381730267
108433543307514226302958306002244027
130180240952697495904800834240734827
133821300239684360736252644872482667
170552917495235874158626978127000107
172984810849424324762378882128710427
190396974079269426009063603932421067
232811018206485989295674832899151547
234152953348022502725277795404949787
284750126190279772046593069630281307
285153731222819008388631605358959947
300487571294121915406875103743003067
520398855012510718909216488416926027
561148536051080141365274673553230187
565809263979301739072426102457987547
599560312440201267491236428174127867
1062786977228478694479531113234998747
1112978788534539481233247602656645947
1144608868849607279387313661976888827
1463410133605023433177083762522668747
1657725999727963143759627502589518747
1733236080821264822430016026809423227
1789193964491133130497855912644047627
2077239295163783831955475810954313227
2118809348128179868095547676520693787
2270416716376876097865905317425502507
3564678402153467597009712737008591147
3817335039803602623515571575603132107
3889574700231196618950977702240482507
4611899725645331135484932892396314347
5704824848146777528756530624599705947
5840631861566338554414545306296905067
9110327195790972519806517273647708347
9948518350017479225895668647848731947
10287927036337801458583696631096261947
13155270634594728000203114097497140267
16835682706680004631856063013425950107
16979610282130799873691895318594844107
17186723157944297837317253317865099227
18161863735887497909586060895673172187
19788767953972394762060607068480717947
22671572241434885951766851351324607067
23744151985580497625531517179564645227
29857466643115284005005539122178688267
33709150280466595775751037567891185547
36950917133948538657337202740356491467
51177718298483881344103782732394787467
65467453161151866487578707790498831307
69468456685179147370864916310349146667
69925959340410012383850804820723112587
83021349313256741919945700532411320267
134417527688607330219566014114306497307
136041910606897673889118324344169062907
171709158807103345247838932669061732667
177985445353012310295551927467711280347
187152315448955632561506299668782209947
187529081735311932494084450182042115467
201252221218667500778582008333718065627
206950290600826298990927343300766066267
227802448978147070312636764065297243787
276156403408517422813558816669841928187
329787065971878801867859922230235530267
338232902333986596568237865271955017307
365807964135148271872125311645400662587
371322134240355544149847306798533548347
394174648214260169967912735545134824907
442173220927955751562626240479207542987
469001343906370045168223301796040765467
492376920895221846841896913726955086987
542803006449436961232209382250545236827
552154426609865293362856821483132735787
581284113904086154346088397068397040587
613196247538565229767563636435952707627
697880965260408905036690110028290674187
720790515074128308445793394037533193147
818648680412181200692097304025291488907
874291646625077394331037199170277848347
980807007578394453772881418272194255227
1034871069706942603225661887894535228347
1515834240327990618475399415220106382587
1809095680925910345141579827902504102267
2500253757671125742642567721287020640827
2926294517956266929540521236583644030187
4638698299713574777754341609182957016747
4671119479972759512190083808429697851867
5016401360397029998876928037054465279547
6294563838426330438958714257489083916907
6755735188355794892569938121545771785947
8083224020214903588376560879818854193947
11109042669094674473252401978626065813227
14689691478923833346996919587161707701467
16086391305527453926905019142561192320267
25427830986886285443110990874262040589787
285837430125177875337407905992480883035547
4987907302758736994622148510194614517951642187
377554215320518336098718048365615062191243733467
8455815296459309007028238231947968764699701575547
8633135194947460439082492928941395800440787220507
6677381841560475568475381858135041590681358196918347
121831680646636291086639154608688151372970242384165493441043
120051749507432728558432408124149264824699469166213421449112163
209049726214423972650644255886235335009269075962644824906422805829521876803
1286243694723516727213368443559530030349949003135449627873454306561721509603
146514041087757753829845217182294094783212145787671259314683616591865804391227