-
Notifications
You must be signed in to change notification settings - Fork 0
/
fermat_p==3_mod_80.pl
executable file
·123 lines (99 loc) · 2.76 KB
/
fermat_p==3_mod_80.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
#!/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 number with all prime factors p == 3 (mod 80):
# 330468624532072027
use 5.020;
use strict;
use warnings;
use Math::GMPz;
use ntheory qw(:all);
use experimental qw(signatures);
use Math::Prime::Util::GMP;
sub pretest ($n) {
my $rem = $n % 80;
($rem == 27 or $rem == 3) || return;
foreach my $p (5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 89, 97) {
if (Math::GMPz::Rmpz_divisible_ui_p($n, $p)) {
return;
}
}
return 1;
}
sub isok ($n) {
pretest($n) || return;
#say "Candidate: $n";
vecall { Math::GMPz->new($_) % 80 == 3 } Math::Prime::Util::GMP::factor($n);
}
my %seen;
while (<>) {
next if /^\h*#/;
/\S/ or next;
my $n = (split(' ', $_))[-1];
$n || next;
next if ($n < ~0);
next if (length($n) > 35);
Math::Prime::Util::GMP::is_strong_pseudoprime($n, 2) || next;
$n = Math::GMPz::Rmpz_init_set_str($n, 10);
if (isok($n)) {
say $n if !$seen{$n}++;
}
}
__END__
# Terms < 2^64
51962615262396907
330468624532072027
2255490055253468347
18436227497407654507
# Terms > 2^64
68435117188079800987
164853581396047908970027
522925572082528736632187
1820034970687975620484907
2605157947467797996807947
4263739170243679206753787
4360728281510798266333387
28541906071781213329174507
33833150661360980271172507
36100943328465990644496427
84444874320158644422192427
171707422464325875666659707
175352076630428496579381067
221081948731696270871926027
228523370315602155990347467
270136290676063386556053067
596059132007430984588188347
615437738523352001584590187
1536486018499606762223955307
1837130267804044793751812107
2023623971222499551187256027
2651791873888228770082194427
3408560627000081376639770587
4081749303988487175194521387
4391047159586605999625716027
4813941200693026259680403467
9759314949604031643356504827
10211424373781434897965039067
11260257876970792445537580187
12189191505056700686401395547
13250862924216177986720216587
17222637016345201396446167707
18038503407552250665853993387
23976880743114436461734144827
25556087928963002195904211387
26877586214793730440180570907
32206753839720498687161984747
41613809868072287191858769947
74495465218970377841884647067
98840688110829294801402891067
105559187481858803791971361627
132673467351775248997835724107
239439709215397066278294864187
789987760288757621810609174107
1333005715546010658798779135707
17334361425463050679308487636267