Wiskundemeisjes

Deze column staat vandaag in de Volkskrant.

“Mooie zeden in Ede, zei oom.” Als kind bladerde ik uren in mijn moeders exemplaar van Battus’ Opperlandse taal&letterkunde. Hele stukken leerde ik uit mijn hoofd, waaronder die klassieke omkeerzin. Prachtig vond ik palindromen als levensnevel, moorddroom of nepmarsrampen.

Spelen met letters vind ik nog steeds leuk, maar minstens zo graag speel ik met cijfers. Ook daar heb je mooie palindromen. Een fijn voorbeeld is het priemgetal 11933316181512171330203317121518161333911 (dit getal is alleen te delen door één en zichzelf). Als je van dit getal steeds de eerste en laatste twee cijfers weghaalt, dan krijg je een rijtje met allemaal palindroompriemen. Het eindigt met 2, het enige even priemgetal. Ook aardig is 1030301, de derde macht van 101 (dat zelf een omkeerpriem is).

We weten nog een heleboel niet over symmys in de getallen. Bestaan er bijvoorbeeld oneindig veel palindroompriemen? Hoe groter de getallen, hoe schaarser de palindromen. Tussen de 100 en 999 is één op de tien getallen een palindroom, want bij elke twee begincijfers geeft één van de tien mogelijke eindcijfers een palindroom. Tussen 100.000 en 999.999 is de score nog maar één op de duizend. Bij elke twee cijfers die erbij komen, neemt het percentage palindromen met een factor tien af. Ook priemgetallen zijn steeds zeldzamer in de hogere regionen. Niemand weet of er desondanks toch oneindig veel palindroompriemen zijn.

Nog veel intrigerender is het 196-probleem. Je kunt palindromen soms maken uit gewone getallen. Neem een getal, keer het om en tel het op bij wat je had. Herhaal dit tot je een palindroom krijgt. Als je begint met 32, dan krijg je 32+23 =55 en ben je in één stap klaar. Begin je met 39, dan ga je via 39+93 = 132 naar 132+231 = 363. Als je met een getal onder de honderd begint, dan eindig je altijd bij een palindroom. Al kan het best even duren, vanaf 89 moet je maar liefst 24 stappen maken voordat je eindelijk bij 8813200023188 komt.

Kom je uiteindelijk altijd uit bij een palindroom? Wiskundigen vermoeden dat er getallen zijn waarbij het niet lukt. Het kleinste voorbeeld is 196 (vandaar dat dit het 196-probleem heet). Meer dan een biljoen stappen zijn er al doorgerekend en er verschijnt maar geen palindroom. Het is moeilijk om te bewijzen is dat er nóóit een palindroom komt, want het zou altijd kunnen dat bij een volgende stap ineens een mooie symmetrie tevoorschijn komt. De kans daarop is natuurlijk wel steeds kleiner, omdat in de grote getallen minder en minder palindromen voorkomen. Er zijn meer getallen zoals 196 waarvan we niet weten of ze op een palindroom uitkomen. De slimmeriken hebben vast al geraden dat 691 ook een probleemgeval is. Onder de duizend zijn er in totaal dertien van zulke getallen. En daarboven nog veel meer.

Levert een oplossing van dit 196-probleem ook maar iets op? Krijgen we er snellere computers door? Veiligere auto’s? Nog meer welvaart? Waarschijnlijk niet. Maar wie net als ik van Opperlans houdt, begrijpt dat het daar helemaal niet om gaat bij dit soort problemen.

Deze column verscheen vandaag in de Volkskrant. Aan het eind van de Boekenweek leek het me mooi om net als de 75 auteurs in de prachtige bundel “Titaantjes waren we” een brief aan mijn jonge ik te schijven.

Lief pubermeisje Ionica,

Laat ik maar met de deur in huis vallen: het is tijd dat je ontdekt wat je écht leuk vindt. Op school vind je het vooral fijn om goede cijfers te halen. Je vindt daarom alle vakken wel leuk, behalve dan gymnastiek en tekenen (waarvoor je nooit meer dan een zes haalt en die voldoende krijg je vooral omdat de leraren vinden dat je zo aandoenlijk je best doet). Maar er is niets waarover je echt enthousiast bent, niets waarover je ‘s avonds na het eten wilt nadenken, niets om je tanden eens in te zetten.

Dit is een nog jongere Ionica. Als puber keek ik natuurlijk altijd chagerijnig vanachter mijn puistjes, dus daar ga ik hier geen foto van plaatsen.

Ik weet vrij zeker dat er iets is dat je geweldig vindt: wiskunde. Je denkt nu dat wiskunde gaat over het berekenen van driehoekszijdes, het tekenen van grafiekjes en het oplossen van vergelijkingen. Maar wiskunde is veel meer dan die sommen die je nu krijgt. Wiskunde gaat nauwelijks over rekenen, het gaat om grote ideeën en over helder nadenken. Het allermooiste van wiskunde zijn de waterdichte bewijzen.

Heb je bijvoorbeeld al eens gehoord van priemgetallen? Dat zijn getallen die alleen deelbaar zijn door één en zichzelf. Zeventien is een voorbeeld, en 1999 (probeer als je me niet gelooft maar eens een deler van 1999 te vinden op je rekenmachine). Meer dan tweeduizend jaar geleden bewees de Griekse wiskundige Euclides dat er oneindig veel priemgetallen zijn. Zijn bewijs is na al die jaren nog steeds mooi en helder.

Neem eens aan dat er eindig veel priemgetallen zijn. Die kun je dan in een lijstje zetten en nummeren: het eerste noem je , het volgende en zo ga je door tot het laatste priemgetal op de lijst dat je noemt. Maak nu een nieuw getal x door al deze priemgetallen met elkaar te vermenigvuldigen en er één bij op te tellen. Dus . Vanzelfsprekend is groter dan één en dat betekent dat door minstens één priemgetal te delen is. Die deler zou op onze lijst met alle priemgetallen moeten staan.

Maar als je x deelt door dan houd je een rest van één over. Hetzelfde geldt voor en elk ander priemgetal op onze lijst priemgetallen. Dus is door geen van de priemgetallen op die lijst te delen. Dat kan twee dingen betekenen: óf is zelf een priemgetal, óf is te delen door een of ander priemgetal dat niet op de lijst staat. In beide gevallen ontbreekt er een priemgetal op onze lijst: terwijl we aannamen dat alle priemgetallen daarop stonden. Kortom: er zijn oneindig veel priemgetallen, want je kunt voor elke eindige lijst priemgetallen een priemgetal vinden dat er niét opstaat. Klaar! Als je dit bewijs inderdaad mooi vindt (en dat is zo, toch?), koop dan eens een boek over getaltheorie. Er zal een wereld voor je opengaan.

Tenslotte nog een klein advies: als je straks voor het eerst naar de disco gaat, doe dan niet je favoriete roze Snoopy-trui aan. Geloof me.

Liefs,

Ionica

Naar aanleiding van deze xkcd:

heeft iemand zich uitgeleefd en een factoriseerklok gemaakt, op deze website! Per seconde kun je zien wat de priemfactoren van de tijd zijn, bijvoorbeeld:

2 • 3 • 5 • 7 • 17 • 59 om 21:06:30.

Voor als je zelf wel iets te doen hebt.

Bekijk vooral ook eens het lijstje met priemtijden, en de priemtweelingtijden.

(Joris, bedankt voor de tip!)

Deze column verscheen in de Volkskrant van 6 juni 2009.

Heeft u ook pas het boek "De eenzaamheid van de priemgetallen" van de Italiaanse debutant Paolo Giordano gelezen? Een boek met zo'n titel kon ik natuurlijk niet laten liggen. En hoewel ik het zeker goed geschreven vond, had ik na een tijdje wel genoeg van de problematische karakters. Nu wat aandacht voor de priemgetallen zelf dus, want die zijn ook heel interessant.

Een priemgetal is een getal dat geen andere delers heeft dan 1 en zichzelf. Per afspraak is het getal 1 geen priemgetal. De eerste priemgetallen zijn dus 2, 3, 5, 7, 11, 13, 17, 19. En zijn die priemgetallen echt zo eenzaam? Er bestaan oneindig veel priemgetallen, dus in die zin niet. Maar ze staan haast nooit naast elkaar in de rij van gehele getallen: 2 en 3 staan naast elkaar en zijn allebei priem, maar daarna schelen priemgetallen altijd minstens twee (want als twee getallen maar één schelen, is altijd één van de twee deelbaar door 2). En naarmate de getallen groter worden, worden de priemgetallen steeds zeldzamer: in de buurt van het getal 10.000 is ongeveer een op de negen getallen priem, en rond de 1.000.000.000 een op de 21.

Ook in de natuur komen priemgetallen voor. Een bekend voorbeeld is de levenscyclus van een bepaald insect, de cicade. Cicaden zijn een beetje rare beestjes: afhankelijk van de soort leven ze eerst dertien of zeventien jaar onder de grond, waar ze leven van sappen uit boomwortels, en daarna komen ze met z'n allen tegelijk naar boven om zich voort te planten. Binnen een maand gaan ze allemaal dood. Maar de larven laten zich weer uit de boomtakken naar beneden vallen, en kruipen dan weer voor dertien of zeventien jaar de grond in, enzovoort.

Wetenschappers vragen zich natuurlijk af: is het toeval dat de lengtes van deze cycli priemgetallen zijn, of zit daar een evolutionair voordeel aan vast? Bewijzen kun je het moeilijk, maar de hypothese is geopperd dat een priemgetal als cyclus handig is om natuurlijke vijanden te ontlopen. Als je vijand er elk jaar is, maakt het niet uit wanneer je als cicade bovenkomt. Maar mocht een natuurlijke vijand ook periodiek verschijnen, of met een bepaalde periode steeds meer of minder talrijk zijn, dan wil je als cicade liever niet bovenkomen op het moment dat het aantal vijanden ook piekt. Als je als cicade een twaalfjarige cyclus zou hebben, dan zou je vijanden die er eens per 1, 2, 3, 4, 6 of 12 jaar zijn elke keer als je bovenkomt tegen kunnen komen. Als je een dertienjarige cyclus hebt, kun je alleen vijanden met een cyclus van één of dertien jaar elke keer tegenkomen. En een vijand met een cyclus van zes jaar kom je dan maar eens per 6 × 13 = 78 jaar tegen.

Cicaden richten overigens nauwelijks schade aan. Wel zijn ze imposant: op een vierkante kilometer kunnen wel een half miljoen beestjes uit de grond komen! Priemgetallen mogen misschien eenzaam zijn, cicaden zijn dat zeker niet.

Zoals we al schreven leek het erop dat er een nieuw Mersenne-priemgetal gevonden was. Dat blijkt inderdaad zo te zijn, maar dat is nog niet alles: er zijn er zelfs twee gevonden! We kennen nu 46 Mersenne-priemgetallen.

De Franse monnik Marin Mersenne (1588-1648) naar wie deze priemgetallen genoemd zijn.

Een Mersenne-priemgetal is een priemgetal van de vorm 2^p - 1. Mersenne werkte aan deze getallen toen hij een formule probeerde te vinden waarmee alle priemgetallen gegenereerd kunnen worden. Dat lukte niet, en zo'n formule is nog nooit gevonden.

Niet alle getallen van de vorm 2^p -1 zijn priem. Als 2^p -1 een priemgetal is, dan moet p zelf ook een priemgetal zijn: stel namelijk dat p een factor q heeft, dan is 2^p -1 deelbaar door 2^q - 1. Maar zelfs als p priem is, is 2^p - 1 heel vaak geen priemgetal. Voor p= 2, 3, 5 en 7 geldt wél dat 2^p - 1 priem is, maar 2¹¹ - 1 = 2047 = 23 × 89.

Uit het Kennislink-artikel van Alex van den Brandhof:

Voor het eerst in de geschiedenis kennen we priemgetallen van meer dan tien miljoen cijfers. Twee reuzenpriemgetallen werden onlangs gevonden door de Amerikaan Edson Smith en de Duitser Hans Michael Elvenich, of beter gezegd: de computers van deze twee heren. De twee getallen, 2^43.112.609 - 1 en 2^37.156.667 - 1, zijn volledig uitgeschreven 12.978.189 respectievelijk 11.185.272 cijfers lang. De nieuwe priemgetallen werden gevonden in het kader van GIMPS (Great Internet Mersenne Prime Search), een project waarbij duizenden vrijwilligers de ongebruikte rekencapaciteit van hun computer beschikbaar stellen voor via internet gedistribueerde berekeningen. GIMPS bestaat sinds januari 1996 en heeft sindsdien twaalf nieuwe Mersenne-priemgetallen opgeleverd. Het oude priemrecord stamt uit 2006, toen een priemgetal van ruim 9,8 miljoen cijfers werd gevonden.

Er was een prijs van $100.000 uitgeloofd voor het eerst gevonden priemgetal met meer dan 10 miljoen cijfers. Het priemgetal dat twee jaar geleden gevonden werd, was dus net te klein, en nu zijn er binnen een paar weken twee nieuwe gevonden die wel groot genoeg zijn! GIMPS geeft $50.000 van de prijs aan het UCLA Mathematics Department waar Smith de software liet draaien, $25.000 gaat naar een goed doel en van de rest gaat het grootste deel naar de ontdekkers van de vorige zes Mersenne-priemen.

Vandaag in Delta een interview met Richard Gill over het probioticaonderzoek waarbij onverwachts patiënten overleden na toediening van `goede' bacteriën: `Tragisch dat het is misgegaan'. Gill geeft op 17 september om 11 uur een voordracht over dit onderwerp in de Snijderszaal van het EWI-gebouw, Mekelweg 4 te Delft.

En het lijkt er echt op dat er een nieuw Mersennepriemgetal is gevonden (en de kans is groot dat daarvoor 100.000 dollar wordt uitgereikt).

Jeffrey Shallit schrijft op zijn onvolprezen blog Recursivity over een nieuwe formule om priemgetallen te genereren. Koen schreef hier ook al over. Weten jullie allemaal nog wat priemgetallen zijn? Dat zijn de getallen die alleen deelbaar zijn door één en zichzelf: bijvoorbeeld 2, 3, 5, 7 of 5417. Om technische redenen noemen we 1 geen priemgetal.

Priemgetallen worden al heel lang bestudeerd. We weten al meer dan tweeduizend jaar dat er oneindig veel priemgetallen bestaan en de zeef van Eratosthenes om priemgetallen te vinden is ongeveer even oud. Je zou misschien denken dat we alles wel zo'n beetje weten over priemgetallen. Niets is minder waar. Het vermoeden van Goldbach, de Riemann-hypothese en allerlei andere vermoedens over priemgetallen zijn nog steeds onbewezen.

Het is daarom enigszins verrassend als er iets nieuws over priemgetallen wordt ontdekt dat tamelijk eenvoudig is. Zoals deze formule om priemgetallen te genereren. Neem a(1) = 7 en neem voor n ≥ 2

a(n) = a(n-1) + ggd(n,a(n-1)).

Dat ggd is een afkorting voor de grootste gemene deler . Dus we vinden bij de eerste stap a(2) = a(1) + ggd(2,7) = 8. De verschillen tussen twee opeenvolgende termen a(n) - a(n-1) geven priemgetallen (en een heleboel enen).

De reeks a begint zo:

en dit zijn de bijbehorende verschillen a(n) - a(n-1)

Als we de enen overslaan, dan krijgen we de priemgetallen 5, 3, 11, 3 en 23. Als je zo verder gaat, dan vinden we (zonder de dubbelen en de enen) meer priemgetallen

Eric Rowland bewijst in het artikel A Natural Prime-Generating Recurrence dat in deze reeks alleen enen en priemgetallen voorkomen. Dit artikel is deze maand gepubliceerd in Journal of Integer Sequences. In het stuk van Shallit kun je meer lezen over de ontdekking van deze formule.

Er zijn trouwens nog een paar interessante open vragen bij de nieuwe formule. Werkt het bijvoorbeeld ook voor andere beginwaarden dan a(1) = 7? Voor a(1) = 532 (om maar wat te noemen) krijg je bijvoorbeeld vrij snel een 9. Rowland vermoedt echter dat voor elke begingetal er na een eindig aantal stappen alleen nog enen en priemgetallen komen. Nog interessanter is volgens mij de vraag of ook alle oneven priemgetallen voorkomen in zo'n reeks. Rowland vermoedt van wel...

Shallit had ons trouwens zelf gemaild over dit nieuwe resultaat. We zouden het heel leuk vinden als meer wiskundigen ons zouden tippen over ontwikkelingen die interessant zijn om hier te noemen!