211service.com
Er 57 et primtall? Det er et spill for det.
Ms Tech | Pixabay
Den greske matematikeren Euklid kan godt ha bevist, rundt 300 f.Kr., at det finnes uendelig mange primtall. Men det var den britiske matematikeren Christian Lawson-Perfect som nylig utviklet dataspillet Er dette prime?
Spillet ble lansert for fem år siden og overgikk tre millioner forsøk 16. juli – eller mer til poenget, det oppnådde 2 999 999 kjøres – etter en Hacker News-innlegg genererte en økning på rundt 100 000 forsøk.
Målet med spillet er å sortere så mange tall som mulig i primtall eller ikke primtall på 60 sekunder (som Lawson-Perfect opprinnelig beskrevet det på Aperiodica l, en matematikkblogg som han er grunnlegger og redaktør av).
Et primtall er et helt tall med nøyaktig to divisorer, 1 og seg selv.
Det er veldig enkelt, men irriterende vanskelig, sier Lawson-Perfect, som jobber i e-læringsenheten ved Newcastle Universitys School of Mathematics and Statistics. Han skapte spillet på fritiden, men det har vist seg nyttig på jobben: Lawson-Perfect skriver programvare for e-vurdering (systemer som evaluerer læring). Systemet jeg lager er laget for å tilfeldig generere et mattespørsmål, og ta et svar fra eleven, som den automatisk markerer og gir tilbakemelding på, sier han. Du kan se på prime-spillet som en slags vurdering – han har brukt det når han gjør oppsøkende økter på skoler.
Han gjorde spillet litt enklere med hurtigtaster – y- og n-tastene klikker på de tilsvarende ja-nei-knappene på skjermen – for å spare tid når du beveger musen.
Gi det en virvel:
Primalitetssjekkende algoritmer
Primtall har praktisk nytte i databehandling – for eksempel med feilkorrigerende koder og kryptering. Men selv om primfaktorisering er vanskelig (derav verdien i kryptering), er primalitetskontroll enklere, om enn vanskelig. The Fields Medal-vinnende tysk matematiker Alexander Grothendieck beryktet feil 57 for prime (den Grothendieck prime). Når Lawson-Perfect analyserte data fra spillet , fant han ut at forskjellige tall viste en viss Grothendieckyness. Tallet som oftest ble forvekslet med et primtall var 51, etterfulgt av 57, 87, 91, 119 og 133 – Lawson-Perfects nemesis (han utviklet også en praktisk tjeneste for primalitetssjekking: https://isthisprime.com/2 ).
Den mest minimalistiske algoritmen for å kontrollere et talls primitet er prøvedeling - del tallet med hvert tall opp til kvadratroten (produktet av to tall større enn kvadratroten vil være større enn tallet det gjelder).
Denne naive metoden er imidlertid ikke særlig effektiv, og det er heller ikke noen andre teknikker som er utviklet gjennom århundrene – som den tyske matematikeren Carl Friedrich Gauss observerte i 1801, krever de utålelig arbeidskraft selv for den mest utrettelige kalkulator.
Algoritmen Lawson-Perfect kodet opp for spillet kalles Miller-Rabin primality test (som bygger på en veldig effektiv, men ikke jernkledd metode fra 1600-tallet, Fermats lille teorem ). Miller-Rabin-testen fungerer overraskende bra. Når det gjelder Lawson-Perfect, er det i bunn og grunn magi - jeg forstår egentlig ikke hvordan det fungerer, men jeg er sikker på at jeg kunne hvis jeg brukte tiden til å se dypere på det, sier han.
Siden testen bruker tilfeldighet, gir den et sannsynlighetsresultat. Noe som betyr at noen ganger lyver testen. Det er en sjanse for å avdekke en bedrager, et sammensatt tall som prøver å passere som primtall, sier Carl Pomerance, en matematiker ved Dartmouth College og medforfatter av boken Primtall: Et beregningsperspektiv . Sjansen for at en bedrager skal slippe gjennom algoritmens smarte kontrollmekanisme er kanskje én på en billion, så testen er ganske sikker.
Men når det gjelder smarte primalitetssjekkingsalgoritmer, er Miller-Rabin-testen toppen av isfjellet, sier Pomerance. Spesielt for 19 år siden kunngjorde tre informatikere - Manindra Agrawal, Neeraj Kayal og Nitin Saxena, alle ved Indian Institute of Technology Kanpur - at AKS primalitetstest (igjen bygger på Fermats metode), som til slutt ga en test for utvetydig å bevise at et tall er primtall, uten randomisering og (teoretisk i det minste) med imponerende hastighet. Akk, rask i teorien oversettes ikke alltid til rask i det virkelige liv, så AKS-testen er ikke nyttig for praktiske formål.
Den uoffisielle verdensrekorden
Men det praktiske er ikke alltid poenget. Av og til mottar Lawson-Perfect e-post fra folk som er opptatt av å dele sine toppscore i spillet. Nylig rapporterte en spiller 60 primtall på 60 sekunder, men rekorden er mer sannsynlig 127. (Lawson-Perfect sporer ikke høye poengsummer; han vet at det er noen juksemakere, med datastøttede forsøk som gir topper i dataene.)
Poengsummen 127 ble oppnådd av Ravi Fernando, en matematikkstudent ved University of California, Berkeley, som la ut resultatet i juli 2020 . Det er fortsatt hans personlige rekord, og han regner med den uoffisielle verdensrekorden.
Siden i fjor sommer har Fernando ikke spilt spillet mye med standardinnstillingene, men han har prøvd med tilpassede innstillinger, valgt for større tall og tillatt lengre tidsbegrensninger - han scoret 240 med en fem-minutters grense. Noe som krevde mye gjetting, fordi tallene kom inn i det høye firesifrede området, og jeg har bare husket primtallene opp til de lave 3000-tallet, sier han. Jeg antar at noen vil hevde at selv det er overdrevet.
Fernandos forskning er i algebraisk geometri, som involverer primtal til en viss grad. Men, sier han, forskningen min har mer å gjøre med hvorfor jeg sluttet å spille spillet enn hvorfor jeg begynte (han startet sin doktorgrad i 2014). I tillegg tror han at 127 ville være veldig vanskelig å slå. Og, sier han, det føles rett å stoppe ved en primtallsrekord.
