Algemeen

Reken mee met ABC heeft op het moment 159.029 deelnemers.

Gezamelijk gebruiken zij 236.267 computers om te zoeken naar abc drietallen.

Er zijn 298.450.889.052.826.752 drietallen doorgerekend waarvan 34.208.964 abc-drietallen zijn!

                   

Algoritme

21 Mar 2007

Als je op zoek gaat naar abc-drietallen, wil je hier graag een snelle methode voor, en je wilt zeker weten dat je alle drietallen vindt. Nou is het niet mogelijk om alle abc-drietallen te vinden, omdat dit er oneindig veel zijn. In dit artikel wordt het algoritme beschreven dat door BOINC gebruikt wordt om op een efficiënte manier alle abc-drietallen te vinden met a, b en c kleiner dan een bepaald (groot) getal N.

Een abc-drietal is een drietal waarin het radicaal van het drietal kleiner is dan c. In plaats van het radicaal van een drietal berekenen, kunnen we ook het radicaal van één getal berekenen. We nemen dan alle verschillende priemfactoren van het getal, en vermenigvuldigen deze met elkaar. Omdat getallen a, b en c die een abc-drietal vormen onderling ondeelbaar zijn, is het radicaal van het drietal a, b en c hetzelfde als het radicaal van het getal a× b× c.

Wat is het radicaal van 28?
Je antwoord:
  Je antwoord is juist!Helaas, je antwoord is niet juist.Het juiste antwoord is: 14

Om alle drietallen te kunnen vinden, moeten we eerst weten hoe we alle getallen kleiner dan N met een bepaald radicaal kunnen vinden. Stel eerst eens dat we alle getallen kleiner dan N met radicaal 2 willen vinden. Een getal kan alleen radicaal 2 hebben als zijn enige priemdeler 2 is. Dit betekent dat alleen machten van 2 radicaal 2 hebben. Om alle machten van 2 te vinden onder de N, hoeven we alleen maar 2 steeds met 2 te vermenigvuldigen, tot we een getal krijgen dat groter is dan N. Als we hier even over nadenken, zien we dat dit niet alleen voor 2 zo is. Als we alle getallen kleiner dan N willen vinden met radicaal p, waarbij p een priemgetal is, moeten we p steeds met zichzelf vermenigvuldigen, net zolang tot we een getal krijgen dat groter is dan N. Zo'n proces gaat heel snel: het enige wat je moet doen is met p vermenigvuldigen, en kijken of het getal wat je krijgt groter is dan N of niet. Voor N=100000 doet een computer die een beetje snel en modern is, hier niet langer dan een seconde over.

Maar wat gebeurt er nu als het radicaal wat we willen geen priemgetal is? Kijk bijvoorbeeld naar 6, dit is 2x3. Een getal met radicaal 6 mag dus alleen maar priemdelers 2 en 3 hebben. Als we nu alle getallen met radicaal 6 onder een getal N willen vinden, dan beginnen we met 6. Dit vermenigvuldigen we met 2, net zo lang tot we boven N uitkomen. Nu vermenigvuldigen we alle getallen die we gevonden hebben met 3, en kijken we weer welke er nog kleiner zijn dan N, en welke niet meer. Hierna vermenigvuldigen we weer alle nieuwe getallen met 3, en dit blijven we doen, tot we geen nieuwe getallen meer vinden die kleiner zijn dan N. Dan hebben we dus alle getallen gevonden met radicaal 6 die kleiner zijn dan N. Stel namelijk dat een getal kleiner dan N radicaal 6 heeft, dan moet dit van de vorm 2k× 3m zijn, met k en m gehele getallen. We hebben alle getallen van de vorm 2k× 3 gevonden, totdat k zo groot was dat 2k× 3 groter is dan N. Daarna hebben we alle getallen 2k×32 geprobeerd, totdat k te groot werd, enzovoorts. Ook dit proces gaat vrij snel. Je hoeft alleen maar met 2 en 3 te vermenigvuldigen, en te controleren welke getallen kleiner zijn dan N. Dus ook dit duurt niet langer dan een paar seconden.

Nu kunnen we ook kijken wat er gebeurt met andere radicalen. Het radicaal van een getal vind je door alle verschillende priemfactoren met elkaar te vermenigvuldigen. Een radicaal is dus altijd een getal waar geen enkele priemfactor twee keer in zit. Dit betekent dat 6 wel een radicaal kan zijn, want dit is 2x3, maar 4 kan geen radicaal zijn, want 4 is 2x2, dus geen product van allemaal verschillende priemfactoren.

Welk van de getallen 22, 45 en 60 is een radicaal?
Je antwoord:
  Je antwoord is juist!Helaas, je antwoord is niet juist.Het juiste antwoord is: 22

Stel nu dat je een getal hebt wat een product is van allemaal verschillende priemfactoren. Dan kan dit getal een radicaal zijn. Om nu alle getallen te vinden kleiner dan N met dit radicaal, doen we weer ongeveer hetzelfde als net. We beginnen met het product van alle priemfactoren, dus het radicaal zelf. Nu vermenigvuldigen we dit met de kleinste priemfactor, net zo lang tot we een getal hebben dat groter is dan N. Dan nemen we de tweede priemfactor, en vermenigvuldigen we alle gevonden getallen met dit getal, zo vaak mogelijk. Daarna nemen we het volgende priemgetal, en vermenigvuldigen we weer alle getallen die we tot nu toe hebben gevonden met dit priemgetal. Zo gaan we door tot we alle priemgetallen in het radicaal hebben gehad. Je moet nu vaker controleren of een getal groter is dan N of niet, maar nog steeds is het een vrij snel proces.

We hebben net al gezien welke getallen geschikt zijn als radicaal. Dit zijn alle getallen waar elke priemfactor die er in zit, maar één keer in zit. Dit betekent dat elk getal dat niet deelbaar is door een kwadraat van een priemgetal, een radicaal is. Nu willen we graag alle mogelijke radicalen vinden die kleiner zijn dan een getal N. Hiervoor moeten we eerst weten hoe we alle priemgetallen kunnen vinden die kleiner zijn dan N.

De zeef van Eratosthenes

Het vinden van alle priemgetallen onder de N doen we met een methode die door de Griekse Eratosthenes in ongeveer 240 jaar voor Christus is bedacht. De methode gaat als volgt: je schrijft alle getallen van 2 tot en met N op. Je begint met 2, omdat 1 geen priemgetal is. Nu herhaal je steeds twee stappen:
1. Omcirkel het eerste getal wat nog niet doorgestreept is.
2. Streep alle veelvouden van het getal wat je net omcirkeld hebt weg.
Je omcirkelt dus eerst 2, daarna streep je alle veelvouden van 2 weg. Dit zijn de getallen 4, 6, 8, 10, 12 etc. Dan omcirkel je het eerste getal wat nog niet doorgestreept is, dus 3, daarna streep je alle veelvouden van 3 weg. Zo kun je doorgaan tot alle getallen omcirkeld of doorgestreept zijn. Alle omcirkelde getallen zijn nu priemgetallen, omdat ze niet deelbaar zijn door een kleiner getal (dan had je ze namelijk wel weggestreept, en konden ze dus niet omcirkeld zijn).


De zeef van Eratosthenes

Het vinden van alle radicalen onder de N gaat ongeveer op dezelfde manier. Weer doe je steeds twee stappen:
1. Bekijk het eerste niet doorgestreepte getal. Als dit geen priemgetal is, ga je naar het volgende niet doorgestreepte getal. Als je bij een priemgetal bent, omcirkel je het getal en ga je naar stap 2.
2. Streep alle getallen door die deelbaar zijn door het kwadraat van het priemgetal wat je net omcirkeld hebt.
Alle getallen die niet doorgestreept zijn, kunnen nu een radicaal zijn. Je hebt namelijk alle getallen weggestreept die deelbaar zijn door het kwadraat van een priemgetal.

We hebben nog iets meer informatie nodig voor we alle abc-drietallen met c kleiner dan N kunnen vinden. Hiervoor gaan we kijken naar een willekeurig abc-drietal. Stel dat a, b en c alledrie kleiner zijn dan N en dat ze een abc-drietal vormen. We bekijken nu de radicalen van a, b en c. Het getal met het kleinste radicaal noemen we x, het getal met het middelste radicaal noemen we y, en het getal met het grootste radicaal noemen we z. Dus: r(x)<r(y)<r(z). We sorteren a, b en c dus op radicaal. We weten dat x, y en z onderling ondeelbaar zijn, want a, b en c zijn dat ook. Er geldt dus r(xr(yr(z)=r(xyz). Er geldt natuurlijk ook r(xyz)=r(abc), want het zijn dezelfde getallen, in een andere volgorde. Omdat a, b en c een abc-drietal vormen, weten we ook dat het radicaal van abc kleiner is dan c, dus zeker kleiner dan N. We weten dat r(y)2 is kleiner dan r(yr(z), want r(y) is kleiner dan r(z). Ook weten we dat r(x) altijd groter of gelijk is aan 1, dus is r(y)2 ook kleiner dan r(x)r(y)r(z)=r(xyz). Hieruit volgt dat r(y)2 kleiner is dan N, dus dat r(y) kleiner is dan N. Dit betekent dat we alle mogelijke waarden voor r(y) gewoon uit kunnen rekenen, we hebben namelijk al gezien hoe we alle mogelijke radicalen onder een bepaald getal uit kunnen rekenen.

We hebben nu een maximum voor r(y). Zo'n maximum kunnen we ook voor r(x) maken. Omdat r(y)2 kleiner is dan r(y)r(z), geldt ook dat r(x)r(y)2 kleiner is dan r(x)r(y)r(z), wat weer kleiner is dan N. Hieruit volgt dat r(x) kleiner is dan N/r(y)2.

Wat hierboven staat, geldt voor alle abc-drietallen. Nu kunnen we dus alle abc-drietallen met a, b en c kleiner dan N vinden. Dit doen we in een aantal stappen:
1. We vinden alle mogelijke radicalen die kleiner zijn dan N. Dit zijn alle mogelijke radicalen voor y.
2. We vinden alle getallen met dit radicaal, die kleiner zijn dan N. Dit zijn alle mogelijke getallen voor y.
3. Bij elk radicaal wat we voor y hadden gevonden, zoeken we alle radicalen voor x. Dit zijn de radicalen die kleiner zijn dan N/r(y)2.
4. Bij elk radicaal wat we voor x vinden, zoeken we alle getallen kleiner dan N, met dit radicaal. Dit zijn alle mogelijke getallen voor x, bij een bepaalde waarde van r(y).
Met de vorige vier stappen hebben we allemaal waarden voor y en bijbehorende waarden voor x gevonden. We moeten hier nog een z bij vinden, zo dat de drie getallen een abc-drietal kunnen vormen. Het kan zijn dat z de c is, dan geldt dus x+y=z. Het kan ook zijn dat x of y de c is. Dan geldt x-y=z, of y-x=z, dus de absolute waarde van x-y moet dan gelijk zijn aan z. De laatste stappen zijn dus:
5. Vind bij elke tweetal waarden voor x en y de twee mogelijke bijbehorende waarden voor z (dit zijn dus x+y en |x-y|.
6. Vind het radicaal van z en controleer of x, y en z een abc-drietal vormen.

Met dit stappenplan vinden we dus alle abc-drietallen met a, b en c kleiner dan N. We hebben al gezien dat de eerste vier stappen niet heel veel tijd kosten. De vijfde stap is alleen maar optellen of aftrekken. De eerste vijf stappen kosten dus relatief weinig tijd. Met deze vijf stappen worden een heleboel drietallen weggestreept, we houden nog maar een relatief kleine selectie van mogelijke abc-drietallen over. We hoeven dus voor veel minder drietallen te controleren of het een abc-drietal is, dan in de meeste algoritmes het geval is. Dit scheelt een hoop tijd, en maakt dit algoritme snel. In de zesde stap moet steeds de priemontbinding van z gevonden worden. Voor grote z kan dit veel tijd kosten. Dit is een stap die in elk algoritme uitgevoerd moet worden, dus het maakt ons algoritme niet langzamer in vergelijking met andere algoritmes.

Auteur: Sietske Tacoma