Riesel Sieve

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Riesel Sieve is een distributed computingproject dat probeert om het vermoeden van Riesel te bewijzen. Dit vermoeden luidt dat 509203 het kleinste rieselgetal is. Dit project draait gedeeltelijk onder het BOINC-platform. Een soortgelijk project is Seventeen or bust, dat naar sierpinskigetallen zoekt.

Het bewijzen van de stelling[bewerken]

Om deze stelling te bewijzen moet bij iedere oneven k kleiner dan 509203 een n gezocht worden zodanig dat k \cdot 2^n-1 een priemgetal is. De priemgetallen bij deze k's zijn immens groot, het grootste gevonden priemgetal is 275293 \cdot 2^{2335007}-1. Dit is een getal van 702913 cijfers.

LLR[bewerken]

Voor het bewijzen van de primaliteit van getallen van de vorm k \cdot 2^n-1 is een test ontwikkeld, de Lucas-Lehmer-Rieseltest. Deze is gebaseerd op de bestaande Lucas-Lehmertest voor mersennegetallen. Deze test kan voor ieder k-n paar bewijzen of het priem is. Maar om dit voor ieder paar te testen, zou veel te lang duren, daarom wordt ook gebruikgemaakt van de Proth sieve.

Proth sieve[bewerken]

In plaats van het testen of een enkel k-n-paar priem of composiet is, kan je ook een factor tegen alle k-n-paren houden. Dit gebeurt door middel van de Proth sieve. Hierbij wordt een range van mogelijke factoren gedownload en vervolgens wordt getest of er een of meerdere paren zijn die een factor uit deze range hebben. Als dit zo is, kunnen deze paren geen priemgetal zijn en hoeft het dus niet meer door de LLR-test. Met deze zeef worden dus alleen negatieve resultaten gevonden (k-n-paren die composiet zijn) en kan men dus geen priemgetallen vinden. Een factor gevonden met de zeef is waardevoller dan een LLR-test, want binnen enkele milliseconden kan de factor worden geverifieerd, maar om een LLR-test te verifiëren moet hij helemaal opnieuw worden gedaan.

BOINC[bewerken]

Het project draait niet meer zelfstandig. Het is overgenomen door het project PrimeGrid, waar je ook naar andere priemgetallen kunt zoeken. Je kan nog wel specifiek naar Rieselgetallen zoeken.[1]

Resultaten[bewerken]

Van de 101 mogelijke rieselkandidaten bij het begin van het project zijn er nog maar 66 over. Dit zijn de volgende getallen:

2293, 9221, 23669, 31859, 38473, 40597, 46663, 65531, 67117, 74699, 81041, 93839, 97139, 107347, 113983, 121889, 123547, 129007, 141941, 143047, 146561, 161669, 162941, 191249, 192971, 206039, 206231, 215443, 226153, 234343, 245561, 250027, 252191, 273809, 304207, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 353159, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 398023, 402539, 409753, 415267, 428639, 444637, 470173, 474491, 477583, 485557, 485767, 494743, 502573.

Er zijn tot nu toe 29 priemgetallen gevonden door dit project die 29 mogelijke k's hebben verwijderd.

Gebruiker k n cijfers datum
Mackerel 469949 1649228 496472 2007-10-27
Cipher 342673 2639439 794556 2007-04-24
DarkStar 26773 2465343 742147 2006-11-30
botXXX 275293 2335007 702913 2006-09-21
bwhite 114487 2198389 661786 2006-05-23
Auritania 196597 2178109 655681 2006-05-07
maefly 450457 2307905 694754 2006-03-27
mackerel 467917 1993429 600088 2005-12-24
frmky 417643 1800787 542097 2005-10-04
NeoLogic 357659 1779847 535793 2005-09-24
tekno 110413 1591999 479244 2005-06-07
Footmaster 234847 1535589 462264 2005-05-07
tekno 325627 1472117 443157 2005-04-04
pvh 149797 1414137 425703 2005-03-13
Rseffco 502541 1199930 361221 2004-12-21
neologic 71009 1185112 356759 2004-12-06
sean 350107 1144101 344414 2004-10-23
footmaster 500621 1138518 342734 2004-10-18
Magnus 504613 1136459 342114 2004-10-16
SISU 412717 1084409 326445 2004-08-24
footmaster 150847 1076441 324046 2004-08-14
hemigrid 309817 901173 271286 2004-06-07
mercutio 192089 1395688 420149 2004-05-09
neologic 170591 866870 260959 2004-04-15
mercutio 93997 864401 260216 2004-04-01
neologic 460139 779536 234669 2004-03-26
spooty 246299 752600 226561 2004-01-23
cipher 279703 616235 185511 2004-01-06
sean 261221 689422 207542 2003-12-22

Rieselsieve draait tegenwoordig onder PrimeGrid en ook daar zijn 8 priemgetallen gevonden:

Gebruiker k n datum
Dmitry Domanov 162941 2993718 2012-02-02
Jaakko Reinman 353159 4331116 2011-05-31
Scott Brown 141941 4299438 2011-05-26
Alexey Tarasov 415267 3771929 2011-05-08
Jakub Luszczek 123547 3804809 2011-05-08
Adrian Schori 65531 3629342 2011-04-05
Brett Melvold 428639 3506452 2011-01-14
Jonathan Pritchard 191249 3417696 2010-11-21

Externe links[bewerken]

Bronnen, noten en/of referenties