Är 57 ett primtal? Det finns ett spel för det.

Ms Tech | Pixabay

Den grekiske matematikern Euklid kan mycket väl ha bevisat, cirka 300 f.Kr., att det finns oändligt många primtal. Men det var den brittiske matematikern Christian Lawson-Perfect som på senare tid skapade datorspelet Är detta prime?

Spelet lanserades för fem år sedan och överträffade tre miljoner försök den 16 juli – eller mer till punkten, det fick 2 999 999 körningar – efter en Hacker News-inlägg genererade en ökning med cirka 100 000 försök.

Målet med spelet är att sortera så många tal som möjligt i primtal eller inte primtal på 60 sekunder (som Lawson-Perfect ursprungligen beskrivs det på Aperiodica l, en matematikblogg där han är grundare och redaktör).

Ett primtal är ett heltal med exakt två delare, 1 och sig själv.

Det är väldigt enkelt, men irriterande svårt, säger Lawson-Perfect, som arbetar på e-learning-enheten vid Newcastle Universitys School of Mathematics and Statistics. Han skapade spelet på sin fritid, men det har visat sig användbart på jobbet: Lawson-Perfect skriver programvara för e-bedömning (system som utvärderar lärande). Systemet jag gör är designat för att slumpmässigt generera en matematikfråga, och ta ett svar från eleven som den automatiskt markerar och ger feedback på, säger han. Du kan se prime-spelet som ett slags bedömning – han har använt det när han gör uppsökande sessioner i skolor.

Han gjorde spelet något enklare med kortkommandon – y- och n-tangenterna klickar på motsvarande ja-nej-knappar på skärmen – för att spara tid för att flytta musen.

Ge det en snurra:

Primalitetskontrollerande algoritmer

Primtal har praktisk nytta i datoranvändning - som med felkorrigerande koder och kryptering. Men även om primtalsfaktorisering är svårt (därav dess värde i kryptering), är primalitetskontroll lättare, om än knepigt. The Fields Medal-vinnande tysk matematiker Alexander Grothendieck ökänt misstag 57 för prime (den Grothendieck prime). När Lawson-Perfect analyserade data från spelet , fann han att olika nummer uppvisade en viss Grothendieckyness. Siffran som oftast förväxlades med ett primtal var 51, följt av 57, 87, 91, 119 och 133 – Lawson-Perfects nemesis (han skapade också en praktisk tjänst för primalitetskontroll: https://isthisprime.com/2 ).

Den mest minimalistiska algoritmen för att kontrollera ett tals primeness är provdelning – dividera talet med varje tal upp till dess kvadratrot (produkten av två tal större än kvadratroten skulle vara större än talet i fråga).

Denna naiva metod är dock inte särskilt effektiv, och inte heller några andra tekniker som har utvecklats under århundradena – som den tyske matematikern Carl Friedrich Gauss observerade 1801, kräver de outhärdligt arbete även för den mest outtröttliga räknaren.

Algoritmen som Lawson-Perfect kodade för spelet kallas för Miller-Rabins primattest (som bygger på en mycket effektiv men inte järnklädd 1600-talsmetod, Fermats lilla teorem ). Miller-Rabin-testet fungerar förvånansvärt bra. När det gäller Lawson-Perfect är det i grunden magi - jag förstår inte riktigt hur det fungerar, men jag är övertygad om att jag skulle kunna om jag ägnade tid åt att titta på det djupare, säger han.

Eftersom testet använder slumpmässighet ger det ett probabilistiskt resultat. Vilket gör att testet ibland ljuger. Det finns en chans att avslöja en bedragare, ett sammansatt tal som försöker passera som primtal, säger Carl Pomerance, matematiker vid Dartmouth College och medförfattare till boken Prime Numbers: A Computational Perspective . Chansen för att en bedragare ska glida igenom algoritmens smarta kontrollmekanism är dock kanske en på en biljon, så testet är ganska säkert.

Men när det gäller smarta primalitetskontrollalgoritmer är Miller-Rabin-testet toppen av isberget, säger Pomerance. För 19 år sedan tillkännagav tre datavetare – Manindra Agrawal, Neeraj Kayal och Nitin Saxena, alla vid Indian Institute of Technology Kanpur – att AKS primalitetstest (återigen bygger på Fermats metod), som slutligen gav ett test för att otvetydigt bevisa att ett tal är primtal, utan randomisering och (åtminstone teoretiskt) med imponerande hastighet. Tyvärr, snabb i teorin översätts inte alltid till snabb i verkliga livet, så AKS-testet är inte användbart för praktiska ändamål.

Det inofficiella världsrekordet

Men det praktiska är inte alltid poängen. Ibland får Lawson-Perfect e-post från personer som vill dela med sig av sina höga poäng i spelet. Nyligen rapporterade en spelare 60 primtal på 60 sekunder, men rekordet är mer troligt 127. (Lawson-Perfect spårar inte höga poäng; han vet att det finns några fuskare, med datorstödda försök som ger toppar i data.)

Poängen 127 uppnåddes av Ravi Fernando, en doktorand i matematik vid University of California, Berkeley, som publicerade resultatet i juli 2020 . Det är fortfarande hans personbästa och, tror han, det inofficiella världsrekordet.

Sedan förra sommaren har Fernando inte spelat spelet mycket med standardinställningarna, men han har försökt med anpassade inställningar, valt för större siffror och tillåtit längre tidsgränser - han fick 240 med en femminutersgräns. Vilket tog en hel del gissningar, eftersom siffrorna hamnade i det höga fyrsiffriga intervallet och jag har bara någonsin memorerat primtal upp till de låga 3 000-talen, säger han. Jag antar att vissa skulle hävda att även det är överdrivet.

Fernandos forskning är i algebraisk geometri, vilket involverar primtal till viss del. Men, säger han, min forskning har mer att göra med varför jag slutade spela spelet än varför jag började (han började sin doktorsexamen 2014). Dessutom tror han att 127 skulle vara väldigt svårt att slå. Och, säger han, det känns helt rätt att stanna vid ett primtalsrekord.

Dölj