10223 is dus geen Sierpinski-getal, nog vijf te gaan


Op 6 november van dit jaar werd openbaar gemaakt dat de Hongaar Peter Szabolcs op 31 oktober een nieuw priemgetal gevonden had: $10223\times 2^{31172165}+1$. Dit is met zijn 9383761 cijfers het zevende grootste priemgetal dat de mens ooit ontdekt heeft. Maar het is wel het grootste gekende Proth-priemgetal, dat is een priemgetal van de vorm $k\times 2^n+1$ met $k$ oneven. En het is het enige in de top 10 van grootste gekende priemgetallen dat geen Mersenne-priemgetal is, een priemgetal van de vorm $2^n-1$. (check The Largest Known Primes Database van Chris Caldwell).

Bovendien is deze nieuwe vondst van Szabolcs het grootste Colbert-getal tot nu toe. Dit is een megapriemgetal (een priemgetal met meer dan 1 miljoen cijfers) in Proth-gedaante $k\times 2^n+1$ waarbij $k$ tot de 17 getallen behoort in het lijstje van Seventeen or Bust. Omdat $k=10223$ inderdaad op dit lijstje staat, wordt deze nieuw flinke telg in de priemfamilie dus een Colbertgetal genoemd, tenminste door sommige rare, met de waanzin flirtende wiskundigen (voor het gemak doen we alsof we jullie vraag “Zijn er dan nog anderen?” niet gehoord hebben). De benaming verwijst namelijk naar Stephen Colbert, de gastheer van de populaire Amerikaanse comedy show The Colbert Report. Deze man heeft niets met de zaak te maken, maar het is een running gag voor mensen die namen verzinnen om allerlei dingen naar hem te vernoemen, bij voorkeur als er totaal geen verband bestaat met Colbert. Een brug in Hongarije, een smaak van Ben&Jerry, een spin in California,…, en nu dus ook een speciale familie van megapriemgetallen.colbertMaar de recente ontdekking van Szabolcs is vooral interessant omdat we nu weten dat 10223 geen Sierpinski-getal is, en dat dus enkel21181, 22699, 24737, 55459 en 67607 nog kanshebbers zijn om het Selfridge-getal 78557 zijn status van kleinste Sierpinski-getal te ontnemen. Als de lezer zich door deze hoeveelheid aan nietszeggende informatie en mystieke getallen verpletterd voelt, kunnen we hem direct geruststellen. Dit was de bedoeling. Maar lees vooral verder, een en ander zal uitgelegd worden. Wanneer op het einde niet alles duidelijk geworden is, dan zal toch tenminste het inzicht verkregen zijn dat niet iedereen hetzelfde idee heeft over nuttig tijdverdrijf.

PrimeGrid, het wereldwijde netwerk van priemgetallenjagers en gebundelde computerkracht is zo mogelijk nog geeker, nog onfrisser en nog losser van de wereld dan de nooit slapende community van gamers. Een grote hap rekentijd van PrimeGrid gaat naar het project GIMPS, dat zich beperkt tot het zoeken naar Mersenne-priemgetallen (van de vorm $2^n – 1$), een succesvolle strategie zoals blijkt uit de gebroken records voor grootste priemgetal van de laatste 25 jaar, die alle een Mersenne-vorm hadden. De lezer kan zijn geheugen opfrissen door onze blogpost van begin 2016 ter gelegenheid van het laatste record te herlezen (nog steeds op naam van Cooper, een priemgetal van meer dan 22 miljoen cijfers).

Maar nu willen we jullie aandacht vestigen op een andere ‘subcultuur’ binnen PrimeGrid, de nachtridders van het project Seventeen or Bust, officieel opgedoekt in april 2016, maar enkele koppige echo’s blijven sindsdien nagalmen in de donkere kelders van PrimeGrid. In dit deelproject wordt op priemgetallen gejaagd van de vorm $k\cdot 2^n + 1$, zogenaamde Proth-priemgetallen. Je vertrekt hierbij altijd met een oneven getal $k$, bijvoorbeeld $k=9$, vermenigvuldigt dit met 2 of een macht van 2, bijvoorbeeld $9\times 2 = 18$, en telt er eentje bij op, bijvoorbeeld $18+1=19$. In dit voorbeeld hebben we geluk, want we vinden een (Proth-)priemgetal 19. Hoe meer cijfers je wil voor je Proth-priemgetal, hoe langer je zal moeten zoeken. Het is zelfs zo dat je met wat pech een ongelukkig getal $k$ als beginwaarde kiest waarvoor $k\cdot 2^n+1$ nooit een priemgetal wordt, voor geen enkele tweemacht $2^n$. In 1960 bewees de Poolse wiskundige Waclaw Sierpinski dat er zelfs oneindig veel van zulke (oneven) getallen $k$ bestaan die nooit tot een Proth-priemgetal $k\cdot 2^n+1$ leiden. Deze ‘ongelukkige’ keuzes voor de beginwaarde $k$ werden vanaf toen Sierpinski-getallen genoemd. Weten dat er oneindig veel zijn is één ding, maar effectief een Sierpinski-getal vinden (met garantiebewijs) is iets anders. In 1962 bewees de Amerikaan Selfridge dat 78557 een Sierpinski-getal. Hij had er zo lang achter gezocht dat hij veronderstelde dat dit het kleinste Sierpinski-getal is. In die tijd van beperkte computermogelijkheden was dit een wilde gok, maar intussen geloven de meeste wiskundigen dat hij het bij het rechte eind had. In januari 2002 had men voor bijna alle getallen $k$ kleiner dan 78557 gevonden dat ze aanleiding gaven tot een priemgetal van de vorm $k\cdot 2^n+1$ (en dus niet de Sierpinski-eigenschap hadden), maar er bleven nog zeventien lastige kandidaten voor Sierpinski-getallen kleiner dan 78557, die dus het vermoeden van Selfridge konden tegenspreken. Louis Helm, Ann Arbor en David Norris, twee informaticastudenten en een programmeur uit Michigan (wellicht alle drie met obligatoire ‘ponytail’) wilden deze zaak eens en voor altijd uitklaren. In maart 2002 werd onder hun impuls Seventeen or Bust geboren, een computernetwerk dat de berekeningen over de processoren van meer dan duizend vrijwilligers distribueerde, met als bedoeling het lijstje van 17 eventuele Sieprinski-getallen een voor een te schrappen. Een bezigheid als een ander zullen we maar denken, eens iets anders dan met Super Mario de kerstballen te ontwijken die door Lemma Koopa gegooid worden.

In het veertienjarige bestaan van dit project was Seventeen or Bust er in geslaagd om 11 van de 17 overgebleven kandidaten voor een Sierpinsky-getal kleiner dan 78557 te ontmaskeren. De zes overblijvers waren:10223, 21181, 22699, 24737, 55459, and 67607.
Wie bij de les is, begrijpt dus dat een kandidaat $k$ geëlimineerd wordt zodra een bijbehorend Proth-priemgetal $k\cdot 2^n + 1$ ontdekt wordt. Dit was en is een lastige en tijdrovende klus omdat deze lijst niet voor niets de laatste der Sieprinsky-kandidaten kleiner dan 78557 bevat. Het betreffende Proth-priemgetal is dan ook van aanzienlijke lengte, maar krijgt na de verlossende positieve priemtest de eretitel van Colbert-getal.

In oktober 2016 kreeg Szabolcs dankzij het geleverde werk van de Seventeen or Bust community een kanshebber om 10223 te schrappen, het mogelijke Colbert-getal $10223\times 2^{31172165}+1$. Hij gebruikte een handige implementatie van de LLR-priemtest en bijna negen dagen rekentijd op zijn Intel Core i7-4770 CPU @ 3.40GHz met 12GB RAM om deze zaak uiteindelijk te bevestigen.

Voor de volledigheid geven we hieronder het lijstje van de 17 $k$-waarden die in 2002 aan de wieg stonden van Seventeen or Bust. Sinds november 2016 blijven er nog 5 over, de andere 12 bleken geen Sierpinsky-getal, getuige het geassocieerde Proth-priemgetal dat er naast staat.

$$\begin{array}{c|c|c}
\mbox{kandidaat Sierpinski-getal }k & \mbox{ontkrachtend priemgetal  }k2^n+1 & \mbox{aantal cijfers }\\
\hline
4847 &     4847\times 2^{3321063}+1&999744\\
5359 & 5359\times 2^{5054502}+1         &1521561\\
10223& 10223\times 2^{31172165}+1         &9383761    \\
19249& 19249\times 2^{13018586}+1     &3918990    \\
21181&        &    \\
22699&        &    \\
24737&        &    \\
27653& 27653\times 2^{9167433}+1         &2759677    \\
28433& 28433\times 2^{7830457}+1     &2357207    \\
33661&33661\times 2^{7031232}+1     &2116617    \\
44131&44131\times 2^{995972}+1         &299823    \\
46157&46157\times 2^{698207}+1         &210186    \\
54767&54767\times 2^{1337287}+1         &402569    \\
55459&        &    \\
65567&65567\times 2^{1013803}+1    &305190    \\
67607&        &    \\
69109&69109\times 2^{1157446}+1&348431
\end{array}$$

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Een reactie geven