# What happens when we (incorrectly) make improper fractions proper again?

Many folks avoid the "mixed number" notation such as $$4\frac{2}{3}$$ due to its ambiguity. The example could mean "$$4$$ and two thirds", i.e. $$4+\frac{2}{3}$$, but one may also be tempted to multiply, resulting in $$\frac{8}{3}$$.

My questions pertain to what happens when we iterate this process -- alternating between changing a fraction to a mixed number, then "incorrectly" multiplying the mixed fraction. The iteration terminates when you arrive at a proper fraction (numerator $$\leq$$ denominator) or an integer. I'll "define" this process via sufficiently-complicated example:

$$\frac{14}{3} \rightarrow 4 \frac{2}{3} \rightarrow \frac{8}{3} \rightarrow 2 \frac{2}{3} \rightarrow \frac{4}{3} \rightarrow 1\frac{1}{3}\rightarrow \frac{1}{3}.$$

1. Does this process always terminate?

2. For which $$(p,q)\in\mathbb{N}\times(\mathbb{N}\setminus\{0\})$$ does this process, with initial iterate $$\frac{p}{q}$$, terminate at $$\frac{p \mod q}{q}$$?

• This is actually a cool question! Jun 30 '20 at 22:53
• We transform $a+\frac{b}{c}=\frac{ac+b}{c}$ into $\frac{ab}{c}$ , which is smaller because of $ac+b>ab+b>ab$ , hence the process terminates whenever $q>1$ Jun 30 '20 at 22:56
• The process you describe is easily expressed as the recurrence equation: $$a_{n+1}=\lfloor a_n\rfloor(a_n-\lfloor a_n\rfloor);\quad a_0=\frac{p}{q}$$ Jun 30 '20 at 23:12
• Is there really a culture in which $4 \frac 2 3$ is parsed as $4 \cdot \frac 2 3$ and not $4 + \frac 2 3$? In my whole time at school and university (in germany), this has always meant $4 + \frac 2 3$, I never considered the possibility that it could be parsed as multiplication. The interpretation as sum is also what is used in everyday speech, exclusively. Jul 1 '20 at 16:09
• @Polygnome Usually, I find that mixed numbers with actual digits are rarely ambiguous, but the real confusion lies in generalization by introducing variables: $e \frac{\pi}{x}$. I like the question, but I think you have a point. Jul 1 '20 at 16:48

Yes, the process does always terminate.

Here's why:

Consider the mixed number $$a\frac{b}{c}$$, where $$0 \le b < c$$ and $$a > 0$$. Then, it is clear that $$ab < ac+b$$, and so the process always continues to lead to smaller and smaller fractions with the same denominator $$c$$ until the numerator finally becomes smaller than $$c$$.

In case of a negative mixed number $$-a\frac{b}{c}$$, remember that this means "$$-(a+\frac{b}{c})$$", not "$$(-a)+\frac{b}{c}$$". But one can easily ignore the negative sign, so without loss of generality, one can consider positive mixed numbers only.

• Interesting, thanks for answering part 1! Please let me know if you also solve part 2 :)
– Zim
Jul 1 '20 at 2:17
• The sequence is decreasing, but that does not prove that it terminates.
– Paul
Jul 1 '20 at 16:48
• @Paul Indeed, $\frac{1}{2} > \frac{1}{3} > \frac{1}{4} > ...$ is a strictly decreasing sequence of fractions that never terminates, for example. Thanks for pointing that out! I will edit my answer to make it clear that it is really about the numerators only. Jul 1 '20 at 16:58
• "...with the same denominator..." - The denominator can change if $a$ and $c$ share a factor. The result is still correct, since that can happen only finitely-many times. Jul 1 '20 at 18:49
• This is a classic application of the fact that, when positive integers shrink, they have to shrink by at least $1$, so can only do so finitely many times.
– J.G.
Jul 2 '20 at 17:26

The formula given by R. Burton in a comment is very useful for analyzing this problem. We have the following iteration function, where $$\lfloor x \rfloor$$ is the floor function: $$f(x) = \lfloor x \rfloor(x-\lfloor x \rfloor)$$ We get a sequence by repeatedly applying this function until $$a_n$$ is an integer or $$0 < a_n < 1$$. $$\begin{array}{rcl} a_0 &=&\frac{p}{q} \\ a_{n+1} &=& f(a_n) \end{array}$$ Note that we can just as well take a value for $$a_0$$ that is not a rational number but an arbitrary positive real number. I think this generalization makes the problem easier, because we can forget about numerators and denominators.

This is the plot of $$f$$: You can see that, for example, if $$4 < x < 5$$, then $$0 < f(x) < 4$$.

If we call the area between two adjacent integers on the x-axis a column, then we can say that with every application of $$f$$, the value of $$a_n$$ moves at least one column to the left. Or, in a formula, $$\lfloor a_{n+1} \rfloor < \lfloor a_n \rfloor$$.

But of course $$a_n$$ is never negative, so this process must terminate.

# Problem 2

Let $$f^*$$ be the function $$f$$ repeated until the result is an integer or between 0 and 1. Where $$f^*$$ is continuous, its graph looks like this, lines from 0 to 1 directly next to each other: The vertical gray lines indicate where $$f^*$$ is discontinuous and has a positive integer value. (value is not visible in the plot.) The positions of the vertical lines can be calculated with the following recurrence relation. The set $$L_i$$ contains all discontinuities of $$f^*$$ up to $$i$$ and has $$2^{i-1}$$ elements. $$\begin{array}{rcl} L_1 &=& \{1\} \\ L_{i+1} &=& L_i\ \cup\ \{i + \frac{k}{i}\ |\ k \in L_i\} \end{array}$$ For drawing the plot I used $$L_7$$, which is equal to $$\left\{1,2,\frac{5}{2},3,\frac{10}{3},\frac{11}{3},\frac{23}{6},4,\frac{17}{4},\frac{9}{2},\frac{37}{8},\frac{19}{4},\frac{29}{6},\frac{59}{12},\frac{119}{24},5,\frac{26}{5},\frac{27}{5},\frac{11}{2},\frac{28}{5},\frac{17}{3},\frac{86}{15},\frac{173}{30},\frac{29}{5},\frac{117}{20},\frac{59}{10},\frac{237}{40},\frac{119}{20},\frac{179}{30},\frac{359}{60},\frac{719}{120},6,\frac{37}{6},\frac{19}{3},\frac{77}{12},\frac{13}{2},\frac{59}{9},\frac{119}{18},\frac{239}{36},\frac{20}{3},\frac{161}{24},\frac{27}{4},\frac{325}{48},\frac{163}{24},\frac{245}{36},\frac{491}{72},\frac{983}{144},\frac{41}{6},\frac{103}{15},\frac{69}{10},\frac{83}{12},\frac{104}{15},\frac{125}{18},\frac{313}{45},\frac{1253}{180},\frac{209}{30},\frac{279}{40},\frac{419}{60},\frac{559}{80},\frac{839}{120},\frac{1259}{180},\frac{2519}{360},\frac{5039}{720},7\right\}.$$

The corresponding Mathematica code is: (Wolfram Alpha)

Fold[Join[#1, #2 + #1/#2] &, {1}, Range]


Let $$x = \frac{p}{q}$$ be a positive number, then we have $$f^* \left( \frac{p}{q} \right) = \frac{p \mod q}{q}\quad \iff \quad f^*(x) = x - \lfloor x \rfloor.$$ If we draw $$x - \lfloor x \rfloor$$ on top of $$f^*(x)$$, we get this image: The equation $$f^*(x) = x - \lfloor x \rfloor$$ is true where the blue and orange lines overlap or cross, except at positive integers, where it is false because the right hand side is $$0$$.

We can see that the equation holds for $$0 \le x < 1$$ and $$1 < x < 2$$. It is also true at one point on every blue line that does not start or end at an integer. So for every integer $$n \ge 2$$, there are $$|L_{n+1}| - |L_n| - 2 = 2^{n-1}-2$$ points between $$n$$ and $$n+1$$ for which the equation is true.

To get the coordinates of the points, we have to equate a blue line with an orange line. Let $$a$$ and $$b$$ be the values of two adjacent non-integer discontinuity points, for example $$a = \frac{10}{3}$$ and $$b = \frac{11}{3}$$ to get the first point. Then the equations for the blue and orange lines are: $$\begin{array}{rcl} l_b(x) &=& \frac{x - a}{b - a} \\ l_o(x) &=& x - \lfloor a \rfloor \end{array}$$ Solving $$l_b(x) = l_o(x)$$ gives us: $$x = \frac{a + \lfloor a \rfloor(a - b)}{1 + a - b}$$ In Mathematica we can use this code to output all numbers between 2 and 7 for which the equation holds:

x[a_, b_] := (a + Floor[a](a - b)) / (1 + a - b);
list = Fold[Join[#1, #2 + #1/#2] &, {1}, Range];
intervals = Select[Partition[list, 2, 1], NoneTrue[#, IntegerQ] &];
points = x @@ # & /@ intervals


This gives us $$\left\{\frac{7}{2},\frac{19}{5},\frac{13}{3},\frac{32}{7},\frac{33}{7},\frac{53}{11},\frac{54}{11},\frac{114}{23},\frac{21}{4},\frac{49}{9},\frac{50}{9},\frac{79}{14},\frac{40}{7},\frac{167}{29},\frac{168}{29},\frac{111}{19},\frac{112}{19},\frac{77}{13},\frac{232}{39},\frac{352}{59},\frac{353}{59},\frac{713}{119},\frac{31}{5},\frac{70}{11},\frac{71}{11},\frac{111}{17},\frac{112}{17},\frac{232}{35},\frac{233}{35},\frac{154}{23},\frac{155}{23},\frac{318}{47},\frac{319}{47},\frac{483}{71},\frac{484}{71},\frac{976}{143},\frac{977}{143},\frac{199}{29},\frac{200}{29},\frac{408}{59},\frac{409}{59},\frac{618}{89},\frac{619}{89},\frac{1246}{179},\frac{1247}{179},\frac{830}{119},\frac{831}{119},\frac{1670}{239},\frac{1671}{239},\frac{2511}{359},\frac{2512}{359},\frac{5032}{719}\right\}.$$

• Awesome, thanks for the interesting approach as well as the graphical accompaniment! I look forward to reading more :)
– Zim
Jul 2 '20 at 2:18
• @Zim Thanks, yes, visualizing things often helps making things clear for me.
– Paul
Jul 2 '20 at 17:59
• this is astounding, thank you very much!
– Zim
Jul 2 '20 at 18:23

Partial answer for 2: if $$q = 2$$, the process will terminate at $$\frac12$$ iff $$p = 2^k - 1 \, (k \in \mathbb{N})$$ and at an integer otherwise. This is because the only way to end up with a $$1$$ in the numerator is by having an integer part of $$1$$ and a numerator of $$1$$, so $$1\frac12 = \frac32$$. The only way to end up at $$\frac32$$ is from $$3\frac12$$, etc. It doesn't matter that $$15 = 3 \cdot 5$$, you can't have anything other than $$1$$ in the numerator.

So if $$q = 2$$, the final numerator is, modulo q, equal to the original $$p$$ iff $$p$$ is even or $$p = 2^k - 1$$.

For other $$q$$, it's much harder to find a general 'formula', but as @isaacg notes, the case above can be generalized to numbers of the form $$p_k=\frac{q^k-1}{q-1}$$:

$$\frac{q^k-1}{q-1}=\frac{qq^{k-1}-q+q-1}{q-1}=q\frac{q^{k-1}-1}{q-1}+1=qp_{k-1}+1$$

so $$p_k \equiv 1 \pmod q$$, and the improper fraction $$\frac{p_k}{q}$$ is equal to $$p_{k-1}\frac1q$$ which becomes $$\frac{p_{k-1}}{q}$$ in the next step, and we end up with $$\frac1q$$.

Those are not the only cases, e.g. $$\frac53 \to 1\frac23 \to \frac23$$ is another 'proper' (non-integer-ending) example.

• Nitpick: if $p$ is even, then $p/q$ is an integer and the process terminates there, not with a numerator of $(p \mod q) = 0$. Jul 1 '20 at 21:01
• @MichaelSeifert yeah, I interpreted it as the final numerator must be equal to the original one (mod q). Jul 1 '20 at 21:07
• We can generalize this to say that for any base $q$, a number of the form $11 \ldots 1_q$ will always have this property. Jul 1 '20 at 23:00
1. Does this process always terminate?

Yes. The process described is simply the evaluation of the recurrence relation...

$$a_{n+1}=\lfloor a_n\rfloor(a_n-\lfloor a_n\rfloor);\quad a_0=\frac{p}{q}$$

...where $$\lfloor\cdot\rfloor$$ is the floor function, while $$a_n>0$$.

To show that the process terminates, it suffices to show that there is some $$n$$ such that $$a_n=0$$.

A proof-sketch follows:

Suppose that there is some $$n$$ such that $$a_n$$ is an integer. Then $$a_{n+1}=0$$ and we are done.

Suppose that there is no $$n$$ such that $$a_n$$ is an integer. Let $$c=\max\{a_n-\lfloor a_n\rfloor:n\in\Bbb{N}\}$$ (note that $$c<1$$). It follows that...

$$a_{n+1}\le\lfloor a_n\rfloor c\le a_nc$$

Because $$a_{n+1}=a_nc$$ has closed form $$a_n=a_0c^n$$, we know that $$a_n\le a_0c^n$$. Since $$\lim_{n\to\infty}a_0c^n=0$$ and $$0\le a_n$$ for all $$n$$, it follows that $$\lim_{n\to\infty}a_n=0$$. By definition of the limit of a sequence, there must exist some $$n$$ such that $$a_n-0<1$$. Let $$k$$ be the least such $$n$$, then $$a_{k+1}=0$$ and we are done.

The convention employed @GeoffreyTrang can be used for dealing with negative rationals.

1. For which $$(p,q)\in\mathbb{N}\times(\mathbb{N}\setminus\{0\})$$ does this process, with initial iterate $$\frac{p}{q}$$, terminate at $$\frac{p \mod q}{q}$$?

It is easier to consider the pairs for which the process doesn't terminate at $$\frac{p\mod q}{q}$$.

To start with, note let $$h(p,q)$$ be the last value prior to termination, as described above. It is worth noting that $$h(p,q)=h(np,nq)$$ for any $$n\in\Bbb{Z}^+$$ - so it is only necessary to consider the proportion between $$p$$ and $$q$$. We can identify each such proportion with a line through $$\Bbb{N}\times\Bbb{Z}^+$$.

(more to follow)

(see @Paul 's answer for solution)

• You have "Let $c=\max\{a_n−⌊an⌋:n∈\mathbb{N}\}$", but it's not clear to me that such a max must exist; an infinite bounded set, even of rationals, need not have a maximum, e.g. $\{ (n-1)/n : n \in \mathbb{N}, n > 0\}$. Probably it works here because there's only finitely many possible values, based on the initial denominator. Jul 3 '20 at 3:09
• Correct, but as you point out the set $\{a_n-\left\lfloor a_n\right\rfloor : n\in\Bbb{N}\}$ is finite. The maximum also isn't strictly necessary, since you can use the argument "$a_n$ is decreasing" even if the set is not finite. I chose to assume the existence of the maximum because you can see that $c^n$ decreases by putting it into a graphing calculator, whereas a proof that "for a sequence of rational numbers $(c_i)_{i\in\Bbb{N}}$, such that $c_i<1$ for all $i\in\Bbb{N}$, the product $\prod_{i=0}^n c_n$ converges to $0$ as $n\to\infty$," demands a lot more from the reader. Jul 3 '20 at 21:18