searching for twin emirps and bemirps

the emirp records on my primes page all came out of the same kind of search. here is how it works.

four primes at once

a bemirp needs four large primes at once: the number, its reversal, its upside-down version and the upside-down reversal. a twin emirp needs four as well (n, n+2 and both reversals). each one alone is already rare, so almost everything gets thrown out before any real test.

candidates are a short head and tail around a long block of repeated digits. reversing or flipping that just moves the head and tail around, so one sieve in c strikes out every candidate where any of the four numbers has a small factor. survivors go to the gpu for base-3 fermat tests, and anything that passes gets an ecpp proof.

3^(N-1) mod N == 1   # probable prime, then prove it

the 1,800-digit twin emirp came from one 5-hour run on the lab server: 4.7 trillion candidates sieved, 140 million tested on the gpu, 1 hit. proving all four numbers took about 20 minutes each.

the gpu kernel

the fermat tests are modular exponentiation on 1,000 to 2,000 digit numbers, written with cgbn (nvidia's big-number library for cuda). a fermat test only ever needs base 3, and multiplying by 3 is far cheaper than a general multiply, so a base-3 specific kernel ran about 4x faster than the generic one:

# l40s, tests per second
#   1,000 digits   generic 21.9k   base-3 89.1k
#   1,230 digits   generic 13.5k   base-3 55.8k

after that the cpu sieve was the bottleneck in every search.

smallest, not largest

"smallest titanic" (titanic means at least 1,000 digits) is harder than "large", because every candidate below the answer has to be ruled out, not just one found. the smallest titanic bemirp search covered 204 billion candidates before stopping at 10^999 + 118609688181001111.

tools

• ·python drivers with resumable sqlite checkpoints, one per search type.
• ·sieves in c, called through ctypes.
• ·cuda and cgbn for fermat tests on an nvidia l40s.
• ·cm ecpp for proofs, with every certificate checked by ecpp-check.
• ·a macbook air m4, and a lab server with 32 xeon cores.