Op 9 oktober 1817 werd de Universiteit Gent boven het doopvont gehouden in het Gentse stadhuis. Daarom stond het jaar 2017 volledig in het teken van de 200e verjaardag van de UGent1. Ter gelegenheid van deze festiviteiten hebben we speciaal voor de Universiteit Gent een priemgetal ontworpen.

het priemgetal van de UGent
Het priemgetal van de UGent (9000 cijfers).

Het priemgetal bestaat enkel uit de cijfers 1 en 8 — 9000 in totaal, verwijzend naar de postcode van de stad Gent — maar als je goed kijkt dan zie je dat het cijfer 2 ook één keer in het priemgetal voorkomt (aangeduid in het geel in bovenstaande figuur).

Invoer

De invoer omschrijft een rechthoekige afbeelding die bestaat uit minstens drie rijen en minstens drie kolommen. De afbeelding wordt opgebouwd met drie verschillende karakters: twee van deze karakters komen elk minstens twee keer voor in de afbeelding en het andere karakter komt juist één keer voor in de afbeelding.

De eerste regel van de invoer bevat de twee karakters die minstens twee keer voorkomen in de afbeelding. Daarna volgen de regels die de rijen van de afbeelding voorstellen. Elke rij bestaat uit een vast aantal karakters (evenveel als het aantal kolommen van de afbeelding).

Uitvoer

Een regel met de tekst

karakter 's' komt enkel voor op rij r en kolom k

waarbij het karakter dat juist één keer voorkomt in de afbeelding moet ingevuld worden op de plaats waar s staat. Het nummer van de rij (resp. kolom) waarop dit karakter terug te vinden is in de afbeelding moet ingevuld worden op de plaats waar r (resp. k) staat. Hierbij nummeren we de rijen van de afbeelding van boven naar onder, en de kolommen van links naar rechts, telkens vanaf 1.

Voorbeeld

In onderstaande voorbeeldinvoer werd het karakter dat juist één keer voorkomt in het geel aangeduid.

Invoer:

.8
...........................................
...........................................
....................88.....................
.................88888888..................
...............888888888888................
............888888......888888.............
.........888888............888888..........
......888888..................888888.......
....888888......................888888.....
....888............................888.....
...........................................
......888888888888888888888888888888.......
........88888888888888888888888888.........
...........................................
...........................................
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..82..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
...........................................
...........................................
......888888888888888888888888888888.......
......888888888888888888888888888888.......
...........................................
....8888888888888888888888888888888888.....
....8888888888888888888888888888888888.....
...........................................
...........................................

Uitvoer:

karakter '2' komt enkel voor op rij 21 en kolom 30

Epiloog

Het ontwerp van het priemgetal van de Universiteit Gent is geïnspireerd op deze video die gemaakt werd door Numberphile2.

De video toont een verrassende afbeelding die te vinden is in een klein kadertje dat aan de muur hangt in de Senior Combination Room in Trininty College3, een college dat behoort bij de Universiteit van Cambridge. De jonge onderzoeker James McKee bedacht een priemgetal van 1350 cijfers dat een sterke gelijkenis vertoont met het wapenschild van de Universiteit van Cambridge. Ook het aantal cijfers is niet toevallig gekozen, want het verwijst naar het jaar waarin bisschop William Bateman4 de universiteit gesticht heeft.

het priemgetal van Trinity Hall
Het priemgetal van Trinity Hall (1350 cijfers) vormt het wapenschild van de Universiteit van Cambridge.

Nu blijkt het vinden van een priemgetal dat een bepaalde afbeelding weergeeft, eenvoudiger te zijn dan je op het eerste gezicht misschien zou denken. In de beschrijving onder de video legt McKee uit hoe hij tot het ontwerp van het priemgetal gekomen is:

De meeste cijfers van het priemgetal $$p$$ werden vastgelegd zodat i) tweede derde van de cijfers bovenaan het gewenste patroon vormen en ii) één derde van de cijfers onderaan ervoor zorgen dat $$p - 1$$ een mooi grote (samengestelde) priemfactor $$F$$ heeft, waarbij de ontbinding in priemgetallen van $$F$$ gekend is. Voor getallen van deze vorm bestaat een eenvoudige en snelle manier om te controleren of het priemgetallen zijn. Tenslotte werd een klein aantal cijfers (je kan makkelijk zien welke) gebruikt om systematisch op te tellen vanaf 1, totdat een getal $$p$$ gevonden werd dat een priemgetal is.

Het inspireerde ook wiskundestudent Jack Hodkinson van de Universiteit van Cambridge om een priemgetal te ontwerpen met de afbeelding5 van Corpus Christi College6, waarin hij zijn eigen initialen en geboortedatum wist te verwerken.

het priemgetal van Corpus Christi College
Het priemgetal van Corpus Christi College (2688 cijfers) toont de beeltenis van het college, en bevat de initialen (linksboven) en de geboortedatum (rechtsonder) van ontwerper Jack Hodkinson.

Om het priemgetal van de Universiteit Gent te ontwerpen, zijn we vertrokken van het logo dat gebruikt werd voor de 200e verjaardag van de UGent.

200 jaar UGent
Logo dat gebruikt werd bij de 200e verjaardag van de Universiteit Gent (2017).

Dit logo hebben we omgezet naar een ASCII afbeelding bestaande uit 9000 cijfers (als verwijzing naar de postcode van de stad Gent7), verdeeld over 75 rijen van elk 120 enen en achten. Voor de weergave van het priemgetal kozen we het lettertype Bimini, omdat het een mooi contrast gaf tussen "zware" achten (die de blauwe pixels voorstellen) en "lichte" enen (die de witte pixels voorstellen). Gelukkig was de pixel rechtsonder wit, omdat het priemgetal dat we voor ogen hadden onmogelijk even kon zijn.

Daarna schreven we een Python programma dat dit initiële getal — dat nog geen priemgetal was, maar wel het gewenste patroon weergaf — moest omvormen tot een priemgetal. Hiervoor overliep het programma systematisch alle cijfers 8 in het initiële getal, verving die telkens door één van de andere cijfers (niet 1 of 8) en controleerde of het getal dat zo bekomen werd een priemgetal was. Om snel te controleren of een getal van 9000 cijfers een priemgetal is, maakten we gebruik van de Miller-Rabin-priemgetaltest8. Dit algoritme heeft het altijd bij het rechte eind als het zegt dat een getal geen priemgetal is, maar het kan enkel met (zeer) grote zekerheid stellen dat een getal wel een priemgetal is. Om finaal te controleren dat een kandidaat-priemgetal wel degelijk priem was, hebben we gebruik gemaakt van de fantastische app van Dario Alpern9 om onszelf absolute zekerheid te geven.

Hoe wisten we nu zo zeker dat dit zou werken? Wel, de priemgetalstelling10 zegt ons dat er ongeveer $$\frac{n}{\log{n}}$$ priemgetallen zijn die kleiner zijn dan $$n$$. Er zijn met andere woorden ongeveer \[ \frac{10^{9000}}{\log{10^{9000}}} - \frac{10^{8999}}{\log{10^{8999}}} \approx   4.34 \times 10^{8995} \] priemgetallen met 9000 cijfers. Dat betekent dat bij benadering één op de 21.000 getallen met 9000 cijfers een priemgetal zou moeten zijn. Deze schatting hebben we uiteraard niet met de hand op de achterkant van een bierkaartje berekend, want ook hier schoot Python ons ter hulp (de module Decimal zorgt ervoor dat we met grote floating point getallen kunnen rekenen zonder afrondingsfouten).

>>> from decimal import Decimal
>>> n = Decimal(10 ** 9000)
>>> m = Decimal(10 ** 8999)
>>> schatting = lambda x : x / x.ln()
>>> aantal_priemgetallen_met_9000_cijfers = schatting(n) - schatting(m)
>>> aantal_priemgetallen_met_9000_cijfers
Decimal('4.342891196471751863968210190E+8995')
>>> aantal_getallen_met_9000_cijfers = 9 * m
>>> aantal_getallen_met_9000_cijfers / aantal_priemgetallen_met_9000_cijfers
Decimal('20723.52171132395093158056936')

De even getallen mochten we bij voorbaat al buiten beschouwing laten, dus dat reduceert onze zoekruimte al met de helft. Ook de cijfers 0, 3, 6 en 9 hoefden we niet te controleren als vervanging van één van de achten, omdat deze in combinatie met 7660 enen en 1339 achten altijd een drievoud opleveren. Enkel de cijfers 2, 4, 5 en 7 bleven dus nog over als mogelijke vervanging voor één van de achten.

Het zoeken naar ons priemgetal zou dus zeker niet zo tijdrovend zijn als het zoeken van de spreekwoordelijke speld in een hooiberg. Maar als je je bedenkt dat het ons een paar minuten kost om te achterhalen of een getal van 9000 cijfers een priemgetal is, was de voorspelling dat we toch een dikke maand zoet zouden zijn vooraleer we ons priemgetal zouden vinden. Gelukkig was er ook nog de supercomputer van de UGent11 (met dank aan de samenwerking met het Vlaams Supercomputer Centrum12), waardoor we heel wat getallen tegelijkertijd konden controleren. Uiteindelijk leverde het 2942e getal dat we controleerden al een priemgetal op, waardoor onze rudimentaire voorspelling van hierboven zelfs een overschatting bleek te zijn.