/
pseudoprimes_of_the_form_6p+1.pl
executable file
·72 lines (58 loc) · 3.94 KB
/
pseudoprimes_of_the_form_6p+1.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
#!/usr/bin/perl
# Pseudoprimes to base 2 of the form 6p+1 such that 2^(p-1) == 1 (mod p).
# https://oeis.org/A236373
# The first 4 terms are:
# 2047, 8388607, 140737488355327, 576460752303423487
# The first four terms are A065341(1), A065341(2), A065341(7), A065341(9) and have the form 2^m-1.
# Are there terms not of this form?
use 5.020;
use strict;
use warnings;
use ntheory qw(:all);
use Math::GMPz;
my %seen;
my $t = Math::GMPz::Rmpz_init();
while (<>) {
next if /^\h*#/;
/\S/ or next;
my $n = (split(' ', $_))[-1];
$n || next;
is_pseudoprime($n, 2) || next;
($n < ((~0) >> 1))
? Math::GMPz::Rmpz_set_ui($t, $n)
: Math::GMPz::Rmpz_set_str($t, "$n", 10);
Math::GMPz::Rmpz_sub_ui($t, $t, 1);
Math::GMPz::Rmpz_divisible_ui_p($t, 6) || next;
Math::GMPz::Rmpz_divexact_ui($t, $t, 6);
if (is_pseudoprime($t, 2)) {
say $n if !$seen{$n}++;
my $t = Math::GMPz->new($n) + 1;
if (($t & ($t - 1)) != 0) {
die "\nTerm of new form found: $n\n\n";
}
}
}
__END__
2047
8388607
140737488355327
576460752303423487
9671406556917033397649407
187072209578355573530071658587684226515959365500927
766247770432944429179173513575154591809369561091801087
215679573337205118357336120696157045389097155380324579848828881993727
14821387422376473014217086081112052205218558037201992197050570753012880593911807
286687326998758938951352611912760867599570623646035140467198604923365359511060601008752319138765710819327
1174271291386916613944740298394668513687841274454159935353645485766104512557304221731849499192384351515967487
19701003098197239606139520050071806902539869635232723333974146702122860885748605305707133127442457820403313995153407
381072821083495145432323880589986121307201921712032611188861933548019011086397170424842053596617672260721060927906081896416989218663120764927
1560874275157996115690798614896583152874299071332485575429578479812685869409882810060153051531745985579913465560703311447723987839644142653145087
26187124863169134960105517574620793217733136368344518315866330944769070371237396439066160738607233257207093473020480568073738052367083144426628220715007
30191699398572330817932436647906151127335369763331523427009650401964993299137190816689013801421270140331747000246110759198164677039398341060491474011461568349195162615807
506532662216918085755909163048237445191949002959281848144001138878253517018177263964807989373425756138696031080481053366991595590260226478013534525648677207893210669360535830527
40131652080904949243476790488282231640246122763238325954424140190648896440865179612073261537762363061729301215028215161995082338334532195000669973530974432754174985283877903733762083113741475809259744657407
2757826131550993649364364103715456897804056554542556176448634698108099443712107910064330000971904293916892446775667965408323532095584366159791555750475533307061324308088589961496711008293655788792731796366049346060287
3665779701564795034165604343510379326812382614037843523768505561895816192685171732396196386025552432054958017180031964169522798176905392217656963333320266191425647911421339149090150561469309283359365121053663391676919110861662410702765924749628709797887
61501577861568104283923723841611832207865934590357532972465351809127477760976746151505184346770074671911354525161107149776344601938347976800349887747194103071045442949864673913541659442291879217725274258783458313456274137454056383441015716964266784080483319807
1031825256124346184281913642415071497107123683664299847906173259817722465931103241160971202905580445106785927721205329450942085077153682689942458942310428861149192742185556805017053745461770392681687954898849977351851617759280394021168743942904368118143630040815894527
81749619078542123485445026325988907666122803627436340899944335050228199090952768134551878266578358316619466622738124605193111060004601596343876476857746694976307432364076469310158345070361107955001481492256519126766829996241750851128887511795631888691491672345630967465671003964634890646646161407