211service.com
Ist 57 eine Primzahl? Dafür gibt es ein Spiel.
Frau Technik | Pixabay
Der griechische Mathematiker Euklid könnte sehr wohl um 300 v. Chr. bewiesen haben, dass es unendlich viele Primzahlen gibt. Aber es war der britische Mathematiker Christian Lawson-Perfect, der in jüngerer Zeit das Computerspiel entwickelt hat Ist das Primzahl?
Das vor fünf Jahren gestartete Spiel überschritt am 16. Juli drei Millionen Versuche – oder, genauer gesagt, es erreichte 2.999.999 Runs – nach a Hacker-News-Beitrag erzeugte eine Welle von etwa 100.000 Versuchen.
Das Ziel des Spiels ist es, in 60 Sekunden so viele Zahlen wie möglich in Primzahlen oder Nicht-Primzahlen zu sortieren (wie ursprünglich Lawson-Perfect). beschrieben es an Die Aperiodika l, ein Mathematik-Blog, dessen Gründer und Herausgeber er ist).
Eine Primzahl ist eine ganze Zahl mit genau zwei Teilern, 1 und sich selbst.
Es ist sehr einfach, aber ärgerlich schwierig, sagt Lawson-Perfect, der in der E-Learning-Einheit der School of Mathematics and Statistics der Newcastle University arbeitet. Er hat das Spiel in seiner Freizeit entwickelt, aber im Job hat es sich als nützlich erwiesen: Lawson-Perfect schreibt E-Assessment-Software (Systeme, die das Lernen bewerten). Das System, das ich mache, ist so konzipiert, dass es zufällig eine mathematische Frage generiert und vom Schüler eine Antwort entgegennimmt, die es automatisch markiert und Feedback dazu gibt, sagt er. Man könnte das Primes-Spiel als eine Art Bewertung ansehen – er hat es bei seinen Outreach-Sitzungen in Schulen verwendet.
Er hat das Spiel mit Tastaturkürzeln etwas einfacher gemacht – die Tasten y und n klicken auf die entsprechenden Ja-Nein-Schaltflächen auf dem Bildschirm – um Zeit für Mausbewegungen zu sparen.
Probieren Sie es aus:
Primzahlprüfungsalgorithmen
Primzahlen haben einen praktischen Nutzen beim Rechnen – beispielsweise bei Fehlerkorrekturcodes und Verschlüsselung. Aber während die Primfaktorzerlegung schwierig ist (daher ihr Wert bei der Verschlüsselung), ist die Primzahlprüfung einfacher, wenn auch knifflig. Mit der Fields-Medaille ausgezeichneter deutscher Mathematiker Alexander Grothendieck berüchtigt falsch 57 für die Primzahl (die Grothendieck-Primzahl). Wenn Lawson-Perfect Analysierte Daten aus dem Spiel , stellte er fest, dass verschiedene Nummern eine gewisse Grothendieckigkeit aufwiesen. Die Zahl, die am häufigsten mit einer Primzahl verwechselt wurde, war 51, gefolgt von 57, 87, 91, 119 und 133 – Lawson-Perfects Nemesis (er entwickelte auch einen praktischen Dienst zur Überprüfung der Primzahl: https://isthisprime.com/2 ).
Der minimalistischste Algorithmus zum Prüfen der Primzahl einer Zahl ist die Probedivision – dividiere die Zahl durch jede Zahl bis zu ihrer Quadratwurzel (das Produkt zweier Zahlen, die größer als die Quadratwurzel sind, wäre größer als die betreffende Zahl).
Diese naive Methode ist jedoch nicht sehr effizient, und auch einige andere Techniken wurden im Laufe der Jahrhunderte nicht entwickelt – wie der deutsche Mathematiker Carl Friedrich Gauß 1801 feststellte, erfordern sie selbst für den unermüdlichsten Rechner eine unerträgliche Arbeit.
Der von Lawson-Perfect für das Spiel codierte Algorithmus heißt Miller-Rabin-Primzahltest (der auf einer sehr effizienten, aber nicht eisernen Methode des 17. Jahrhunderts aufbaut, Kleiner Satz von Fermat ). Der Miller-Rabin-Test funktioniert überraschend gut. Soweit es Lawson-Perfect angeht, ist es im Grunde magisch – ich verstehe nicht wirklich, wie es funktioniert, aber ich bin zuversichtlich, dass ich es könnte, wenn ich mir die Zeit nehme, es genauer zu betrachten, sagt er.
Da der Test Zufälligkeit verwendet, erzeugt er ein probabilistisches Ergebnis. Was bedeutet, dass manchmal der Test lügt. Es besteht die Möglichkeit, einen Betrüger aufzudecken, eine zusammengesetzte Zahl, die versucht, als Primzahl durchzugehen, sagt Carl Pomerance, Mathematiker am Dartmouth College und Mitautor des Buches Primzahlen: Eine rechnerische Perspektive . Die Chancen, dass ein Betrüger durch den cleveren Prüfmechanismus des Algorithmus schlüpft, stehen jedoch vielleicht eins zu einer Billion, sodass der Test ziemlich sicher ist.
Aber was clevere Primzahlprüfalgorithmen angeht, ist der Miller-Rabin-Test die Spitze des Eisbergs, sagt Pomerance. Vor allem vor 19 Jahren gaben drei Informatiker – Manindra Agrawal, Neeraj Kayal und Nitin Saxena, alle am Indian Institute of Technology Kanpur – dies bekannt AKS-Primzahltest (wieder aufbauend auf Fermats Methode), die endlich einen Test lieferte, um eindeutig zu beweisen, dass eine Zahl eine Primzahl ist, ohne Randomisierung und (zumindest theoretisch) mit beeindruckender Geschwindigkeit. Leider bedeutet schnell in der Theorie nicht immer schnell im wirklichen Leben, daher ist der AKS-Test für praktische Zwecke nicht nützlich.
Der inoffizielle Weltrekord
Aber Praktikabilität ist nicht immer der Punkt. Gelegentlich erhält Lawson-Perfect E-Mails von Leuten, die ihre Highscores im Spiel teilen möchten. Kürzlich meldete ein Spieler 60 Primzahlen in 60 Sekunden, aber der Rekord liegt wahrscheinlicher bei 127. (Lawson-Perfect verfolgt keine Highscores; er weiß, dass es einige Betrüger gibt, deren computergestützte Versuche Spitzen in den Daten erzeugen.)
Die 127 Punkte wurden von Ravi Fernando, einem Mathematikstudenten an der University of California, Berkeley, erreicht veröffentlichte das Ergebnis im Juli 2020 . Es ist immer noch seine persönliche Bestleistung und, wie er meint, der inoffizielle Weltrekord.
Seit letztem Sommer hat Fernando das Spiel nicht mehr oft mit den Standardeinstellungen gespielt, aber er hat es mit benutzerdefinierten Einstellungen versucht, indem er größere Zahlen ausgewählt und längere Zeitlimits zugelassen hat – er hat 240 Punkte mit einem Fünf-Minuten-Limit erzielt. Was viel Rätselraten erforderte, denn die Zahlen gingen in den hohen vierstelligen Bereich und ich habe mir immer nur Primzahlen bis zu den niedrigen 3.000ern gemerkt, sagt er. Ich nehme an, einige würden argumentieren, dass sogar das übertrieben ist.
Fernandos Forschung befasst sich mit algebraischer Geometrie, die bis zu einem gewissen Grad Primzahlen beinhaltet. Aber, sagt er, meine Forschung hat mehr damit zu tun, warum ich aufgehört habe, das Spiel zu spielen, als warum ich angefangen habe (er hat 2014 mit seiner Promotion begonnen). Plus, er Zahlen 127 wäre sehr schwer zu schlagen. Und, sagt er, es fühlt sich einfach richtig an, bei einem Primzahlrekord aufzuhören.
