Op school hadden Milli en Mu veel lol met het kaartprobleem van vorige keer. De oplossing die ze al programmerend gevonden hadden, bleek wiskundig nog eenvoudiger te begrijpen. Je legt een aantal speelkaarten open op tafel naast elkaar en wilt je hand zodanig neerzetten dat het aantal zwarte kaarten links ervan gelijk is aan het aantal rode kaarten rechts. Als dit je gelukt is, dan kun je alle zwarte kaarten links precies vervangen door alle rode kaarten van rechts. Nu liggen alleen rode kaarten links en alleen zwarte rechts. Blijkbaar moet je je hand zo neerzetten dat het aantal kaarten links ervan gelijk is aan het totale aantal rode kaarten.

Het nieuwe probleem

Het nieuwe probleem dat Milli en Mu hadden opgekregen gaat over het itereren (herhaald toepassen) van een functie, zeg $f$. Je begint met een startgetal, zeg $s$, en maakt nu de rij $s$, $f(s)$, $f(f(s))$, $f(f(f(s)))$, etc. We zullen het $n$ keer toepassen van $f$ op $s$ noteren als $f^{(n)}(s)$. Dan is $f^{(0)}(s) = s$ en $f^{(n+1)}(s) = f(f^{(n)}(s))$. Als $f(s)$ altijd een positief geheel getal is, dan zijn er maar twee dingen mogelijk voor de rij $f^{(i)}(s)$, waarbij $i$ vanaf $0$ oploopt. Óf er komen steeds grotere waarden in de rij voor, óf de rij blijft begrensd en gaat zich herhalen (wordt periodiek). Als de rij begrensd blijft, dat wil zeggen als alle waarden onder een zekere grenswaarde, zeg $G$, blijven, dan moet een waarde, zeg $t$, vaker voorkomen. Vanaf die waarde $t$ herhaalt de rij zich en de periode is kleiner dan $G$. Het probleem is nu als volgt: stel dat je al weet dat de rij $f^{(i)}(s)$ uiteindelijk periodiek wordt. Hoe kun je dan achter de lengte van die periode komen? Anders gezegd, wat is de kleinste $k$ met $f^{(n+k)}(s) = f^{(n)}(s)$ voor alle voldoend grote $n$?

Een bekende functie $f$ om te itereren is de Collatz functie, gedefinieerd door $f^{(n)} = n/2$ als $n$ even is en anders $f^{(n)} = 3n + 1$. Itereren van $f$ vanaf startwaarde $19$ levert de rij $19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, \dots$.

Blijkbaar wordt deze rij periodiek na achttien keer toepassen en komt dan in de cykel $4, 2, 1, 4$ met periode $3$. Men vermoedt dat de Collatz-rij voor elke startwaarde uiteindelijk bij deze cykel uitkomt, maar dit is nog steeds niet bewezen.

Het programma

De vraag vorige keer was om een efficiënt programma te schrijven om de periode te bepalen bij een gegeven functie $f$ en startwaarde $s$.

Mu was meteen aan de slag gegaan met Python en de Collatz functie en kwam tot deze code:

i = 0
while s != 4:
    s, i = f(s), i + 1

Variabele $i$ telt het aantal stappen tot de cykel wordt bereikt. Milli vond dit echter niet goed genoeg. Het is natuurlijk eenvoudig om te detecteren wanneer $4$ bereikt wordt. Maar er zou ook een andere cykel kunnen zijn, wat het geval is als je in de definitie van de Collatz functie $3n + 1$ vervangt door $3n - 1$ of $5n + 1$. En dan weet je niet tot welke waarde je moet itereren. Het is bovendien ook niet zo dat de startwaarde zelf het begin van de cykel is. Het kan een tijdje duren voordat de rij in een cykel terechtkomt. Milli schreef daarom een programma dat alle voorgaande waarden onthoudt om de cykel te detecteren:

rij = [] # lijst met voorgaande waarden
while s not in rij:
    rij.append(s)
    s = f(s)

Als je eenmaal weet met welke waarde de cykel begint, dan is de periode eenvoudig te bepalen met een programma dat lijkt op dat van Mu:

t, k = s, 1 # doelwaarde t en periode k
while f(s) != t:
    s, k = f(s), k + 1

Phi vond dit best al een mooi programma worden, dat qua aantal rekenstappen niet echt beter kan. "Maar", merkte Phi op, "het geheugengebruik kan hard oplopen als het lang duurt voordat de cykel bereikt wordt en één keer is doorlopen." Daaraan voegde Pi raadselachtig toe dat er een slimme manier is om de cykel te detecteren zonder het hele voorgaande deel van de rij te onthouden. Milli en Mu konden zich dat niet voorstellen, want zoiets leek te mooi om waar te zijn.

"Kijk", begon Pi, "we zoeken de kleinste $i$, $k$, met $f^{(i)}(s) = f^{(i+k)}(s)$." Als de cykel al bij $s$ begint, dan kan $i = 0$ blijven en hoeven we alleen $k$ vanaf $1$ te verhogen. Wat als we nu $i$ én $k$ telkens met $1$ verhogen? We houden dus twee variabelen bij: $v = f^{(i)}(s)$ en $w = f^{(i+k)}(s)$. We krijgen dan het programma:

i, k, v, w = 0, 1, s, f(s)
while v != w:
    i, k, v, w = i + 1, k + 1, f(v), f(f(w))

Na afloop van de $while$-lus weten we dus $f^{(i)}(s) = v = w = f^{(i+k)}(s)$. Maar mogelijk zijn $i$ en $k$ niet de kleinste waarden met deze eigenschap. Voor het bepalen van de periode (de lengte van de cykel) hoeven we niet de kleinste $i$ te vinden. Let wel dat de gevonden $k$ een veelvoud kan zijn van de periode. De periode zelf is dan te vinden met het vorige programma. Het aantal rekenstappen is iets meer dan wanneer de voorgaande waarden worden onthouden, want nu wordt $f$ drie keer toegepast in elke slag van de $while$- lus. Qua geheugengebruik is het wel een vooruitgang.

Eigenlijk zijn alleen de twee variabelen $v$ en $w$ nodig om de cykel te detecteren. Hier is het hele programma:

v, w = s, f(s)
while v != w:
    v, w = f(v), f(f(w))

k = 1 # periode
while f(v) != w:
    v, k = f(v), k + 1

Milli en Mu waren duidelijk verrast dat het zo eenvoudig kon.

		Probleem voor volgende keer Gegeven is een tabel met getallen. Elke rij is oplopend gesorteerd en elke kolom ook. Gevraagd is om het aantal voorkomens van een gegeven waarde, zeg $X$, in de tabel te tellen, bijvoorbeeld $X = 5$. In Python wordt een tabel opgeslagen als een lijst van lijsten. Hieronder een voorbeeldtabel: [[1, 1, 1, 2, 2, 2, 2, 2, 3], [1, 2, 2, 2, 3, 3, 3, 4, 4], [1, 2, 3, 3, 3, 4, 4, 4, 5], [2, 2, 3, 4, 4, 4, 5, 5, 6], [2, 3, 3, 4, 5, 5, 5, 6, 6], [2, 3, 4, 4, 5, 6, 6, 6, 7], [2, 3, 4, 5, 5, 6, 7, 7, 7], [2, 4, 4, 5, 6, 6, 7, 8, 8], [3, 4, 5, 6, 6, 7, 7, 8, 9]]

 

	Verder lezen
Benne de Weger, "Het 3n + 1-vermoeden", Nieuw Archief voor Wiskunde, 5/15 nr. 1. maart 2014, https://www.nieuwarchief.nl/serie5/pdf/naw5-2014-15-1-040.pdf. John Simons, "Het 3x + 1-probleem, recente ontwikkelingen en oplossingsrichtingen", Nieuw Archief voor Wiskunde, 5/23 nr. 3. sept. 2022, https://www.nieuwarchief.nl/serie5/pdf/naw5-2022-23-3-147.pdf.