] >
Rijen die optreden als het verloop van een element onder een transformatie hebben een speciale gedaante: zijn twee termen in zo’n rij aan elkaar gelijk, dan repeteert de rij.
4.19 Definitie. Een rij in een verzameling heet repetent als er een en een zijn zodat voor alle . We zeggen ook dat de rij repeteert vanaf de -de term. De eindige rij noemen we een periode van lengte van de rij. De eindige rij noemen we de aanloop tot de periode . De rij heet zuiver repetent als bovendien .
Repeteert de rij vanaf de -de term met een periode van lengte , dan noteren we deze rij wel als
De rij getallen heeft een periode van lengte met aanloop :
Of een periode van lengte met aanloop :
Of een periode van lengte met aanloop :
Er zijn dus oneindig veel mogelijkheden. Er zijn, in de notatie van de definitie, wel kleinste getallen en . Hier zijn die respectievelijk en .
4.20 Propositie. Laat een transformatie zijn van een verzameling en zij de rij het verloop van het element . Dan, hetzij is injectief, d.w.z. dat alle termen verschillend zijn, hetzij de rij repeteert.
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
4.21 Gevolg. Laat een transformatie zijn van een eindige verzameling . Dan repeteert het verloop onder van ieder element van .
Bewijs. Het verloop is niet injectief. □
Als het verloop repeteert, dan kun je bij het berekenen van het verloop stoppen op het moment dat er herhaling optreedt. De functie repcourse(f,a) geeft voor een repeterend verloop de kleinste aanloop en de kleinste periode.
4.22 Het -vermoeden. Hier is een eenvoudige transformatie van waarbij de aard van het verloop van elementen een open probleem is:
Het verloop van : .
Het verloop van : .
Het verloop van : .
Het verloop van : .
Het vermoeden is dat van ieder getal het verloop repeteert met periode .
Voor getallen tot
is het met de computer geverifieerd, maar er blijven er dus nog oneindig veel over
waarvoor we het niet weten. Het vermoeden staat ook bekend als het Collatzvermoeden,
het Ulamvermoeden, het Syracusevermoeden. Collatz formuleerde het waarschijnlijk als
eerste, in 1937.
De functie collatz(n) is de transformatie uit bovenstaand voorbeeld. Omwille van de snelheid van het algoritme gebruiken we hier de natuurlijke getallen zoals ze in python voorkomen: het datatype integer met de bijbehorende functies.