A fraction is the non-evaluated division of a number $$n \in \mathbb{N}$$ (the numerator) by another number $$d \in \mathbb{N}_0$$ (the denominator). The usual representation of a fraction is $$\frac{n}{d}$$ with the numerator displayed above a line and a non-zero denominator displayed below that line (examples: $$\frac{1}{2}$$ of $$\frac{17}{3}$$).
A fraction is reduced to its lowest terms if the numerator and denominator are as small as possible. For example, the fraction $$\frac{13}{39}$$ reduced to its lowest terms is $$\frac{1}{3}$$. Making a fraction "as small as possible" is called reducing. This is done by dividing the numerator and denominator by their greatest common divisor1: the largest integer that divides both the numerator and the denominator. Reduction of a fraction therefore yields a numerator and a denominator with a greatest common divisor equal to 1.
A fraction whose reduced form has a denominator equal to 1, is an integer number whose value is the numerator of the reduced form of the fraction.
The square $$x^2$$ of a number $$x \in \mathbb{R}$$ is the product of $$x$$ with itself ($$x \times x$$). We define the almost square of a number $$x \in \mathbb{R}$$ as $$x \times \left\lceil{x}\right\rceil$$, with $$\left\lceil{x}\right\rceil$$ the smallest integer greater than or equal to $$x$$.
Now consider a fraction $$x = \frac{n}{d}$$ where $$1 \leq d < n$$, and let us compute the almost square repeatedly. Let's take the fraction $$\frac{8}{7}$$ as an example. In the first step, $$\left\lceil{\frac{8}{7}}\right\rceil = 2$$ and $$\frac{8}{7} \times 2 = \frac{16}{7}$$ (simply multiply the numerator by the integer). In the second step we have $$\left\lceil{\frac{16}{7}}\right\rceil = 3$$, so we have $$\frac{16}{7} \times 3 = \frac{48}{7}$$. In the third step we have $$\left\lceil{\frac{48}{7}}\right\rceil = 7$$, and so we have $$\frac{48}{7} \times 7 = \frac{48}{1} = 48$$. Now the denominator (of the reduced form) is 1 and the result is the integer 48, the iteration stops, and we say that the fraction $$\frac{8}{7}$$ has reached its destination 48 (the integer) in 3 steps.
Research shows that the behavior of this procedure is chaotic, to say the least. Some fractions, such as $$\frac{8}{7}$$ reach their destination after just a few steps. Sometimes it takes a lot longer: the fraction $$\frac{6}{5}$$ has a destination with 57735 digits that is reached after 18 steps. Sometimes it even gets downright ridiculous: the fraction $$\frac{200}{199}$$ has a destination with no less than $$10^{435}$$ digits. It is conjectured but not yet proven that iterated application of almost squaring always terminates in an integer.
We consider fractions $$\frac{n}{d}$$ whose numerator $$n \in \mathbb{N}$$ and whose denominator $$d \in \mathbb{N}_0$$. Your task:
Write a function reduce that takes the numerator $$n$$ (int) and denominator $$d$$ (int) of a fraction. The function must return the numerator (int) and the denominator (int) of the fraction $$\frac{n}{d}$$ reduced to its lowest terms.
The greatest common divisor of two integers can be computed using the function gcd2 from the math module in The Python Standard Library3.
Write a function almost_square that takes the numerator $$n$$ (int) and denominator $$d$$ (int) of a fraction. The function must return the numerator (int) and the denominator (int) of the almost square of the fraction $$\frac{n}{d}$$, reduced to its lowest terms.
Write a function destination that takes the numerator $$n$$ (int) and denominator $$d$$ (int) of a fraction, where $$1 \leq d < n$$. The function must return the destination (int) of the fraction $$\frac{n}{d}$$.
Write a function steps that takes the numerator $$n$$ (int) and denominator $$d$$ (int) of a fraction, where $$1 \leq d < n$$. The function must return the number of steps (int) after which the fraction $$\frac{n}{d}$$ reaches its destination.
>>> reduce(2, 4)
(1, 2)
>>> almost_square(8, 7)
(16, 7)
>>> almost_square(16, 7)
(48, 7)
>>> almost_square(48, 7)
(48, 1)
>>> destination(8, 7)
48
>>> destination(10, 6)
1484710602474311520
>>> destination(17, 13)
59832260230817687634146563200
>>> steps(8, 7)
3
>>> steps(10, 6)
6
>>> steps(17, 13)
7