Prime Hunting in the Spare Cycles

After much time, my in-progress National Egg Day Challenge tasks for the 321 Prime Search (LLR) have finally finished up. The project is a continuation of Paul Underwood’s work looking for primes of the form \(3 \cdot 2^{n} - 1\) (and its companion \(3 \cdot 2^{n} + 1\)) — the “3…2…1” that gives the search its name. These are tested with LLR, the workhorse deterministic test for numbers of the form \(k \cdot 2^{n} \pm 1\), which is exactly why this family is such a comfortable target for a distributed effort like PrimeGrid: the arithmetic is heavy, but it is also embarrassingly parallel.

I did not take part in the World Snake Day challenge, but I do plan on participating in the Perseid Meteor Shower Challenge in mid-August (more on that at the end). I haven’t spent much time focusing on prime searches lately, as we’ve moved our family from Texas to Omaha, Nebraska. We’ve been settling in, finally found us a rent house, and we’ll be heading back to Texas to collect more of our stuff in a few short weeks. Prime hunting, it turns out, is a wonderfully low-maintenance hobby: the machines keep working through the boxes and the packing tape whether I’m paying attention or not.

In the meantime, I’ve been running through a few projects I’d like to highlight. I’ve yet to personally discover either a prime or an arithmetic progression. I have double-checked an arithmetic progression — a genuinely useful contribution, since every headline discovery needs independent confirmation before it counts — but verifying someone else’s find, satisfying as it is, hasn’t quite scratched the “discovery” itch I’m longing for.

AP27

One of the searches I’ve spent spare cycles on is the AP27 search. This project searches for (and double-checks) long arithmetic progressions of primes. An arithmetic progression is a sequence of numbers with a common difference between any two successive terms. For example, the sequence

3,\; 5,\; 7,\; 9,\; 11,\; 13,\; 15

is an arithmetic progression with a common difference of \(2\).

An arithmetic progression of primes is a sequence of primes with a common difference between any two successive terms. For example,

3,\; 7,\; 11

is an arithmetic progression of \(3\) primes with a common difference of \(4\).

Why 27? The Green–Tao theorem (2004) guarantees that arbitrarily long arithmetic progressions of primes exist — but it is spectacularly non-constructive, telling us nothing about where to look. AP27 is the concrete, brute-force complement to that abstract promise: it hunts for progressions of exactly \(27\) primes, the longest length anyone has managed to exhibit. Each term has the shape \(a + n \cdot d\) for \(n = 0, 1, \ldots, 26\), and the common difference \(d\) is necessarily a multiple of every prime up to \(23\) (i.e. of \(23\# = 223{,}092{,}870\)), which is what makes the candidates so sparse and the search so expensive.

CPS (Compositorial Prime Search)

Another one I’ve been feeding cycles to is the Compositorial Prime Search, one of PrimeGrid’s newer subprojects. Where a factorial \(n!\) is the product of every positive integer up to \(n\), and a primorial \(n\#\) is the product of every prime up to \(n\), a compositorial is what you get from the numbers left over — the product of every composite up to \(n\).

Compositorial The compositorial of \(n\) is the product of all composite numbers \(\le n\). Equivalently, it is the factorial divided by the primorial:

\frac{n!}{n\#}

For instance, \(9! / 9\# = 4 \cdot 6 \cdot 8 \cdot 9 = 1728\). A compositorial prime is a prime of the form \(\dfrac{n!}{n\#} \pm 1\).

The search looks for primes of the form \(\tfrac{n!}{n\#} \pm 1\), which sit in the same intellectual neighborhood as factorial and primorial primes but are studied far less. There’s a lovely bit of trivia hiding in here: because \(281\) is prime, dividing it out changes nothing, so \(280!/280\# \pm 1\) and \(281!/281\# \pm 1\) are the same pair of numbers — and that pair happens to be twin primes. (For the tidy formal definition, the Prime Pages’ glossary entry on compositorials is worth a look.)

Cullen/Woodall Prime Search

Rounding out the rotation is the Generalized Cullen/Woodall Prime Search. These are two closely related families named for the clergyman-mathematician James Cullen, who studied them in 1905, and for Cunningham and Woodall, who took up the mirror-image case in 1917.

Cullen and Woodall numbers A Cullen number has the form \(n \cdot 2^{n} + 1\); a Woodall number is its near-twin \(n \cdot 2^{n} - 1\). The generalized versions swap the base \(2\) for an arbitrary base \(b\), giving \(n \cdot b^{n} + 1\) and \(n \cdot b^{n} - 1\).

Cullen primes are famously scarce — despite there being infinitely many candidates, only a couple dozen are known — which is exactly the sort of needle-in-a-haystack scarcity that makes them fun to chase. PrimeGrid has been extraordinarily good at it: the project holds both the largest known Cullen prime, \(6679881 \cdot 2^{6679881} + 1\), and the largest known Woodall prime, \(8508301 \cdot 2^{17016603} - 1\), among other records. Contributing here means you’re throwing tasks at the same well-tuned machinery that produced million-digit results. (The PrimeGrid wiki keeps a running history of the finds.)

Looking ahead: the Perseids

So why am I excited for the Perseid Meteor Shower Challenge in particular? Partly it’s the timing. The Perseids are the best-known meteor shower of the year — debris shed by comet 109P/Swift–Tuttle, burning up in the atmosphere at its August peak and putting on a show of dozens of meteors an hour under a dark sky. Nebraska, as it happens, has considerably darker skies than the Houston outskirts I just left, so I’m hoping to watch the real thing overhead while my machines chase primes in its honor down in the basement.

There’s something fitting about the pairing. A meteor shower is a recurrence you can predict to the day but never quite the moment — you know the Perseids are coming, you just don’t know which streak will be the bright one. Prime hunting has the same texture. You know the primes are out there, the theorems promise it, and yet you can’t say which task in the queue will be the one that lights up. I’ll take my chances at both this August.