Around 300 BC, the Greek mathematician Euclid probably proved that there are infinitely many prime numbers. But the British mathematician Christian Lawson-Perfect recently designed a computer game”Is this a prime number?“
Launched five years ago, the game surpassed 3 million attempts on July 16, or more precisely, it reached 2,999,999 after a period of time. Hacker News Post There was a surge of approximately 100,000 attempts.
The goal of the game is to classify as many numbers as possible as “prime numbers” or “non-prime numbers” within 60 seconds (such as Lawson-Perfect’s original description it is at Non-periodicl, a math blog, he is the founder and editor of the blog).
A prime number is an integer with exactly two divisors, 1 and itself.
“It’s very simple, but very difficult,” said Lawson-Perfect, who works in the e-learning department of the School of Mathematics and Statistics at Newcastle University. He created this game in his spare time, but it turns out to be useful in his work: Lawson-Perfect writes electronic assessment software (a system for assessing learning). “The system I made is designed to randomly generate a math question and get the answer from the students, it will automatically mark and give feedback,” he said. “You can think of a prime number game as an evaluation”-he used it in school outreach activities.
In order to save mouse movement time, he uses keyboard shortcuts to make the game easier-click the corresponding yes/no buttons on the screen with the y and n keys.
Give it a try:
Primality check algorithm
Prime numbers have practical value in calculations-such as error correction codes and encryption. However, although prime number decomposition is difficult (so it has value in encryption), prime number checking is easier, even if it is tricky.Fields Medal winner German mathematician Alexander Grothendieck Notorious misunderstanding 57 It is a prime number (“Grothendieck prime number”).When Lawson is perfect Analyze game data, He found that various numbers showed a kind of “Grotendik”. The number most often mistaken for prime numbers is 51, followed by 57, 87, 91, 119 and 133-the nemesis of Lawson-Perfect (he also designed a convenient prime number check service: https://isthisprime.com/2).
The simplest algorithm to check the prime number of a number is trial division-divide the number by each number until its square root (the product of two numbers greater than the square root will be greater than the number in question).
However, this naive approach is not very effective, and other techniques have not been devised for centuries-as the German mathematician Karl Friedrich Gauss observed in 1801, they “even for The most tireless calculator also requires unbearable labor.”
The Lawson-Perfect algorithm written for the game is called the Miller-Rabin primality test (it is based on a very effective but not ironclad 17th century method,”Fermat’s Little Theorem“). The results of the Miller-Rabin test are surprisingly good. As far as Lawson-Perfect is concerned, it is “basically magical”-“I don’t really understand how it works, but I believe if I take the time to go deeper Study it carefully, I can,” he said.
Because the test uses randomness, it produces probabilistic results. This means that sometimes the test will lie. “It is possible to find an imposter, a composite number that is trying to pass as a prime number,” said Karl Pomeranz, a mathematician at Dartmouth College and co-author of the book Prime numbers: Calculate the angle of viewHowever, the probability of an imposter passing through a clever algorithmic checking mechanism may be one in a trillion, so the test is “very safe”.
But in terms of clever primality checking algorithms, the Miller-Rabin test is just “the tip of the iceberg,” Pomerance said.It is worth noting that 19 years ago, three computer scientists from the Kanpur Institute of Technology in India-Manindra Agrawal, Neeraj Kayal and Nitin Saxena-announced AKS primality test (Based on Fermat’s method again), it finally provides a test that can clearly prove that a number is prime, not randomized, and (at least theoretically) surprisingly fast. Alas, theoretically fast does not always translate into real-life fast, so the AKS test is useless for practical purposes.
Unofficial world record
But practicality is not always the point. Sometimes Lawson-Perfect receives emails from people who are keen to share their high scores in the game. A player recently reported 60 prime numbers within 60 seconds, but the record is more likely to be 127. (Lawson-Perfect does not track high scores; he knows that there are some cheaters, and computer-assisted attempts can produce spikes in the data.)
127 points were awarded by Ravi Fernando, a mathematics graduate student at the University of California, Berkeley. Results announced in July 2020. This is still his personal best, and he considers this to be an “unofficial world record.”
Since last summer, Fernando hasn’t played too many games under the default settings, but he tried custom settings, choosing larger numbers and allowing a longer time limit-he scored 240 under the 5-minute limit. “This requires a lot of guesswork, because the numbers fall into the upper four-digit range, and I only remember prime numbers as low as 3,000,” he said. “I think some people will even argue that this is too much.”
Fernando’s research is algebraic geometry, which involves prime numbers to a certain extent. However, he said, “My research is more about why I stopped playing games rather than why I started playing games” (he started his PhD in 2014). In addition, he believes that 127 is difficult to defeat. And, he said, “It feels right to stay on the prime number record.”