Czy 57 jest liczbą pierwszą? Jest na to gra.

Pani Tech | Pixabay

Około 300 p.n.e. grecki matematyk Euklides mógł równie dobrze udowodnić, że istnieje nieskończenie wiele liczb pierwszych. Ale to brytyjski matematyk Christian Lawson-Perfect, który niedawno wymyślił grę komputerową Czy to pierwsza?

Uruchomiona pięć lat temu gra przekroczyła trzy miliony prób 16 lipca — lub, co bardziej istotne, osiągnęła liczbę 2 999 999 — po Post z wiadomościami o hakerach wygenerował gwałtowny wzrost o około 100 000 prób.

Celem gry jest posortowanie jak największej liczby liczb na liczbę pierwszą lub nie pierwszą w ciągu 60 sekund (jak pierwotnie Lawson-Perfect opisane to na Aperiodica l, blog matematyczny, którego jest założycielem i redaktorem).

Liczba pierwsza to liczba całkowita z dokładnie dwoma dzielnikami, 1 i samą sobą.

To bardzo proste, ale irytująco trudne, mówi Lawson-Perfect, który pracuje w jednostce e-learningowej w Szkole Matematyki i Statystyki Uniwersytetu Newcastle. Stworzył grę w wolnym czasie, ale okazała się przydatna w pracy: Lawson-Perfect pisze oprogramowanie do e-oceny (systemy oceniające uczenie się). System, który tworzę, jest zaprojektowany tak, aby losowo generował pytanie z matematyki i pobierał odpowiedź od ucznia, którą automatycznie zaznacza i przekazuje informację zwrotną – mówi. Możesz postrzegać grę liczb pierwszych jako rodzaj oceny — używał jej podczas sesji informacyjnych w szkołach.

Ułatwił nieco grę za pomocą skrótów klawiaturowych — klawisze y i n klikają odpowiednie przyciski tak-nie na ekranie — aby skrócić czas poruszania myszą.

Zamieszaj to:

Algorytmy sprawdzania pierwszości

Liczby pierwsze mają praktyczną użyteczność w obliczeniach — na przykład w przypadku kodów korekcji błędów i szyfrowania. Ale podczas gdy rozkład na czynniki pierwsze jest trudny (stąd jego wartość w szyfrowaniu), sprawdzanie pierwszości jest łatwiejsze, jeśli jest trudne. Niemiecki matematyk nagrodzony Medalem Fieldsa Aleksander Grothendieck niesławnie pomylił się 57 dla liczby pierwszej (prim Grothendiecka). Kiedy Lawson-idealny przeanalizowane dane z gry stwierdził, że różne liczby wykazywały pewną Grothendieckyness. Liczba najczęściej mylona z liczbą pierwszą wynosiła 51, a następnie 57, 87, 91, 119 i 133 — wróg Lawsona-Perfecta (opracował także przydatną usługę sprawdzania pierwszości: https://isthisprime.com/2 ).

Najbardziej minimalistycznym algorytmem sprawdzania pierwszości liczby jest dzielenie próbne — należy podzielić liczbę przez każdą liczbę aż do jej pierwiastka kwadratowego (iloczyn dwóch liczb większych od pierwiastka kwadratowego byłby większy niż podana liczba).

Jednak ta naiwna metoda nie jest zbyt wydajna, podobnie jak inne techniki opracowane przez wieki — jak zauważył niemiecki matematyk Carl Friedrich Gauss w 1801 r., wymagają one pracy nie do zniesienia nawet dla najbardziej niestrudzonego kalkulatora.

Algorytm zakodowany przez Lawsona-Perfecta na potrzeby gry nazywa się testem pierwszości Millera-Rabina (który opiera się na bardzo wydajnej, ale nieżelaznej metodzie z XVII wieku, Małe twierdzenie Fermata ). Test Millera-Rabina działa zaskakująco dobrze. Jeśli chodzi o Lawson-Perfect, to w zasadzie magia — tak naprawdę nie rozumiem, jak to działa, ale jestem przekonany, że mógłbym, gdybym poświęcił czas na dokładniejsze przyjrzenie się temu, mówi.

Ponieważ test wykorzystuje losowość, daje wynik probabilistyczny. Co oznacza, że ​​czasami test kłamie. Istnieje szansa na odkrycie oszusta, złożonej liczby, która próbuje uchodzić za pierwszą, mówi Carl Pomerance, matematyk z Dartmouth College i współautor książki Liczby pierwsze: perspektywa obliczeniowa . Szanse, że oszust prześlizgnie się przez sprytny mechanizm sprawdzający algorytmu, są jednak może jeden na bilion, więc test jest całkiem bezpieczny.

Ale jeśli chodzi o sprytne algorytmy sprawdzania pierwszości, test Millera-Rabina jest wierzchołkiem góry lodowej, mówi Pomerance. Warto zauważyć, że 19 lat temu trzech informatyków — Manindra Agrawal, Neeraj Kayal i Nitin Saxena, wszyscy z Indyjskiego Instytutu Technologii Kanpur — ogłosili Test pierwszości AKS (znowu w oparciu o metodę Fermata), która w końcu dostarczyła testu na jednoznaczne udowodnienie, że liczba jest liczbą pierwszą, bez randomizacji i (przynajmniej teoretycznie) z imponującą szybkością. Niestety, szybkość w teorii nie zawsze przekłada się na szybkość w prawdziwym życiu, więc test AKS nie jest przydatny do celów praktycznych.

Nieoficjalny rekord świata

Ale nie zawsze chodzi o praktyczność. Czasami Lawson-Perfect otrzymuje e-maile od osób, które chcą podzielić się swoimi najlepszymi wynikami w grze. Ostatnio gracz zgłosił 60 liczb pierwszych w ciągu 60 sekund, ale jest bardziej prawdopodobne, że rekord wynosi 127. (Lawson-Perfect nie śledzi wysokich wyników; wie, że są tacy oszuści, którzy wspomagają komputerowo próby, które powodują gwałtowne wzrosty danych).

Wynik 127 uzyskał Ravi Fernando, absolwent matematyki na Uniwersytecie Kalifornijskim w Berkeley, który opublikował wynik w lipcu 2020 r. . To wciąż jego rekord życiowy i, jak twierdzi, nieoficjalny rekord świata.

Od zeszłego lata Fernando nie grał zbytnio w grę z ustawieniami domyślnymi, ale próbował z niestandardowymi ustawieniami, wybierając większe liczby i dopuszczając dłuższe limity czasowe – zdobył 240 punktów z pięciominutowym limitem. Co wymagało wielu domysłów, ponieważ liczby osiągnęły wysoki czterocyfrowy zakres, a ja zapamiętałem liczby pierwsze tylko do 3 000, mówi. Przypuszczam, że niektórzy twierdzą, że nawet to jest przesadne.

Badania Fernando dotyczą geometrii algebraicznej, która w pewnym stopniu obejmuje liczby pierwsze. Ale, jak mówi, moje badania mają więcej wspólnego z tym, dlaczego przestałem grać w tę grę, niż dlaczego zacząłem (rozpoczął pracę doktorską w 2014 roku). Poza tym uważa, że ​​127 byłoby bardzo trudne do pokonania. I, jak mówi, po prostu dobrze jest zatrzymać się na rekordzie liczby pierwszej.

ukryć