Is 57 a prime number? Theres a game for that. – MIT Technology Review

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 16or, more to the point, it hit run 2,999,999after 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 hes a founder and editor).

A prime number is a whole number with precisely two divisors, 1 and itself.

Its very simple, but infuriatingly difficult, says Lawson-Perfect, who works in the e-learning unit in Newcastle Universitys School of Mathematics and Statistics. He created the game in his spare time, but its 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 assessmenthes used it when doing outreach sessions in schools.

He made the game slightly easier with keyboard shortcutsthe y and n keys click the corresponding yes-no buttons on the screenin order to save mouse-moving time.

Give it a whirl:

Prime numbers have practical utility in computingsuch 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 Medalwinning 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 133Lawson-Perfects nemesis (he also devised a handy primality-checking service: https://isthisprime.com/2).

The most minimalistic algorithm for checking a numbers primeness is trial divisiondivide 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 nave method is not very efficient, and neither are some other techniques devised over the centuriesas 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, Fermats little theorem). The Miller-Rabin test works surprisingly well. As far as Lawson-Perfect is concerned, its basically magicI dont really understand how it works, but Im 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 algorithms 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 scientistsManindra Agrawal, Neeraj Kayal, and Nitin Saxena, all at the Indian Institute of Technology Kanpurannounced the AKS primality test (again building upon Fermats 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 doesnt always translate to fast in real life, so the AKS test isnt useful for practical purposes.

But practicality isnt 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 doesnt 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. Its still his personal best and, he reckons, the unofficial world record.

Since last summer, Fernando hasnt played the game much with the default settings, but he has tried with customized settings, selecting for larger numbers and allowing longer time limitshe scored 240 with a five-minute limit. Which took a lot of guesswork, because the numbers got into the high four-digit range and Ive only ever memorized primes up to the low 3,000s, he says. I suppose some would argue even that is excessive.

Fernandos 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 gamethan 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.

Excerpt from:

Is 57 a prime number? Theres a game for that. - MIT Technology Review