162
$\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$
8
  • 39
    $\begingroup$ This is actually a cool question! $\endgroup$ Jun 30 '20 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 '20 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 '20 at 23:12
  • 3
    $\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 '20 at 16:09
  • 4
    $\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 '20 at 16:48
54
$\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 '20 at 2:17
  • 5
    $\begingroup$ The sequence is decreasing, but that does not prove that it terminates. $\endgroup$
    – Paul
    Jul 1 '20 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 '20 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 '20 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 '20 at 17:26
38
$\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 '20 at 2:18
  • 1
    $\begingroup$ @Zim Thanks, yes, visualizing things often helps making things clear for me. $\endgroup$
    – Paul
    Jul 2 '20 at 17:59
  • 3
    $\begingroup$ this is astounding, thank you very much! $\endgroup$
    – Zim
    Jul 2 '20 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 '20 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 '20 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 '20 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 '20 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 '20 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.