164
$\begingroup$

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}$?

$\endgroup$
9
  • 41
    $\begingroup$ This is actually a cool question! $\endgroup$ Jun 30, 2020 at 22:53
  • 4
    $\begingroup$ 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$ $\endgroup$
    – Peter
    Jun 30, 2020 at 22:56
  • 11
    $\begingroup$ 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}$$ $\endgroup$
    – R. Burton
    Jun 30, 2020 at 23:12
  • 4
    $\begingroup$ 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. $\endgroup$
    – Polygnome
    Jul 1, 2020 at 16:09
  • 6
    $\begingroup$ @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. $\endgroup$
    – Bladewood
    Jul 1, 2020 at 16:48

4 Answers 4

56
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Interesting, thanks for answering part 1! Please let me know if you also solve part 2 :) $\endgroup$
    – Zim
    Jul 1, 2020 at 2:17
  • 5
    $\begingroup$ The sequence is decreasing, but that does not prove that it terminates. $\endgroup$
    – Paul
    Jul 1, 2020 at 16:48
  • 3
    $\begingroup$ @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. $\endgroup$ Jul 1, 2020 at 16:58
  • 9
    $\begingroup$ "...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. $\endgroup$ Jul 1, 2020 at 18:49
  • 2
    $\begingroup$ 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. $\endgroup$
    – J.G.
    Jul 2, 2020 at 17:26
39
$\begingroup$

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$:

Iteration graph

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:

Repeated function graph

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[6]]

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:

Two plots

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[6]];
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\}. $$

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

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ Jul 1, 2020 at 21:01
  • $\begingroup$ @MichaelSeifert yeah, I interpreted it as the final numerator must be equal to the original one (mod q). $\endgroup$
    – Glorfindel
    Jul 1, 2020 at 21:07
  • $\begingroup$ 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. $\endgroup$
    – isaacg
    Jul 1, 2020 at 23:00
8
$\begingroup$
  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)

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jul 3, 2020 at 3:09
  • $\begingroup$ 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. $\endgroup$
    – R. Burton
    Jul 3, 2020 at 21:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .