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!

                   

Op zoek naar abc-drietallen I

11 Jan 2007

We weten dat er oneindig veel abc-drietallen zijn, omdat we zonder al te veel moeite er oneindig veel kunnen maken. Het vinden van alle abc-drietallen is echter veel moeilijker. Je kunt natuurlijk gewoon gaan uitproberen: neem twee getallen a en b, tel ze op om c te krijgen en kijk of het een abc-drietal is. Met deze methode kun je wel abc-drietallen vinden, maar het kost heel veel tijd en moeite. Om alleen al alle drietallen te vinden waarvan het grootste getal hoogstens 1000 is, moet je zo'n 125.000 mogelijkheden afgaan.

Gelukkig zijn er andere methodes ontwikkeld om sneller abc-drietallen te vinden, het liefst ook nog met een goede kwaliteit. Op deze pagina leggen we een van deze methodes uit. Je kunt ook nog hier kijken voor een andere, leuke methode waarmee heel goede abc-drietallen gevonden zijn. Deze methode is wel wat ingewikkelder.

De methode van Jaap Top

Deze methode is bedacht door Jaap Top en gepubliceerd door Tim Dokchitser in 2003. Met deze methode zijn meer dan 40 abc-drietallen gevonden met kwaliteit minstens 1,4. Dat is heel veel als je bedenkt dat er maar zo'n 200 drietallen bekend zijn met kwaliteit minstens 1,4.

Hieronder leggen we stap voor stap uit hoe de methode in zijn werk gaat. Daarna geven we een getallenvoorbeeld, waarbij we deze methode gebruiken om een abc-drietal te vinden.

Stap 1. Kies een getal N. Hoe groter dit getal is, hoe groter straks de getallen a, b en c van je drietal worden.

Stap 2. Kies drie getallen n1, n2 en n3 die allemaal kleiner zijn dan N, maar niet zo heel veel kleiner. Verder is het belangrijk dat de priemfactoren van deze getallen klein zijn en vaak in de getallen voorkomen. Maar let op: een priemfactor van n1 mag niet in n2 en n3 voorkomen, een priemfactor van n2 niet in n1 en n3, en een priemfactor van n3 niet in n1 en n2. In andere woorden, de getallen n1, n2 en n3 moeten onderling ondeelbaar zijn.

Stap 3. Bereken B = √(3 × N) + 1. Je mag B naar boven afronden op een geheel getal.

Stap 4. Maak een lange lijst van getallen die eruit zien als b1 × n1 + b2 × n2 + b3 × n3. Voor de getallen b1, b2 en b3 vul je hier getallen van 1 tot en met B in. Dus je krijgt bijvoorbeeld 1 × n1 + 1 × n2 + 1 × n3 en 5 × n1 + 3 × n2 + 12 × n4 en ook 1 × n1 + B × n2 + B × n3. Als je alle mogelijkheden gebruikt, bevat je lijst B × B × B getallen. Dit is al gauw heel veel, dus het is handig om hiervoor een computer te gebruiken.

Stap 5. Zoek in je lijst twee dezelfde getallen, die toch op een andere manier gemaakt zijn:

b1 × n1 + b2 × n2 + b3 × n3 = c1 × n1 + c2 × n2 + c3 × n3.

Bereken nu a1 = b1 - c1, a2 = b2 - c2, a3 = b3 - c3.

Stap 6. Berekenen de getallen a1 × n1, a2 × n2 en a3 × n3. Als er hiervan twee getallen negatief zijn, neem dan de absolute waarde daarvan als a en b en het derde getal als c. Als er maar één getal negatief is, neem de absolute waarde daarvan dan als c en de andere twee getallen als a en b. Als je het goed gedaan hebt, geldt nu a + b = c.

Stap 7. Ontbind a, b en c in priemfactoren en kijk of je een abc-drietal gevonden hebt. Let ook op dat a, b en c geen gemeenschappelijke priemfactoren hebben.

Nu gaan we deze methode toepassen om een abc-drietal te vinden.

Stap 1. We nemen N = 10.

Stap 2. We kiezen n1 = 5, n2 = 8 en n3 = 9. Je ziet dat de priemfactor 3 in n3 twee keer voorkomt en de priemfactor 2 in n2 zelfs drie keer.

Stap 3. De wortel van 3 × 10 is iets groter dan 5, dus B wordt gelijk aan 7.

Stap 4. We krijgen een lijst van 343 getallen. Hieronder zie je een uitsnede. Je kunt ook hier klikken om de hele lijst te bekijken.


Twee stukjes uit de lijst. Beide stukjes bevatten 77.

Stap 5. Er staan veel dezelfde getallen in de lijst. We kiezen hieruit 77:

3 × 5 + 1 × 8 + 6 × 9 = 77,

2 × 5 + 5 × 8 + 3 × 9 = 77.

We krijgen hiermee a1 = 3 - 2 = 1, a2 = 1 - 5 = -4 en a3 = 6 - 3 = 3.

Stap 6. We berekenen a1 × n1 = 1 × 5 = 5, a2 × n2 = -4 × 8 = -32 en a3 × n3 = 3 × 9 = 27. Hier is één negatief getal bij, namelijk -32, dus we nemen c = 32. Nu wordt a = 5 en b = 27. Er geldt inderdaad 5 + 27 = 32.

Stap 7. De priemontbinding van de drie getallen is a = 5, b = 3 × 3 × 3 en c = 2 × 2 × 2 × 2 × 2. Het radicaal van dit drietal is dus gelijk aan r = 5 × 3 × 2 = 30. Dit is net iets kleiner dan c = 32, dus we hebben een abc-drietal gevonden!

Hoe zit deze methode eigenlijk in elkaar? Waarom is dit een goede methode om abc-drietallen te vinden?

Het geheim van deze methode is dat je vooraf al een deel van je getallen a, b en c vastlegt. Uiteindelijk worden a, b en c veelvouden van n1, n2 en n3. Die getallen kies je zo dat er weinig verschillende en vooral kleine priemfactoren in voorkomen. Je krijgt in a, b en c nog wel wat extra priemfactoren van de getallen a1, a2 en a3. Maar die kunnen nooit echt groot worden, want deze getallen zijn in elk geval niet groter dan B. Als N groot is, is B ongeveer √(3 × N) en dat is veel kleiner dan N.

Je moet wel nog een beetje geluk hebben. Als je pech hebt, zijn a1, a2 en a3 ongeveer even groot als B en bestaan ze uit allemaal verschillende priemfactoren. Dan wordt het radicaal ongeveer B × B × B = B × 3 × N, terwijl c ongeveer B × N is. Het radicaal is dan dus groter dan c, zodat het gevonden drietal geen abc-drietal is.

Een oplossing hiervoor zou kunnen zijn om B te verkleinen. Als B kleiner is, dan zijn a1, a2 en a3 ook kleiner en is het radicaal vaker kleiner dan c. Helaas hebben we de waarde van √(3 × N) voor B nodig om te garanderen dat de lijst met getallen bij stap 4 wel twee dezelfde getallen bevat. Deze lijst bestaat namelijk uit B × B × B > 3 × B × N getallen, die allemaal kleiner zijn dan B × N + B × N + B × N = 3 × B × N. Je kunt niet meer dan 3 × B × N verschillende getallen hebben die allemaal kleiner zijn dan 3 × B × N, dus moeten er wel twee dezelfde in de lijst staan.

Als we nu B zouden verkleinen, dan zou de lijst met getallen korter worden. Maar als deze lijst minder dan 3 × B × N getallen bevat, dan zouden het allemaal verschillende getallen kunnen zijn. In dat geval kunnen we de methode niet verder uitvoeren en vinden we in elk geval geen abc-drietal.

Auteur: Birgit van Dalen