-
Notifications
You must be signed in to change notification settings - Fork 0
/
check.sf
85 lines (80 loc) · 5.81 KB
/
check.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
#!/usr/bin/ruby
# Primes p such that the greatest common divisor of 2^p+1 and 3^p+1 is composite.
# https://oeis.org/A349722
# Fun facts: let g = gcd(2^p+1, 3^p+1)
# * g must be a strong pseudoprime to base 2 and base 3
# * the multiplicative order of g modulo 2 and modulo 3 equals 2*p
# i.e.: znorder(Mod(2, g)) == znorder(Mod(3, g)) == 2*p
# * using the list of base-2 Fermat pseudoprimes below 2^64, should be possible to find some of the terms
var terms = [
2243399, 2334547, 2743723, 3932207, 4623107, 4716343, 5482423, 5993411, 7156769, 7187743, 8795167, 9026987, 9608843, 9923209, 10451599, 11362123, 11761291, 12547307, 13426667, 14882383, 15574861, 17458943, 18117991, 18308443, 18467203, 18756191, 19418123, 19811503, 20572729, 20968427, 21216751, 21772811, 23621723, 24192587, 26394847, 27517667, 27765443, 27795583, 28501727, 29222183, 29438107, 30206327, 30397363, 31949941, 32235067, 32416823, 33035027, 33570347, 33634927, 33705391, 34081471, 36609787, 37819813, 40210147, 40296163, 40475251, 40735693, 41702027, 42277927, 42531451, 42769451, 42894197, 43338203, 48141287, 48313849, 48419047, 50076109, 51784543, 52853987, 54469643, 55384831, 55736743, 56244467, 56535043, 57759607, 58821907, 58939411, 59106881, 60091763, 60110123, 60192367, 60339131, 60690691, 63267007, 63339803, 64726751, 66938323, 67103711, 68021699, 68498827, 68834387, 70097743, 72720587, 73332047, 73894687, 74954387, 75352567, 75674563, 76213603, 77343943, 77666063, 78093263, 79452463, 79764823, 80295769, 80834599, 81647551, 81742163, 82346087, 82622027, 84482327, 85263727, 85608067, 88300763, 89120807, 90118229, 90530347, 93888611, 93983023, 96233843, 98936647, 99492167, 102265307, 104468867, 109002151, 111510823, 112353203, 114383551, 114565127, 114874883, 115580323, 118369543, 120632027, 121397971, 124515563, 125686711, 126519643, 129564467, 130665427, 131309467, 131891323, 132186007, 132360427, 135864923, 136972967, 138852251, 139707367, 140145287, 141264083, 141968923, 142496323, 142943687, 143384383, 146360843, 147622367, 147819047, 151675163, 152898667, 152995267, 153281963, 154214611, 154444307, 154926727, 156729943, 158623183, 160638323, 160992131, 161142203, 162781007, 162885091, 163266281, 163499669, 164070143, 165541109, 166784687, 169785983, 171110651, 171984467, 172444507, 172546637, 174615227, 176728907, 177592847, 178186003, 178191551, 179320951, 182170763, 182259923, 184151167, 185394563, 185783231, 186397067, 187692467, 187732243, 187863647, 188187347, 188202607, 190656463, 191012651, 191870051, 193993571, 194113091, 194367827, 197536687, 199126303, 200061731, 200218283, 200550331, 200843351, 201504727, 202034291, 202333567, 203548967, 204541607, 207325543, 208423123, 210202607, 211617643, 212822111, 218981447, 227310443, 228988267, 229946707, 234002683, 238700767, 240498103, 240837607, 241930127, 242389307, 245032787, 248322367, 250544627, 250779707, 251745731, 252173707, 255264643, 255736543, 259649603, 259764623, 260670811, 268176943, 270803983, 276566051, 280717807, 281076751, 282264007, 283513963, 284535731, 291318787, 292381423, 293320507, 300066323, 308350751, 311021927, 314192927, 315193007, 316677983, 323026343, 338948063, 343907567, 345136943, 351418807, 353215243
].uniq.sort
terms.each {|p|
var g = gcd(ipow2(p) + 1, 3**p + 1)
if (g.is_composite) {
say "#{p} -- ok with g = #{g}"
}
else {
warn "Counter-example: #{p} with g = #{g}"
}
}
__END__
2243399 -- ok with g = 9421474973858971
2334547 -- ok with g = 981019829181313
2743723 -- ok with g = 1084034372016667
3932207 -- ok with g = 2226564390248467
4623107 -- ok with g = 6924890617423897
4716343 -- ok with g = 7207021062122857
5482423 -- ok with g = 5410253348534449
5993411 -- ok with g = 6465775790448577
7156769 -- ok with g = 88507024560505633
8795167 -- ok with g = 11139114872191027
9026987 -- ok with g = 11734055449745947
9608843 -- ok with g = 13295500675270747
9923209 -- ok with g = 74443378699799377
10451599 -- ok with g = 125839782501149881
11362123 -- ok with g = 18590089166530267
12547307 -- ok with g = 22670627841543067
13426667 -- ok with g = 51919312102960051
14882383 -- ok with g = 39867358812329809
17458943 -- ok with g = 54866644950426769
18117991 -- ok with g = 94539341166682843
18308443 -- ok with g = 60335835974268769
18467203 -- ok with g = 49109413030638187
18756191 -- ok with g = 151975312220886691
19418123 -- ok with g = 67871430850815649
19811503 -- ok with g = 70649217914635729
20572729 -- ok with g = 319967308185989137
20968427 -- ok with g = 79141488308642593
21216751 -- ok with g = 210670446544335553
21772811 -- ok with g = 136527927242147443
23621723 -- ok with g = 80349955547028667
24192587 -- ok with g = 84280502994147547
26394847 -- ok with g = 100323065325936307
27517667 -- ok with g = 136299960472756033
27765443 -- ok with g = 111012455630983147
27795583 -- ok with g = 111253599374491507
28501727 -- ok with g = 146222720582917393
29222183 -- ok with g = 122966781893775907
29438107 -- ok with g = 124790709582199867
30206327 -- ok with g = 131388796385843587
30397363 -- ok with g = 133055954450863627
31949941 -- ok with g = 771723841724028097
32235067 -- ok with g = 299260670555106451
32416823 -- ok with g = 151322460504024067
33035027 -- ok with g = 157149074271315787
33570347 -- ok with g = 202854276794606113
33634927 -- ok with g = 529452293915547841
33705391 -- ok with g = 204489610056712657
34081471 -- ok with g = 334525441511265643
36609787 -- ok with g = 241249772071318753
37819813 -- ok with g = 1441780963893916411
40210147 -- ok with g = 232827253939976107
40296163 -- ok with g = 233824429572134827
40475251 -- ok with g = 2359074161815791019
40735693 -- ok with g = 1672671860352326731
41702027 -- ok with g = 250424505301917787
42277927 -- ok with g = 257388929312433187
42531451 -- ok with g = 325606379880904417
42769451 -- ok with g = 329260670531152417
42894197 -- ok with g = 2185815621497585641