The Greek mathematician Euclid may very well have proved, circa 300 BCE, that there are infinitely many prime numbers. But it was the British mathematician Christian Lawson-Perfect who, more recently, devised the computer game “Is this prime?”
Launched five years ago, the game surpassed three million tries on July 16—or, more to the point, it hit run 2,999,999—after a Hacker News post generated a surge of about 100,000 attempts.
The aim of the game is to sort as many numbers as possible into “prime” or “not prime” in 60 seconds (as Lawson-Perfect originally described it on The Aperiodical, a mathematics blog of which he’s a founder and editor).
A prime number is a whole number with precisely two divisors, 1 and itself.
“It’s very simple, but infuriatingly difficult,” says Lawson-Perfect, who works in the e-learning unit in Newcastle University’s School of Mathematics and Statistics. He created the game in his spare time, but it’s proved useful on the job: Lawson-Perfect writes e-assessment software (systems that evaluate learning). “The system I make is designed to randomly generate a maths question, and take an answer from the student, which it automatically marks and gives feedback on,” he says. “You could view the primes game as a kind of assessment”—he’s used it when doing outreach sessions in schools.
He made the game slightly easier with keyboard shortcuts—the y and n keys click the corresponding yes-no buttons on the screen—in order to save mouse-moving time.
Give it a whirl:
Primality-checking algorithms
Prime numbers have practical utility in computing—such as with error-correcting codes and encryption. But while prime factorization is hard (hence its value in encryption), primality checking is easier, if tricky. The Fields Medal–winning German mathematician Alexander Grothendieck infamously mistook 57 for prime (the “Grothendieck prime”). When Lawson-Perfect analyzed data from the game, he found that various numbers exhibited a certain “Grothendieckyness.” The number most often mistaken for a prime was 51, followed by 57, 87, 91, 119, and 133—Lawson-Perfect’s nemesis (he also devised a handy primality-checking service: https://isthisprime.com/2).
The most minimalistic algorithm for checking a number’s primeness is trial division—divide the number by every number up to its square root (the product of two numbers greater than the square root would be greater than the number in question).
However, this naïve method is not very efficient, and neither are some other techniques devised over the centuries—as the German mathematician Carl Friedrich Gauss observed in 1801, they “require intolerable labor even for the most indefatigable calculator.”
The algorithm Lawson-Perfect coded up for the game is called the Miller-Rabin primality test (which builds on a very efficient but not ironclad 17th-century method, “Fermat’s little theorem”). The Miller-Rabin test works surprisingly well. As far as Lawson-Perfect is concerned, it’s “basically magic”—“I don’t really understand how it works, but I’m confident I could if I spent the time to look at it more deeply,” he says.
Since the test uses randomness, it produces a probabilistic result. Which means that sometimes the test lies. “There is a chance of uncovering an imposter, a composite number that is trying to pass as prime,” says Carl Pomerance, a mathematician at Dartmouth College and coauthor of the book Prime Numbers: A Computational Perspective. The chances of an imposter slipping through the algorithm’s clever checking mechanism are maybe one in a trillion, though, so the test is “pretty safe.”
But as far as clever primality checking algorithms go, the Miller-Rabin test is “the tip of the iceberg,” says Pomerance. Notably, 19 years ago, three computer scientists—Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, all at the Indian Institute of Technology Kanpur—announced the AKS primality test (again building upon Fermat’s method), which finally provided a test for unequivocally proving that a number is prime, with no randomization and (theoretically, at least) with impressive speed. Alas, fast in theory doesn’t always translate to fast in real life, so the AKS test isn’t useful for practical purposes.
The unofficial world record
But practicality isn’t always the point. Occasionally Lawson-Perfect receives email from people keen to share their high scores in the game. Recently a player reported 60 primes in 60 seconds, but the record is more likely 127. (Lawson-Perfect doesn’t track high scores; he knows there are some cheaters, with computer-aided attempts that produce spikes in the data.)
The 127 score was achieved by Ravi Fernando, a mathematics graduate student at the University of California, Berkeley, who posted the result in July 2020. It’s still his personal best and, he reckons, the “unofficial world record.”
Since last summer, Fernando hasn’t played the game much with the default settings, but he has tried with customized settings, selecting for larger numbers and allowing longer time limits—he scored 240 with a five-minute limit. “Which took a lot of guesswork, because the numbers got into the high four-digit range and I’ve only ever memorized primes up to the low 3,000s,” he says. “I suppose some would argue even that is excessive.”
Fernando’s research is in algebraic geometry, which involves primes to some extent. But, he says, “my research has more to do with why I stopped playing the game than why I started” (he started his PhD in 2014). Plus, he figures 127 would be very hard to beat. And, he says, “it just feels right to stop at a prime-number record.”
