Een breuk is de onuitgewerkte deling van een getal $$t \in \mathbb{N}$$ (de teller) door een ander getal $$n \in \mathbb{N}_0$$ (de noemer). De gebruikelijke voorstelling van een breuk is $$\frac{t}{n}$$ waarbij de teller boven een streep geplaatst wordt, en de noemer onder de streep (bijvoorbeeld $$\frac{1}{2}$$ of $$\frac{17}{3}$$).
Elke breuk heeft een eenvoudigste vorm waarin de teller en de noemer zo klein mogelijk zijn. Zo is de eenvoudigste vorm van $$\frac{13}{39}$$ gelijk aan $$\frac{1}{3}$$. Die breuk is niet weer te geven met kleinere getallen dan 1 en 3. Het "zo klein mogelijk maken" noemt men vereenvoudigen. Dit kan door de teller en de noemer te delen door hun grootste gemene deler1: het grootste getal dat zowel een deler is van de teller als van de noemer. Daardoor hebben de teller en noemer na vereenvoudiging een grootste gemene deler die gelijk is aan 1.
Een breuk waarvan de noemer in de eenvoudigste vorm gelijk is aan 1, is een natuurlijk getal met als waarde de teller uit de eenvoudigste vorm van de breuk.
Het kwadraat $$x^2$$ van een getal $$x \in \mathbb{R}$$ is het product van $$x$$ met zichzelf ($$x \times x$$). We definiëren het benaderend kwadraat van een getal $$x \in \mathbb{R}$$ als $$x \times \left\lceil{x}\right\rceil$$. Hierbij is $$\left\lceil{x}\right\rceil$$ het kleinste geheel getal dat groter of gelijk is aan $$x$$.
Beschouw nu een breuk $$x = \frac{t}{n}$$ waarbij $$1 \leq n < t$$, en laat ons herhaaldelijk het benaderend kwadraat berekenen. Als voorbeeld nemen we de breuk $$\frac{8}{7}$$. In de eerste stap is $$\left\lceil{\frac{8}{7}}\right\rceil = 2$$ en is $$\frac{8}{7} \times 2 = \frac{16}{7}$$ (we vermenigvuldigen gewoon de teller met het geheel getal). In de tweede stap is $$\left\lceil{\frac{16}{7}}\right\rceil = 3$$, waardoor we krijgen dat $$\frac{16}{7} \times 3 = \frac{48}{7}$$. In de derde stap is $$\left\lceil{\frac{48}{7}}\right\rceil = 7$$ en dus hebben we dat $$\frac{48}{7} \times 7 = \frac{48}{1} = 48$$. Als de noemer 1 wordt en we een natuurlijk getal 48 verkrijgen, stopt de procedure en zeggen we dat de breuk $$\frac{8}{7}$$ haar bestemming 48 (het natuurlijk getal) bereikt heeft in 3 stappen.
Onderzoek toont aan dat het gedrag van deze procedure op zijn zachtst gezegd grillig is. Sommige breuken, zoals $$\frac{8}{7}$$ bereiken hun bestemming na slechts een paar stappen. Soms duurt het heel wat langer: de breuk $$\frac{6}{5}$$ heeft een bestemming met 57735 cijfers die bereikt wordt na 18 stappen. Soms wordt het zelfs ronduit belachelijk: de breuk $$\frac{200}{199}$$ heeft een bestemming met maar liefst $$10^{435}$$ cijfers. Het vermoeden is dat het herhaald toepassen van een benaderend kwadraat altijd eindigt met een natuurlijk getal, maar dat kon nog niet bewezen worden.
We beschouwen breuken $$\frac{t}{n}$$ waarvoor geldt dat de teller $$t \in \mathbb{N}$$ en de noemer $$n \in \mathbb{N}_0$$. Gevraagd wordt:
Schrijf een functie vereenvoudig waaraan de teller $$t$$ (int) en de noemer $$n$$ (int) van een breuk moeten doorgegeven worden. De functie moet de teller (int) en de noemer (int) teruggeven van de eenvoudigste vorm voor de breuk $$\frac{t}{n}$$.
De grootste gemene deler van twee getallen kan berekend worden met de functie gcd2 uit de math module van The Python Standard Library3.
Schrijf een functie benaderend_kwadraat waaraan de teller $$t$$ (int) en de noemer $$n$$ (int) van een breuk moeten doorgegeven worden. De functie moet de teller (int) en de noemer (int) teruggeven van de eenvoudigste vorm voor het benaderend kwadraat van de breuk $$\frac{t}{n}$$.
Schrijf een functie bestemming waaraan de teller $$t$$ (int) en de noemer $$n$$ (int) van een breuk moeten doorgegeven worden, waarbij geldt dat $$1 \leq n < t$$. De functie moet de bestemming (int) van de breuk $$\frac{t}{n}$$ teruggeven.
Schrijf een functie stappen waaraan de teller $$t$$ (int) en de noemer $$n$$ (int) van een breuk moeten doorgegeven worden, waarbij geldt dat $$1 \leq n < t$$. De functie moet het aantal stappen (int) teruggeven waarna de breuk $$\frac{t}{n}$$ haar bestemming bereikt.
>>> vereenvoudig(2, 4)
(1, 2)
>>> benaderend_kwadraat(8, 7)
(16, 7)
>>> benaderend_kwadraat(16, 7)
(48, 7)
>>> benaderend_kwadraat(48, 7)
(48, 1)
>>> bestemming(8, 7)
48
>>> bestemming(10, 6)
1484710602474311520
>>> bestemming(17, 13)
59832260230817687634146563200
>>> stappen(8, 7)
3
>>> stappen(10, 6)
6
>>> stappen(17, 13)
7