Sedmnáct nebo Busta - Seventeen or Bust
Sedmnáct nebo Busta byl distribuované výpočty projekt zahájený v březnu 2002 k řešení posledních sedmnácti případů v EU Sierpinského problém. Projekt vyřešil jedenáct případů, než jej ztráta serveru v dubnu 2016 donutila zastavit provoz. Práce na problému Sierpinski se přesunuly do PrimeGrid, který v říjnu 2016 vyřešil dvanáctý případ.[1] Od dubna 2020 zůstává nevyřešeno pět případů[Aktualizace].[2]
Cíle
Cílem projektu bylo dokázat, že 78557 je nejmenší Sierpinského číslo, tj. nejméně liché k takhle k·2n+1 je kompozitní (tj. ne primární ) pro všechny n > 0. Když projekt začal, bylo jich tam jen sedmnáct k <78557, pro které nebylo známo, že odpovídající sekvence obsahuje prvočíslo.
Pro každou z těchto sedmnácti hodnot k, projekt hledal prvočíslo v sekvence
- k·21+1, k·22+1, …, k·2n+1, …
testování kandidátských hodnot n použitím Prothova věta. Pokud byl jeden nalezen, dokázalo to k nebylo Sierpinského číslo. Pokud bylo cíle dosaženo, domnělý Odpověď 78557 na Sierpinského problém by se ukázala jako pravdivá.
Existuje také možnost, že některé ze sekvencí neobsahují žádná prvočísla. V takovém případě by hledání pokračovalo navždy a hledalo se prvočísla, kde žádné nelze najít. Existují však určité empirické důkazy, které naznačují, že domněnka je pravdivá.[3]
Každé známé Sierpinského číslo k má malý krycí sada, konečná sada prvočísel s alespoň jedním dělením k·2n+1 pro každého n> 0 (nebo jinak k má algebraické faktorizace pro některé n hodnoty a konečná prime sada, která funguje pouze pro zbývající n[4]). Například pro nejmenší známé Sierpinského číslo 78557 je krycí sada {3,5,7,13,19,37,73}. Pro další známé číslo Sierpinski 271129 je krycí sada {3,5,7,13,17,241}. Každá ze zbývajících sekvencí byla testována a žádná nemá malou krycí sadu, takže existuje podezření, že každá z nich obsahuje prvočísla.
Druhá generace klienta byla založena na Prime95, který se používá v Skvělé internetové vyhledávání Mersenne Prime V lednu 2010 zahájil projekt Seventeen or Bust spolupráci s PrimeGrid který software používá LLR za testy týkající se problému Sierpiński.[2]
Server Seventeen or Bust selhal během dubna 2016, kdy došlo ke ztrátě serveru a záloh z důvodů, které nebyly zveřejněny. Projekt již není aktivní. Práce na problému Sierpinski pokračují v PrimeGrid.[5][6]
Průběh hledání
Dosud bylo nalezeno dvanáct prvočísel, jedenáct původních Seventeen nebo Bust a dvanáctý projekt SoB PrimeGrid:[2]
| k | n | Číslice k·2n+1 | Datum objevu | Nalezeno uživatelem |
|---|---|---|---|---|
| 46,157 | 698,207 | 210,186 | 26. listopadu 2002 | Stephen Gibson |
| 65,567 | 1,013,803 | 305,190 | 3. prosince 2002 | James Burt |
| 44,131 | 995,972 | 299,823 | 6. prosince 2002 | zařízení (přezdívka) |
| 69,109 | 1,157,446 | 348,431 | 7. prosince 2002 | Sean DiMichele |
| 54,767 | 1,337,287 | 402,569 | 22. prosince 2002 | Peter Coels |
| 5,359 | 5,054,502 | 1,521,561 | 6. prosince 2003 | Randy Sundquist |
| 28,433 | 7,830,457 | 2,357,207 | 30. prosince 2004 | Anonymní |
| 27,653 | 9,167,433 | 2,759,677 | 8. června 2005 | Derek Gordon |
| 4,847 | 3,321,063 | 999,744 | 15. října 2005 | Richard Hassler |
| 19,249 | 13,018,586 | 3,918,990 | 26. března 2007 | Konstantin Agafonov |
| 33,661 | 7,031,232 | 2,116,617 | 13. října 2007 | Sturle Sunde |
| 10,223 | 31,172,165 | 9,383,761 | 31. října 2016[7][1] | Péter Szabolcs |
| 21,181 | ≳ 32,000,000 | ≳ 9,632,964 | (Probíhá vyhledávání) | |
| 22,699 | ≳ 32,000,000 | ≳ 9,632,964 | (Probíhá vyhledávání) | |
| 24,737 | ≳ 32,000,000 | ≳ 9,632,964 | (Probíhá vyhledávání) | |
| 55,459 | ≳ 32,000,000 | ≳ 9,632,964 | (Probíhá vyhledávání) | |
| 67,607 | ≳ 32,000,000 | ≳ 9,632,964 | (Probíhá vyhledávání) | |
Od dubna 2020[Aktualizace] největší z těchto prvočísel, 10223 · 231172165+1, je největší známé prvočíslo to není Mersenne prime.[8] Prvočísla na tomto seznamu o délce více než jednoho milionu číslic jsou šest známých „Colbertových čísel“, která jsou náhodně pojmenována Stephen Colbert. Ty jsou definovány jako prvočísla, která vylučují zbývajícího kandidáta na Sierpinského číslo.[9][10]
Každé z těchto čísel má dostatek číslic, aby vyplnilo středně velké číslo román, alespoň. Projekt rozděloval čísla mezi své aktivní uživatele v naději, že najde prvočíslo v každé z pěti zbývajících sekvencí:
- k·2n+1, pro k = 21181, 22699, 24737, 55459, 67607.
V březnu 2017 n za posledních pět překročil 31 000 000 k hodnoty. V té době se PrimeGrid rozhodl pozastavit testování, aby provedl dvojitou kontrolu všech těch menších n hodnoty, pro které se ztratil testovací zbytek Proth, nebo pro které nebyl výsledek úspěšně ověřen dvěma nezávislými výpočty na různých počítačích.[11] Testování pokračovalo po dokončení dvojité kontroly 10. října 2019, což trvalo přibližně dva a půl roku.[12]
Aktuální stav zbývajících multiplikátorů lze vidět na webových stránkách PrimeGrid.[13]
Modulární omezení
Každý multiplikátor má modulární omezení pro exponenta n, za předpokladu, že existuje. Například pro k = 21 181 stačí zkontrolovat pouze hodnoty n shodné s 20 (mod 24); krycí sada pro všechny ostatní výrazy je {3, 5, 7, 13, 17}. Podobně pro k = 22 699 pouze výrazy s n shodné s 22 (mod 24) jsou kandidáti, protože sada všech ostatních výrazů zahrnuje krycí sadu {3, 5, 7, 13, 17}.
Viz také
- Riesel Sieve, související projekt distribuovaných výpočtů pro čísla formuláře k·2n−1
- Seznam projektů distribuovaného výpočtu
- PrimeGrid, největší hledání prvočísel.
- Počítačem podporovaný důkaz
Reference
- ^ A b „PrimeGrid's Seventeen or Bust Subproject, Official Announcement“ (PDF). 2016.
- ^ A b C Michael Goetz. „Sedmnáct nebo Busta a problém Sierpinski (fórum PrimeGrid)“.
- ^ Chris Caldwell. "Sierpinski číslo".
- ^ „Má každé Sierpinského číslo pokrytí konečnou kongruencí?“. Stack Exchange. 4. března 2016.
- ^ Michael Goetz. „Re: Server nefunguje?“. Archivovány od originál dne 28. června 2016.
- ^ Michael Goetz. „Re: Aktualizace na seveneenorbust.com“.
- ^ Vlákno fóra PrimeGrid
- ^ „Dvacet největších známých prvočísel“. Prvotní stránky. Citováno 7. listopadu 2016.
- ^ Colbert Number - od Wolfram MathWorld. Mathworld.wolfram.com (05.04.2009). Citováno 2014-05-11.
- ^ Hlavní glosář: Colbertovo číslo. Primes.utm.edu. Citováno 2014-05-11.
- ^ Michael Goetz (20. března 2017). „SoB Double Check has started“. Fórum PrimeGrid.
- ^ Michael Goetz (10. října 2019). „Dvojitá kontrola SoB je HOTOVÁ !!!“. Fórum PrimeGrid.
- ^ „Statistiky sedmnácti nebo poprsí“. PrimeGrid.