Is this number prime? There is a game for that.

The Greek mathematician Euclid was able to prove very well, around 300 BC, that there is an infinity of prime numbers. But it was the British mathematician Christian Lawson-Perfect who more recently designed the computer game ”Is this first?

Launched five years ago, the game topped three million tries on July 16 – or, more precisely, it hit 2,999,999 – after a Message from Hacker News generated a wave of about 100,000 attempts.

The object of the game is to sort as many numbers as possible into “prime” or “non-prime” in 60 seconds (like Lawson-Perfect originally described it on The Aperiodicl, a math blog of which he is founder and editor).

A prime number is an integer with precisely two divisors, 1 and itself.

“It’s very simple, but extremely difficult,” says Lawson-Perfect, who works in the e-learning unit at the School of Mathematics and Statistics at Newcastle University. He created the game in his spare time, but it has proven to be useful on the job: Lawson-Perfect writes electronic assessment software (systems that assess learning). “The system I’m creating is designed to randomly generate a math question and take a student’s response, which they automatically grade and comment on,” he says. “You could think of the bonus game as a kind of evaluation” – he used it in awareness sessions in schools.

It 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 travel time.


Primality Check Algorithms

Prime numbers have practical uses in computing, such as with error correction codes and encryption. But while the primary factorization is difficult (hence its value in encryption), the primality checking is easier, so delicate. German mathematician winner of the Fields Medal Alexandre grothendieck notoriously confused 57 for the first (the “first of Grothendieck”). When Lawson-Perfect analyzed game data, he found that various numbers exhibited a certain “grothendieckyness”. The number most often mistaken for a prime number was 51, followed by 57, 87, 91, 119, and 133 – Lawson-Perfect’s nemesis (he also designed a handy primality checking service:

The most minimalistic algorithm for checking the primacy of a number is trial division – divide the number by each 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 naive method is not very efficient, nor are other techniques devised over the centuries – as the German mathematician Carl Friedrich Gauss observed in 1801, they “demand intolerable work even for the calculator the most. more tireless “.

The Lawson-Perfect algorithm coded for the game is called the Miller-Rabin primality test (which is based on a 17th century method that is very efficient but not foolproof, “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 sure I could if I spent the time to examine it more deeply,” says- he.

Because the test uses randomness, it produces a probabilistic result. Which means that sometimes the test is wrong. “There is a chance to discover an impostor, a composite number that tries to pass for first,” says Carl Pomerance, mathematician at Dartmouth College and co-author of the book. Prime numbers: a computational perspective. The chances of an impostor slipping through the algorithm’s intelligent verification mechanism are perhaps one in a trillion, so the test is “fairly safe”.

But when it comes to smart primality checking algorithms, the Miller-Rabin test is “the tip of the iceberg,” Pomerance explains. Notably, 19 years ago, three computer scientists – Manindra Agrawal, Neeraj Kayal and Nitin Saxena, all from the Indian Institute of Technology Kanpur – announced the AKS primality test (again relying on Fermat’s method), which ultimately provided a test to unequivocally prove that a number is prime, without randomization, and (theoretically, at least) with impressive speed. Unfortunately, fast in theory doesn’t always translate to fast in real life, so the AKS test is not useful for practical purposes.

The unofficial world record

But practicality is not always the goal. Occasionally, Lawson-Perfect receives emails from people wanting to share their high scores in the game. Recently, a player reported 60 primes in 60 seconds, but the record is more likely to be 127. (Lawson-Perfect does follow suit. not the high scores; he knows there are cheaters, with computer-assisted attempts producing spikes in the data.)

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

Since last summer, Fernando hasn’t played the game much with the default settings, but he has tried with custom settings, selecting larger numbers and allowing for longer delays – he scored 240 with a five-minute limit. “Which took a lot of guesswork, as the numbers went into the upper four-digit range and I only memorized prime numbers up to 3000,” he says. “I guess some would even say it’s overkill.”

Fernando’s research focuses on algebraic geometry, which to some extent involves prime numbers. But, he says, “my research is more about why I stopped playing the game than why I started” (he started his PhD in 2014). Plus, he thinks 127 would be very hard to beat. And, he says, “it just seems to stop at a prime number record.”

Source link

Leave a Reply

Your email address will not be published. Required fields are marked *