Vai 57 ir pirmskaitlis? Tam ir spēle.

Ms Tech | Pixabay

Grieķu matemātiķis Eiklīds, iespējams, apmēram 300. gadā pirms mūsu ēras ir pierādījis, ka ir bezgalīgi daudz pirmskaitļu. Bet pavisam nesen datorspēli izstrādāja britu matemātiķis Kristians Losons-Perfekts Vai šis ir galvenais?

Spēle, kas tika uzsākta pirms pieciem gadiem, 16. jūlijā pārsniedza trīs miljonus mēģinājumu — vai, vēl jo vairāk, tā sasniedza 2 999 999 — pēc Hacker News ziņa radīja aptuveni 100 000 mēģinājumu pieaugumu.

Spēles mērķis ir 60 sekunžu laikā kārtot pēc iespējas vairāk skaitļu pirmajā vai neskaitlī (kā sākotnēji bija Lawson-Perfect aprakstīts tas ieslēgts Aperiodika l, matemātikas emuārs, kura dibinātājs un redaktors viņš ir).

Pirmskaitlis ir vesels skaitlis ar precīziem diviem dalītājiem — 1 un pats sevi.

Tas ir ļoti vienkārši, bet satriecoši sarežģīti, saka Lovsons-Perfekts, kurš strādā Ņūkāslas Universitātes Matemātikas un statistikas skolas e-mācību nodaļā. Viņš radīja spēli savā brīvajā laikā, taču tā izrādījās noderīga darbā: Lawson-Perfect raksta e-novērtēšanas programmatūru (sistēmas, kas novērtē mācīšanos). Sistēma, ko izveidoju, ir paredzēta, lai nejauši ģenerētu matemātikas jautājumu un saņemtu atbildi no skolēna, ko tā automātiski atzīmē un sniedz atsauksmes, viņš saka. Jūs varētu uzskatīt Primes spēli kā sava veida novērtējumu — viņš to ir izmantojis, veicot informatīvās sesijas skolās.

Viņš nedaudz atviegloja spēli, izmantojot īsinājumtaustiņus — y un n taustiņi ekrānā noklikšķina uz atbilstošām jā-nē pogām, lai ietaupītu peles pārvietošanas laiku.

Iepriecini to:

Primalitātes pārbaudes algoritmi

Pirmskaitļi ir praktiski noderīgi skaitļošanā, piemēram, ar kļūdu labošanas kodiem un šifrēšanu. Bet, lai gan primārā faktorizācija ir sarežģīta (tātad tās vērtība šifrēšanā), primāruma pārbaude ir vieglāka, ja tā ir sarežģīta. Fīldsa medaļas ieguvējs vācu matemātiķis Aleksandrs Grothendiks bēdīgi kļūdījies 57 par galveno (Grothendieck prime). Kad Lawson-Perfect analizēti dati no spēles , viņš atklāja, ka dažādi skaitļi uzrāda zināmu grothendieckyness. Skaitlis, kas visbiežāk tika sajaukts ar pirmskaitļu, bija 51, kam sekoja 57, 87, 91, 119 un 133 — Lousona-Perfekta ienaidnieks (viņš arī izstrādāja ērtu pirmatnības pārbaudes pakalpojumu: https://isthisprime.com/2 ).

Visminimālākais algoritms skaitļa pirmšķirīguma pārbaudei ir izmēģinājuma dalīšana — dala skaitli ar katru skaitli līdz tā kvadrātsaknei (divu skaitļu reizinājums, kas ir lielāks par kvadrātsakni, būtu lielāks par attiecīgo skaitli).

Tomēr šī naivā metode nav īpaši efektīva, un arī daži citi paņēmieni nav izdomāti gadsimtu gaitā — kā 1801. gadā novēroja vācu matemātiķis Karls Frīdrihs Gauss, tie prasa neciešamu darbu pat visnenogurdināmākajam kalkulatoram.

Spēlei iekodētais Lawson-Perfect algoritms tiek saukts par Millera-Rabina pirmatnības testu (kas balstās uz ļoti efektīvu, bet ne gludu 17. gadsimta metodi, Fermā mazā teorēma ). Millera-Rabina tests darbojas pārsteidzoši labi. Kas attiecas uz Lawson-Perfect, tā būtībā ir maģija — es īsti nesaprotu, kā tas darbojas, taču esmu pārliecināts, ka es varētu, ja veltīšu laiku, lai to aplūkotu dziļāk, viņš saka.

Tā kā testā tiek izmantota nejaušība, tas rada varbūtības rezultātu. Tas nozīmē, ka dažreiz pārbaude ir meli. Pastāv iespēja atklāt viltvārdu, saliktu skaitli, kas mēģina tikt pie pirmskaitļa, saka Karls Pomeranss, matemātiķis Dartmutas koledžā un grāmatas līdzautors. Pirmskaitļi: skaitļošanas perspektīva . Tomēr iespēja, ka viltnieks izslīdēs cauri algoritma gudrajam pārbaudes mehānismam, ir viena pret triljonu, tāpēc pārbaude ir diezgan droša.

Bet, ciktāl tas attiecas uz gudriem pirmatnības pārbaudes algoritmiem, Millera-Rabina tests ir aisberga redzamā daļa, saka Pomerance. Proti, pirms 19 gadiem trīs datorzinātnieki — Manindra Agravala, Nerajs Kayal un Nitin Saxena, visi no Indijas Kanpuras Tehnoloģiju institūta — paziņoja par AKS pirmtiesības tests (atkal balstoties uz Fermā metodi), kas beidzot nodrošināja pārbaudi, lai nepārprotami pierādītu, ka skaitlis ir galvenais, bez nejaušības un (vismaz teorētiski) ar iespaidīgu ātrumu. Diemžēl ātrs teorētiski ne vienmēr nozīmē ātru reālajā dzīvē, tāpēc AKS tests nav noderīgs praktiskiem mērķiem.

Neoficiālais pasaules rekords

Taču praktiskums ne vienmēr ir galvenais. Reizēm Lawson-Perfect saņem e-pastu no cilvēkiem, kuri vēlas dalīties ar saviem labākajiem rezultātiem šajā spēlē. Nesen kāds spēlētājs ziņoja par 60 pirmskaitļiem 60 sekundēs, bet rekords, visticamāk, ir 127. (Lawson-Perfect neizseko augstus rezultātus; viņš zina, ka ir daži krāpnieki, ar datorizētiem mēģinājumiem, kas rada lēcienus datos.)

127 punktus sasniedza Kalifornijas Universitātes Bērklijas matemātikas maģistrants Ravi Fernando, kurš publicēja rezultātu 2020. gada jūlijā . Tas joprojām ir viņa personīgais rekords un, pēc viņa domām, neoficiālais pasaules rekords.

Kopš pagājušās vasaras Fernando nav daudz spēlējis spēli ar noklusējuma iestatījumiem, taču viņš ir mēģinājis ar pielāgotiem iestatījumiem, atlasot lielākus skaitļus un pieļaujot garākus laika ierobežojumus — viņš ieguva 240 punktus ar piecu minūšu ierobežojumu. Viņš saka, ka tas prasīja daudz minējumu, jo skaitļi sasniedza augstāko četrciparu diapazonu, un es jebkad esmu iegaumējis tikai pirmskaitļus līdz zemajiem 3000. Es domāju, ka daži iebilst, ka pat tas ir pārmērīgi.

Fernando pētījumi attiecas uz algebrisko ģeometriju, kas zināmā mērā ietver pirmskaitļus. Bet viņš saka, ka mans pētījums ir vairāk saistīts ar to, kāpēc es pārtraucu spēlēt spēli, nevis ar to, kāpēc es sāku (viņš sāka doktora grādu 2014. gadā). Turklāt viņš uzskata, ka 127. punktu būtu ļoti grūti pārspēt. Un, viņš saka, ir pareizi apstāties pie pirmskaitļa ieraksta.

paslēpties