/
find_a12.cpp
113 lines (81 loc) · 2.7 KB
/
find_a12.cpp
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
// Compilation:
// g++ -march=native -Ofast -lgmp find_a12.cpp -o x
#include <gmp.h>
#include <iostream>
using namespace std;
typedef unsigned long long int u64;
static bool primality_pretest(u64 k) {
if (!(k % 3) || !(k % 5) || !(k % 7) || !(k % 11) ||
!(k % 13) || !(k % 17) || !(k % 19) || !(k % 23)
) {
return false;
}
return true;
}
static bool probprime(u64 k, mpz_t n) {
mpz_set_ui(n, k);
return mpz_probab_prime_p(n, 0);
}
static bool is_chernick(int n, u64 m, mpz_t z) {
u64 t = 9 * m;
for (int i = 2; i <= n - 2; i++) {
if (!primality_pretest((t << i) + 1)) {
return false;
}
}
if (!probprime(6 * m + 1, z)) {
return false;
}
if (!probprime(12 * m + 1, z)) {
return false;
}
if (!probprime(18 * m + 1, z)) {
return false;
}
for (int i = 2; i <= n - 2; i++) {
if (!probprime((t << i) + 1, z)) {
return false;
}
}
return true;
}
int main() {
mpz_t z;
mpz_inits(z, NULL);
// sanity checks (all three must be 1)
cout << is_chernick(10, 3208386195840, z) << endl;
cout << is_chernick(11, 31023586121600, z) << endl;
cout << is_chernick(11, 2138939853538560, z) << endl;
cout << "\n";
// sanity checks (all three must be 0)
cout << is_chernick(11, 3208386195840, z) << endl;
cout << is_chernick(12, 31023586121600, z) << endl;
cout << is_chernick(12, 2138939853538560, z) << endl;
cout << "\n";
u64 from = 6269000000000; // initial value of k
int n = 12;
int t = n - 4;
// Make sure we don't overflow
cout << "Test: " << (from * 5 * (1 << (n - 4)) * 9 * (1 << (n - 5)) + 1) << endl;
cout << "Test: " << (((((from * 5) << t) * 9) << (n - 5)) + 1) << endl;
// Make sure mpz works
mpz_set_ui(z, (((((from * 5) << t) * 9) << (n - 5)) + 1));
cout << "Tmpz: " << mpz_get_ui(z) << endl;
cout << "\n";
u64 multiplier = 5 << t;
// Maximum value of k is about 1563750000000 (n = 12)
// Maximum value of k is about 3127500000000 (n = 11)
// Maximum value of k is about 6255000000000 (n = 10)
// Maximum value of k is about 12510000000000 (n = 9)
for (u64 k = from ; ; k++) {
if (k % 1000000000 == 0) {
cout << "Tested up to k = " << k << " -- where largest p = " << (((((k * 5) << t) * 9) << (n - 5)) + 1) << endl;
}
u64 m = k * multiplier;
if (primality_pretest(6 * m + 1) && primality_pretest(12 * m + 1) && primality_pretest(18 * m + 1) && is_chernick(n-3, m, z)) {
cout << ":: Candidate for k = " << k << " and m = " << m << endl;
//break;
}
}
return 0;
}