211service.com
Is 57 een priemgetal? Daar is een spel voor.
mevrouw Tech | Pixabay
De Griekse wiskundige Euclides zou heel goed kunnen hebben bewezen, rond 300 vGT, dat er oneindig veel priemgetallen zijn. Maar het was de Britse wiskundige Christian Lawson-Perfect die, meer recentelijk, het computerspel bedacht Is dit prime?
De game werd vijf jaar geleden gelanceerd en overtrof op 16 juli drie miljoen pogingen - of, meer ter zake, het bereikte een run van 2.999.999 - na een Hacker Nieuwsbericht genereerde een golf van ongeveer 100.000 pogingen.
Het doel van het spel is om binnen 60 seconden zoveel mogelijk getallen in prime of niet in prime te sorteren (zoals Lawson-Perfect oorspronkelijk beschreven het aan de aperiodica l, een wiskundeblog waarvan hij oprichter en redacteur is).
Een priemgetal is een geheel getal met precies twee delers, 1 en zichzelf.
Het is heel eenvoudig, maar verschrikkelijk moeilijk, zegt Lawson-Perfect, die werkt in de e-learningeenheid van de School of Mathematics and Statistics van Newcastle University. Hij maakte het spel in zijn vrije tijd, maar het is nuttig gebleken tijdens het werk: Lawson-Perfect schrijft e-assessmentsoftware (systemen die leren evalueren). Het systeem dat ik maak, is ontworpen om willekeurig een wiskundevraag te genereren en een antwoord van de student te nemen, dat het automatisch markeert en feedback geeft, zegt hij. Je zou de primes-game kunnen zien als een soort beoordeling - hij gebruikte het bij outreach-sessies op scholen.
Hij maakte het spel iets gemakkelijker met sneltoetsen - de y- en n-toetsen klikken op de bijbehorende ja-nee-knoppen op het scherm - om tijd te besparen bij het bewegen van de muis.
Probeer het eens:
Algoritmen voor het controleren van de primaire toestand
Priemgetallen hebben praktisch nut bij computergebruik, zoals bij foutcorrigerende codes en codering. Maar hoewel ontbinden in priemfactoren moeilijk is (vandaar de waarde ervan in codering), is het controleren van de priemgetallen eenvoudiger, zij het lastig. De Fields Medal-winnende Duitse wiskundige Alexander Grothendieck beruchte vergissing 57 voor prime (de Grotendieck prime). Wanneer Lawson-Perfect geanalyseerde gegevens van het spel , ontdekte hij dat verschillende getallen een zekere Grothendieckyness vertoonden. Het getal dat het vaakst werd aangezien voor een priemgetal was 51, gevolgd door 57, 87, 91, 119 en 133 - de aartsvijand van Lawson-Perfect (hij bedacht ook een handige priemcontroleservice: https://isthisprime.com/2 ).
Het meest minimalistische algoritme om de priemheid van een getal te controleren, is proefdeling - deel het getal door elk getal tot aan de vierkantswortel (het product van twee getallen groter dan de vierkantswortel zou groter zijn dan het betreffende getal).
Deze naïeve methode is echter niet erg efficiënt, en er zijn ook geen andere technieken die door de eeuwen heen zijn ontwikkeld - zoals de Duitse wiskundige Carl Friedrich Gauss in 1801 opmerkte, vereisen ze ondraaglijke arbeid, zelfs voor de meest onvermoeibare rekenmachine.
Het algoritme dat Lawson-Perfect voor het spel heeft gecodeerd, wordt de Miller-Rabin-primaliteitstest genoemd (die voortbouwt op een zeer efficiënte maar niet ijzersterke 17e-eeuwse methode, De kleine stelling van Fermat ). De Miller-Rabin-test werkt verrassend goed. Wat Lawson-Perfect betreft, is het eigenlijk magie - ik begrijp niet echt hoe het werkt, maar ik ben ervan overtuigd dat ik het zou kunnen als ik de tijd zou nemen om er dieper naar te kijken, zegt hij.
Omdat de test gebruik maakt van willekeur, levert het een probabilistisch resultaat op. Wat betekent dat soms de test liegt. Er is een kans om een bedrieger te ontdekken, een samengesteld getal dat probeert door te gaan als priemgetal, zegt Carl Pomerance, een wiskundige aan het Dartmouth College en co-auteur van het boek Priemgetallen: een rekenkundig perspectief . De kans dat een bedrieger door het slimme controlemechanisme van het algoritme glipt, is misschien één op een biljoen, dus de test is redelijk veilig.
Maar wat slimme algoritmen voor het controleren van priemgetallen betreft, is de Miller-Rabin-test het topje van de ijsberg, zegt Pomerance. Met name 19 jaar geleden kondigden drie computerwetenschappers - Manindra Agrawal, Neeraj Kayal en Nitin Saxena, allemaal van het Indian Institute of Technology Kanpur - de AKS-primaliteitstest (opnieuw voortbouwend op de methode van Fermat), die uiteindelijk een test opleverde om ondubbelzinnig te bewijzen dat een getal een priemgetal is, zonder randomisatie en (theoretisch althans) met indrukwekkende snelheid. Helaas vertaalt snel in theorie zich niet altijd in snel in het echte leven, dus de AKS-test is niet nuttig voor praktische doeleinden.
Het onofficiële wereldrecord
Maar praktisch is niet altijd het punt. Af en toe ontvangt Lawson-Perfect e-mail van mensen die graag hun hoogste scores in het spel willen delen. Onlangs meldde een speler 60 priemgetallen in 60 seconden, maar het record is waarschijnlijker 127. (Lawson-Perfect houdt geen hoge scores bij; hij weet dat er valsspelers zijn, met computerondersteunde pogingen die pieken in de gegevens veroorzaken.)
De score van 127 werd behaald door Ravi Fernando, een afgestudeerde wiskundestudent aan de University of California, Berkeley, die: het resultaat gepost in juli 2020 . Het is nog steeds zijn persoonlijk record en, schat hij, het onofficiële wereldrecord.
Sinds afgelopen zomer heeft Fernando het spel niet veel gespeeld met de standaardinstellingen, maar hij heeft geprobeerd met aangepaste instellingen, te selecteren voor grotere aantallen en langere tijdslimieten toe te staan - hij scoorde 240 met een limiet van vijf minuten. Dat vergde veel giswerk, omdat de getallen in het hoge viercijferige bereik kwamen en ik alleen priemgetallen tot de lage 3.000s heb onthouden, zegt hij. Ik denk dat sommigen zullen beweren dat zelfs dat overdreven is.
Fernando's onderzoek is in de algebraïsche meetkunde, die tot op zekere hoogte priemgetallen omvat. Maar, zegt hij, mijn onderzoek heeft meer te maken met waarom ik ben gestopt met het spel dan met waarom ik ben begonnen (hij begon zijn PhD in 2014). Bovendien denkt hij dat 127 erg moeilijk te verslaan is. En, zegt hij, het voelt gewoon goed om te stoppen bij een priemgetalrecord.
