Happy Nice Mall

The Greek mathematician Euclid, circa 300 BC, may well have proved that there are infinitely many prime numbers. But more recently it was British mathematician Christian Lawson-Perfect who designed the computer game.Is this prime?”

Released five years ago, the game surpassed three million tries on July 16, or more importantly, reached 2,999,999. Hacker News post created an increase of about 100,000 attempts.

The object of the game is to rank as many numbers as “prime” or “non-prime” in 60 seconds (actually, as with Lawson-Perfect). specification on aperiodical, a math blog of which he is the founder and editor).

A prime number is an integer that has exactly two divisors, 1 and itself.

“It’s so simple, but it’s excruciatingly difficult,” says Lawson-Perfect, who works in the e-learning unit at Newcastle University’s School of Mathematics and Statistics. He created the game in his spare time, but it has proven useful at work: Lawson-Perfect writes e-assessment software (systems that evaluate learning). “The system I built is designed to generate a random math question and automatically receive an answer from the student, which he/she flags and gives feedback on,” he says. “You can see the game of primes as a kind of assessment”—he used it when he was holding outreach sessions in schools.

Made the game a bit easier with keyboard shortcuts (y and n keys clicking corresponding yes-no buttons on the screen) to save mouse movement time.

Give it a whirl:

Primality check algorithms

Prime numbers have practical benefits in computing, such as error correcting codes and encryption. However, while prime factorization is difficult (hence its value in encryption), it is easier to check for prime, if difficult. Fields Medal-winning German mathematician Alexander Grothendieck outrageously wrong 57 for prime (“Grothendieck prime”). Lawson-Perfect analyzed data from the gamefound that various numbers exhibit a certain “Grothendieckyness”. The number most often confused with prime was 51, followed by 57, 87, 91, 119, and 133 – Lawson-Perfect’s nemesis (who also designed a handy prime-checking service: https://istthisprime.com/2).

The most minimalist algorithm for checking the prime of a number is the trial part – divide the number by each number up to its square root (the product of two numbers greater than the square root will be greater than the number in question).

However, this naive method is not very efficient, and neither are other techniques developed over the centuries – as the German mathematician Carl Friedrich Gauss observed in 1801, “they require excruciating labor even for the most tireless calculator.”

The Lawson-Perfect algorithm coded for the game is called the Miller-Rabin primality test (it’s based on a very efficient but not rigid 17th century method, “Fermat’s little theorem”). The Miller-Rabin test works surprisingly well. In the case of Lawson-Perfect, it’s “basically magic”—”I don’t really understand how it works, but I’m sure I can if I take the time to look deeper into it,” he says.

Because the test uses randomness, it produces a probabilistic result. This means that sometimes the test lies. “There’s a chance of uncovering a composite number trying to beat a crook to prime,” says Carl Pomerance, a Dartmouth College mathematician and co-author of the book. Prime Numbers: A Computational Perspective. Still, the odds of a fraudster passing through the algorithm’s smart check mechanism are one in a trillion, so the test is “pretty safe”.

But Pomerance says the Miller-Rabin test is “the tip of the iceberg” when it comes to intelligent primality checking algorithms. Specifically, 19 years ago, three computer scientists (Manindra Agrawal, Neeraj Kayal and Nitin Saxena) working at the Indian Institute of Technology Kanpur AKS primality test It provided (again based on Fermat’s method) a test to finally prove conclusively that a number is prime, without randomization and (at least theoretically) with impressive speed. Unfortunately, fast in theory doesn’t always mean fast in real life, so the AKS test is not useful for practical purposes.

Unofficial world record

But practicality isn’t always the issue. Sometimes Lawson-Perfect receives emails from people who want to share their game high scores. One player recently reported 60 primes in 60 seconds, but the record is likely 127. (Lawson-Perfect doesn’t follow high scores; he knows there are some cheaters with computer-assisted attempts producing spikes in data.)

The 127 score was achieved by Ravi Fernando, a mathematics graduate student at the University of California, Berkeley. published the result in July 2020. It’s still personally the best and, according to him, the “unofficial world record”.

Since last summer, Fernando hasn’t played the game much with the default settings, but experimented with customized settings, choosing larger numbers and allowing for longer time limits – scoring 240 points with a five-minute limit. “This required a lot of guesswork, because numbers fell into the highest four-digit range, and I’ve only memorized prime numbers up to 3,000 so far,” he says. “I think some will argue that even that is excessive.”

Fernando’s research is in algebraic geometry involving prime numbers to some extent. However, “my research has more to do with why I stopped playing the game than why I started it,” he says (he started his PhD in 2014). He also thinks it would be very difficult to beat 127. And, “it feels right to stand on a prime number record,” he says.