Er 57 et primtal? Der er et spil for det.

Fru Tech | Pixabay

Den græske matematiker Euklid kan meget vel have bevist, omkring 300 fvt., at der er uendeligt mange primtal. Men det var den britiske matematiker Christian Lawson-Perfect, der for nylig udtænkte computerspillet Er dette prime?

Spillet blev lanceret for fem år siden og oversteg tre millioner forsøg den 16. juli – eller mere til punkt, det ramte 2.999.999 – efter en Hacker News-indlæg genereret en stigning på omkring 100.000 forsøg.

Formålet med spillet er at sortere så mange tal som muligt i primetal eller ikke primtal på 60 sekunder (som Lawson-Perfect oprindeligt beskrevet den på Aperiodica l, en matematikblog, som han er grundlægger og redaktør af).

Et primtal er et helt tal med præcis to divisorer, 1 og sig selv.

Det er meget enkelt, men irriterende svært, siger Lawson-Perfect, der arbejder i e-læringsenheden på Newcastle Universitys School of Mathematics and Statistics. Han skabte spillet i sin fritid, men det har vist sig nyttigt på jobbet: Lawson-Perfect skriver e-vurderingssoftware (systemer, der evaluerer læring). Det system, jeg laver, er designet til tilfældigt at generere et matematikspørgsmål, og tage et svar fra eleven, som den automatisk markerer og giver feedback på, siger han. Du kan se prime-spillet som en slags vurdering - han har brugt det, når han laver opsøgende sessioner i skoler.

Han gjorde spillet lidt lettere med tastaturgenveje - y- og n-tasterne klikker på de tilsvarende ja-nej-knapper på skærmen - for at spare tid til at bevæge musen.

Giv det et skub:

Primalitetskontrolalgoritmer

Primtal har praktisk nytte i databehandling - såsom med fejlkorrigerende koder og kryptering. Men selvom prime-faktorisering er svært (derfor dens værdi i kryptering), er primalitetskontrol lettere, hvis det er vanskeligt. The Fields Medal-vindende tysk matematiker Alexander Grothendieck berygtet fejlagtigt 57 for prime (den Grothendieck prime). Når Lawson-Perfect analyserede data fra spillet , fandt han, at forskellige numre udviste en vis Grothendieckyness. Det tal, der oftest forveksles med et primtal, var 51, efterfulgt af 57, 87, 91, 119 og 133 – Lawson-Perfects nemesis (han udtænkte også en praktisk service til primalitetskontrol: https://isthisprime.com/2 ).

Den mest minimalistiske algoritme til at kontrollere et tals primehed er prøvedeling - divider tallet med hvert tal op til dets kvadratrod (produktet af to tal større end kvadratroden ville være større end det pågældende tal).

Denne naive metode er imidlertid ikke særlig effektiv, og det er nogle andre teknikker, der er udviklet gennem århundrederne heller ikke - som den tyske matematiker Carl Friedrich Gauss observerede i 1801, kræver de utålelig arbejdskraft selv for den mest utrættelige lommeregner.

Algoritmen Lawson-Perfect kodet til spillet kaldes Miller-Rabin primality test (som bygger på en meget effektiv, men ikke jernbeklædt metode fra det 17. århundrede, Fermats lille teorem ). Miller-Rabin-testen fungerer overraskende godt. Hvad Lawson-Perfect angår, er det dybest set magi - jeg forstår ikke rigtig, hvordan det fungerer, men jeg er overbevist om, at jeg kunne, hvis jeg brugte tiden på at se dybere på det, siger han.

Da testen bruger tilfældighed, giver den et sandsynligt resultat. Hvilket betyder, at nogle gange lyver testen. Der er en chance for at afsløre en bedrager, et sammensat tal, der forsøger at passere som primtal, siger Carl Pomerance, matematiker ved Dartmouth College og medforfatter til bogen Primtal: Et beregningsperspektiv . Chancerne for, at en bedrager slipper igennem algoritmens smarte kontrolmekanisme, er dog måske én ud af en billion, så testen er ret sikker.

Men hvad angår kloge primaalitetskontrolalgoritmer, er Miller-Rabin-testen toppen af ​​isbjerget, siger Pomerance. Især for 19 år siden annoncerede tre computerforskere - Manindra Agrawal, Neeraj Kayal og Nitin Saxena, alle ved Indian Institute of Technology Kanpur - at AKS primalitetstest (igen ved at bygge videre på Fermats metode), som endelig gav en test til utvetydigt at bevise, at et tal er primtal, uden randomisering og (teoretisk i det mindste) med imponerende hastighed. Ak, hurtig i teorien oversættes ikke altid til hurtig i det virkelige liv, så AKS-testen er ikke nyttig til praktiske formål.

Den uofficielle verdensrekord

Men det praktiske er ikke altid pointen. Af og til modtager Lawson-Perfect e-mail fra folk, der er ivrige efter at dele deres highscores i spillet. For nylig rapporterede en spiller 60 primtal på 60 sekunder, men rekorden er mere sandsynligt 127. (Lawson-Perfect sporer ikke høje scores; han ved, at der er nogle snydere med computerstøttede forsøg, der giver spidser i dataene).

Scoren på 127 blev opnået af Ravi Fernando, en matematikstuderende ved University of California, Berkeley, som offentliggjorde resultatet i juli 2020 . Det er stadig hans personlige bedste og, mener han, den uofficielle verdensrekord.

Siden sidste sommer har Fernando ikke spillet spillet meget med standardindstillingerne, men han har prøvet med tilpassede indstillinger, valgt for større tal og tilladt længere tidsgrænser - han scorede 240 med en fem-minutters grænse. Hvilket krævede en del gætværk, for tallene kom ind i det høje firecifrede område, og jeg har kun nogensinde husket primtal op til de lave 3.000-tal, siger han. Jeg formoder, at nogle vil hævde, at selv det er overdrevet.

Fernandos forskning er i algebraisk geometri, som involverer primtal til en vis grad. Men, siger han, min forskning har mere at gøre med, hvorfor jeg stoppede med at spille spillet, end hvorfor jeg startede (han startede sin ph.d. i 2014). Plus, han mener, at 127 ville være meget svær at slå. Og, siger han, det føles bare rigtigt at stoppe ved en primtalsrekord.

skjule