DPC zoekt oplossing voor het Sierpinskiprobleem

Seventeen or Bust (in het kort SoB) is een gedistribueerde aanval op het Sierpinskiprobleem. Het Sierpinskiprobleem gaat over de zogenaamde Prothgetallen. Dit zijn getallen die geschreven kunnen worden in de vorm N=k*2ⁿ+1, met k en n gehele getallen. Als bij een bepaalde waarde van k geen enkele waarde van n een priemgetal N oplevert, dan is k een Sierpinskigetal. Het probleem is het vinden van het kleinste Sierpinskigetal.

In 1962 veronderstelde John Selfridge dat de door hem gevonden k=78.557 het kleinste Sierpinskigetal is. Nu, 42 jaar later, is dit echter nog steeds niet bewezen. Seventeen or Bust is van plan om dit bewijs te leveren. De toegepaste tactiek is simpel: bij elke waarde van k kleiner dan die van Selfridge moet een waarde van n gevonden worden waarbij het Prothgetal N een priemgetal is. Daarmee wordt immers bewezen dat het kleinere getal geen Sierpinskigetal is. Bij het starten van het project waren er nog zeventien k's waarvoor dit gedaan moest worden (vandaar de naam Seventeen or Bust). Intussen zijn er nog elf over.

De k-waarden uitrekenen is nogal veel werk, en hier komt de wereld van de Dutch Power Cows om de hoek kijken. Wij proberen dit probleem samen met concurrerende teams uit de hele wereld door middel van Distributed Computing op te lossen. Een interessante bijkomstigheid bij dit project is dat het uitsluiten van een waarde van k gepaard gaat met het vinden van een zeer groot priemgetal. Voor k=5.359 werd bijvoorbeeld pas bij n=5.054.502 een priemgetal aangetroffen, dit 1.521.561-cijferige getal is nu het op vier na grootste priemgetal dat ooit gevonden is. Grote priemgetallen zijn in bepaalde cryptografische algoritmes, zoals RSA, zeer belangrijk.

Het project is opgezet door Louis Helm, student aan de universiteit van Michigan en David Norris, medewerker aan de universiteit van Illinois. In maart 2002 begonnen zij met het project waarna het al snel door de Distributed Computing-community's, zoals DPC, werd opgenomen. Ons team staat nu wereldwijd vijfde met vier Amerikaanse teams boven zich. Natuurlijk willen we nog verder stijgen om de wereld te laten zien dat een klein land als Nederland behoorlijk krachtig kan zijn als het op Distributed Computing aankomt. Op dit moment gaat het helaas net te langzaam om vooruitgang te boeken, maar met een beetje extra hulp is een plaats bij de eerste drie mogelijk, en wellicht op langere termijn nog meer.

Geïnteresseerd?

Voel jij je geroepen om het Sierpinskiprobleem aan te pakken en de Nederlandse eer in de Distributed Computing-wereld hoog te houden? Kijk dan eens in de installatie-FAQ van SoB hoe je Dutch Power Cows kunt joinen. Op het DPC-forum worden ranglijsten (DPCH's) samengesteld van wie wat inlevert, zodat je kunt zien hoeveel je bijdraagt, en dat zorgt meestal voor een leuke interne 'concurrentie' met de andere DPC leden. Ook heb je natuurlijk via deze manier de mogelijkheid om de wiskundige wereld een handje te helpen zonder dat je wiskundige hoeft te zijn. Je computer doet al het rekenwerk en doet dat op zo'n manier dat je er niet eens last van hebt: de SoB-cliënt geeft namelijk alle andere programma's voorrang en gaat alleen aan het rekenen als er rekenkracht is die andere programma's niet gebruiken.

Reacties (40)

[Verwijderd]

Hoe weet je nu dat voor een willekeurig getal n er nooi een priemgetal zal worden gevonden? n kan varieren van 0 tot oneindig. Of is het aantoonbaar als je een reeks van uitkomsten N hebt, dat volgende getallen ook geen priemgetal zullen zijn?

[Verwijderd]

Het is in ieder geval nuttig in grafische toepassingen, zoals de Sierpinski triangle en ook in cryptografie.

[TweakMij]

Een opendeur en afgezaagde vraag, maar welke praktische toepassingen liggen er op de plank te wachten, die de oplossing voor het Sierpinskiprobleem nodig hebben? Btw, googlen hielp ni.

[Verwijderd]

Geen. Net zoals het uitrekenen van de 6 bilardste decimaal van Pi geen zin heeft, of zoals het proberen te kraken van een 32-, 64-, of 128bits encryptie geen zin heeft, net zoals...

Enfin, je snapt 'm wel denk ik.

[Countess]

PI heeft zeker wel waarden.
in de hoog preciesie meetkunden BV.

[Verwijderd]

@ Countess:

Ongetwijfeld. Maar boven een X aantal decimalen niet meer. Zoals nu bijvoorbeeld, toch staan er nog geregeld computers te stampen om er weer een paar miljoen decimalen bij te vinden.

[tazitiz]

Waar is dit belangrijk voor? Als je met harde nummers een bewijslast kan plaatsen, of met pure logica, en wat is er sneller.

Het is duidelijk dat bijvoorbeeld schakers gebruik maken van logica en inzicht, en computers van vooral veeeeeeel berekeningen. Wanneer wordt een computer beter in schaken dan de gemiddelde mens en wanneer is hij beter dan de beste mens.

Zelfde als deze Sierpinksi getallen, alleen dan minder populair. Google maar eens op schaken en op sierpinskie

[bille]

jaaaaja.. maar ik denk dat in dit geval het 6 biljardste getal er nog voor kan zorgen dat er een spaceshuttel naast de aarde land.. wel degelijk significant dus!

[Truus]

Grappig zeg, dat "probleem". Overigens vraag ik me toch af in hoeverre je op deze manier het bewijs kunt leveren. Zoals eerder al gezegd, n kan een waarde aannemen van 0 tot oneindig, tot hoever moet er dan gezocht worden door de computer? Bovendien kan een computer vast ook rekenfoutjes maken, dus door hoeveel computers wordt hetzelfde rekenwerk gedaan om zekerheid te krijgen over de resultaten?Ik ben dan wel geen wiskundige, maar wel wetenschappelijk opgeleid (nou ja, bijna dan ).

Het zou mij niks verbazen als dit over een tijdje met snellere en betere computers weer overnieuw gedaan moet worden.

[offtopic]Was er niet ooit iets met Pentium en Pi? Kan me vaag wat herinneren, ik dacht toendertijd dat het om een rekenmachien ging [/offtopic]

[mawashigeri]

Grappig zeg, dat "probleem". Overigens vraag ik me toch af in hoeverre je op deze manier het bewijs kunt leveren. Zoals eerder al gezegd, n kan een waarde aannemen van 0 tot oneindig, tot hoever moet er dan gezocht worden door de computer?

Je gaat uit van de aanname dat k=78.557 (Ik heb niet gezocht maar neem even aan dat er een sluitend wiskundig bewijs ligt voor dit getal.) de kleinste is. Daarna kan je dus gaan verifieren dat alle kleinere getallen een priem opleveren voor zekere n.

Bovendien kan een computer vast ook rekenfoutjes maken, dus door hoeveel computers wordt hetzelfde rekenwerk gedaan om zekerheid te krijgen over de resultaten?

Da's "simpel": je levert een k en een n aan, vul in en reken na of het een priem is (ook geen kleinigheid overigens . Dat kan altijd en bovendien achteraf herhaald worden. De grote initiele rekenklus is het vinden van een getal n -- in het genoemde voorbeeld moest dus voor 5 miljoen (zeer grote) getallen bepaald worden of ze priem waren.

Klein voorbeeld: stel k=2 en n=5000 (niet te ruig nog), dan krijg je een getal van 5001 * log(2)/log(10) = (ruim)1500 cijfers!

Het zou mij niks verbazen als dit over een tijdje met snellere en betere computers weer overnieuw gedaan moet worden.

Waarom? Als je de hele mik tot k=78.557 hebt doorgerekend ben je klaar, aangenomen dat de stelling klopt. Zo niet, dan zit er een getal tussen waarvoor de berekeningen niet stoppen, deze is dan gelijk kandidaat om hogere wiskunde op los te laten.

[Truus]

Je gaat uit van de aanname dat k=78.557 (Ik heb niet gezocht maar neem even aan dat er een sluitend wiskundig bewijs ligt voor dit getal.) de kleinste is. Daarna kan je dus gaan verifieren dat alle kleinere getallen een priem opleveren voor zekere n.

hmmm.. ik zat even verkeerd te denken (lees: ), het uitgangspunt is dus dat er altijd een priemgetal zal worden gevonden voor iedere k kleiner dan 78.557. Als dat lukt ben je klaar. * Ik snap *

[THC]

Nu zul je natuurlijk zien dat er 1 getal straks overblijft waar ze maar geen priemgetal voor kunnen vinden. Wanneer geef je het op. Dat blijft het probleem bij Pi enz. Misschien is er wel een patroon of een bijzonder getal bij het volgende getal. Hoe klein die kans ook lijkt, dit mag je niet uitsluiten.

[Verwijderd]

Is er trouwens wel genoeg onderzoek gedaan of k=78.557 inderdaad een Sierpinskigetal is?

Dat zou nou eens een leuk DPC project wezen, als aangetoont kan worden, dat ook dat getal een priemgetal N oplevert.

[THC]

Ik geloof dat meneer Selfridge niet op zijn getal is gekomen via de brute force methode. Hij heeft gekeken naar de "Covering numbers".

In het geval van zijn 78557 zijn dit de nummers: 3, 5, 7, 13, 19, 37, 73

Met deze getallen is het mogelijk om alle getallen te maken die te maken zijn met de Sierpinski formule: (78557 * 2^n)+1

Dus elk getal wat te maken is met die Sierpinski formule en het getal 78557 is deelbaar door die 7 kleine priemgetallen.
En zo weet je dus dat het geen priem getallen kunnen zijn, anders was het niet deelbaar geweest door die gemeenschappelijke delers.
Hoe hij precies wiskundig heeft bewezen dat het voor deze getallen klopt weet ik niet. Maar hier komt het ongeveer op neer.

Ik hoop dat mijn verhaaltje zo klopt en duidelijk is.

Voor andere getallen en covering sets zie:
http://primes.utm.edu/glossary/page.php?sort=SierpinskiNumber

Maar is er nog een kleinere mogelijkheid. Dat moet SoB gaan bekijken.

[Verwijderd]

Misschien wel handig om te weten is als je een overklokt systeem heb dat de SOB client wel eens onstabiel kan lopen. Het beste is dus een niet overklokt systeem te gebruiken als je de DPC wil helpen bij SOB.

[X-G]

Hoe kom je daarbij? Mijn 2500 @ 3000+ heeft bijna een half jaar SoB gedraaid zonder enige problemen?

[Verwijderd]

Als aangetoond kan worden dat het meedoen aan dit projekt enig nut voor de mensheid heeft doe ik mee, anders pas ik.
(M'n cpu-tijd wordt niet aan nogal onzinnige projecten besteed)

[Verwijderd]

Elk extra stukje kennis in de wetenschap is van oneindige waarde voor de mensheid. Als je toch zo gebrand bent op praktische toepassing, vraag je dan af hoe al onze huidige technologieen tot stand zijn gekomen... Inderdaad, door heel veel schijnbaar onzinnige stukjes van enorme puzzels samen te voegen. Beredeneer nooit of iets enig praktisch nut heeft, omdat een mens meestal niet het grote overzicht heeft om dit te kunnen bepalen. Daar is zijn/haar 'processor' te beperkt voor.

[Verwijderd]

Wat je zegt is zinnig, maar ik werk liever mee aan projecten die direct gerelateerd zijn aan bv het ontwikkelen van een medicijn tegen malaria/kanker etc.
En niet elk stukje kennis is een vooruitgang. Als ik het kan vermijden wil ik liever niet meewerken aan het ontwerpen van een nieuw wapen....

[Chaos]

Het is maar net wat je onder direct verstaat. UD-Grid doet alleen maar een grove selectie van moleculen die heel misschien wel eens iets nuttigs zouden kunnen doen en daarom nader onderzocht moeten worden. Het levert echt geen kant en klare ingrediëntenlijst af voor het perfecte medicijn.

Daarentegen worden er bij SoB bijvoorbeeld met zekerheid grote priemgetallen gevonden en zijn deze ook zeker nuttig voor cryptografie.

[dxta]

Zoals gamen of tweakers.net lezen
Dat heeft echt onwijs veel nut voor de mensheid

Zit er over na te denken om ook een koetje te laten lopen, ik moet alleen nog kiezen welk project.

[madhapee]

vergeet ook niet het stroomverbruik.

Toen ons studenthuis een maandje dpc draaide (24/7) kwam de stroomrekening toch heel wat hoger uit.

[Verwijderd]

Dan doe je mee met een wél nuttig project, zoals het zoeken naar een medicijn tegen kanker.
Neem maar eens een kijkje op het DPC forum van GoT.

[Verwijderd]

Wordt dit een stampede of is dit een gewone wervingspost?

( * 786562 wboelen

[Mizitras]

"de Nederlandse eer" ???

Nederlands/Belgische...
(T.net heeft van de bezoekers, +17% Vlamingen (onze Walen verstaan grotendeels geen Nederlands) en bij de DPC zitten ook heel veel Belgen)

[Verwijderd]

Mijn P4 2.8@3.2 doet niet moeilijk over SOB.
draait als een zonnetje.
Ik hoop trouwens dat we wat nieuwe mensen krijgen bij SOB hoe meer hoe beter!