Commissioned for this museum · after a Perl idiom widely circulated in the late 1990s

Primes, By Regular Expression

JavaScript·1998·15 lines·495 bytes

// Primality testing with a regular expression.
//
// The number n becomes a string of n ones. The pattern then asks whether
// that string can be cut into two-or-more equal groups of two-or-more —
// which is exactly the question of whether n has a non-trivial factor.
const composite = /^1?$|^(11+?)\1+$/;

const isPrime = (n) => !composite.test("1".repeat(n));

const primes = [];
for (let n = 2; primes.length < 12; n++) {
	if (isPrime(n)) primes.push(n);
}

console.log(primes.join(" "));

Curator’s note

Regular expressions famously cannot count, and this one decides primality. Both statements are true, and the gap between them is the exhibit.

The move is to stop asking about numbers. n is turned into a string of n ones, so arithmetic becomes geometry: a number is now a length, and asking whether it factors is asking whether that length can be laid out as a rectangle. (11+?)\1+ says *some run of two or more ones, repeated one or more further times* — a group of size at least two, occurring at least twice. A string of ones matches exactly when its length is composite. The pattern tests for composites; primality is what is left when it fails.

^1?$ handles the two numbers that always need handling separately: zero and one are not prime and are not composite either, so they are matched explicitly rather than reasoned about.

The ? in 11+? is the interesting character. It makes the group lazy, so the engine tries the smallest factor first. Greedy would find the same answers by a slower route — this is a hint about search order, not about meaning.

And the honest part: this cheats. It is not a regular expression in the formal sense at all. The backreference \1 is precisely the feature that takes these engines out of the regular languages, which is why a textbook can prove no regular expression does this while the line above plainly does. What made it famous is not that it is efficient — it is spectacularly not, running in time exponential in the digits of n — but that it works at all.