Do these rational sequences always reach an integer?

Question

This post comes from the suggestion of Joel Moreira in a comment on An alternative to continued fraction and applications (itself inspired by the Numberphile video 2.920050977316 and Fridman, Garbulsky, Glecer, Grime, and Tron Florentin - A prime-representing constant).

Let $u_0 \ge 2$ be a rational, and $u_{n+1}=⌊u_n⌋(u_n - ⌊u_n⌋ + 1)$.
Question: Does the sequence $(u_n)$ reach an integer?

$\to$ see below the application to irrational number theory.

Remark: It is true for $u_0=\frac{p}{q}$ with $p \le 40000$ (see Appendix).

Proposition: It is always true for $u_0 = \frac{p}{2}$.
Proof by contradiction: Assume that the sequence never reach an integer, then $u_n = k_n + \frac{1}{2}$ for all $n$. Next note that $u_{n+1} = k_n + \frac{k_n}{2}$, so $k_n$ must be odd for all $n$. Let write $k_n = 2 h_n +1$, then $u_n = 2h_n+1+\frac{1}{2}$ (with $h_n \ge 1$) and $u_{n+1} = 3h_n+1+\frac{1}{2}$. It follows that $2h_{n+1} = 3h_n$, and so $h_n = (\frac{3}{2})^nh_0$, which implies that $2^n$ divides $h_0$ for all $n$, contradiction. $\square$

For $u_0=\frac{11}{5}$, then $$(u_n)= (\frac{11}{5}, \frac{12}{5}, \frac{14}{5}, \frac{18}{5}, \frac{24}{5}, \frac{36}{5}, \frac{42}{5}, \frac{56}{5}, \frac{66}{5}, \frac{78}{5}, 24, \dots).$$ Here is a picture of the dynamic:

By regarding (for example) when $u_0=\frac{15}{7}$ below, we guess that the general proof should be hard. $(u_n) = (\frac{15}{7}, \frac{16}{7}, \frac{18}{7}, \frac{22}{7}, \frac{24}{7}, \frac{30}{7}, \frac{36}{7}, \frac{40}{7}, \frac{60}{7}, \frac{88}{7}, \frac{132}{7}, \frac{234}{7}, \frac{330}{7}, \frac{376}{7}, \frac{636}{7}, \frac{1170}{7}, \frac{1336}{7}, \frac{2470}{7}, \frac{4576}{7}, \frac{7836}{7}, \frac{11190}{7}, \frac{17578}{7}, \frac{20088}{7}, \frac{34428}{7}, \frac{44262}{7}, \frac{50584}{7}, \frac{65034}{7}, \frac{102190}{7}, \frac{160578}{7}, 39324, \dots)$

For $u_0=\frac{10307}{4513}=\frac{k_0}{q}$, the sequence $(\frac{k_n}{q})=(u_n)$ reaches an integer at $n=58254$. The sequence $(u_n)$ reaches an integer once $k_n \text{ mod } q=0$. Below is the picture for $(n,k_n \text{ mod } q)$; it looks completely random. The probability for $s$ random integers between $0$ and $q-1$ to never be zero is about $e^{-s/q}$ when $q$ is large enough.

Application to irrational number theory

According to the paper mentioned above, there is a bijection between the set of numbers $u_0 \ge 2$, and the set of sequences $(a_n)$ such that for all $n$:

• $a_n \in \mathbb{N}_{\ge 2}$,
• $a_n \le a_{n+1} < 2a_n$.

The bijection is given by: $$u_0 \mapsto (a_n) \text{ with } a_n = ⌊u_n⌋ \text{ and } u_{n+1}=⌊u_n⌋(u_n - ⌊u_n⌋ + 1),$$ $$(a_n) \mapsto u_0 = \sum_{n=0}^{\infty}\frac{a_n-1}{\prod_{i=0}^{n-1}a_i}.$$ A positive answer to the question would provide a kind of alternative to continued fraction, in the sense of a natural way to represent the numbers, with a complete characterization of the irrational ones, which here would be that $\lim_{n \to \infty} (a_n)=\infty$.

---

Appendix

In the following list the datum $[r,(p,q)]$ means that the sequence $(u_n)$, with $u_0=\frac{p}{q}$, reaches an integer at $n=r$. The list provides the ones with the longest $r$ according the lexicographic order of $(p,q)$.

Computation

sage: search(40120)
[1, (2, 1)]
[2, (5, 2)]
[3, (7, 2)]
[4, (7, 3)]
[11, (11, 5)]
[30, (15, 7)]
[31, (29, 14)]
[45, (37, 17)]
[53, (39, 17)]
[124, (41, 19)]
[167, (59, 29)]
[168, (117, 58)]
[358, (123, 53)]
[380, (183, 89)]
[381, (201, 89)]
[530, (209, 97)]
[532, (221, 97)]
[622, (285, 131)]
[624, (295, 131)]
[921, (359, 167)]
[1233, (383, 181)]
[1365, (517, 251)]
[1482, (541, 269)]
[2532, (583, 263)]
[3121, (805, 389)]
[3586, (1197, 587)]
[3608, (1237, 607)]
[3860, (1263, 617)]
[4160, (1425, 643)]
[6056, (1487, 743)]
[9658, (1875, 859)]
[9662, (1933, 859)]
[10467, (2519, 1213)]
[10534, (2805, 1289)]
[11843, (2927, 1423)]
[12563, (3169, 1583)]
[13523, (3535, 1637)]
[14004, (3771, 1871)]
[14461, (4147, 2011)]
[17485, (4227, 1709)]
[18193, (4641, 1987)]
[18978, (4711, 2347)]
[22680, (5193, 2377)]
[23742, (5415, 2707)]
[24582, (5711, 2663)]
[27786, (5789, 2837)]
[27869, (6275, 2969)]
[29168, (6523, 3229)]
[32485, (6753, 2917)]
[33819, (7203, 3361)]
[41710, (7801, 3719)]
[49402, (8357, 3863)]
[58254, (10307, 4513)]
[58700, (10957, 4943)]
[81773, (12159, 5659)]
[85815, (16335, 7963)]
[91298, (16543, 7517)]
[91300, (17179, 7517)]
[98102, (19133, 9437)]
[100315, (19587, 8893)]
[100319, (20037, 8893)]
[102230, (20091, 9749)]
[102707, (21289, 10267)]
[103894, (21511, 10151)]
[105508, (22439, 11149)]
[107715, (22565, 10729)]
[142580, (23049, 11257)]
[154265, (24915, 12007)]
[177616, (27461, 13421)]
[178421, (32063, 15377)]
[190758, (34141, 16547)]
[228068, (34783, 15473)]
[228876, (35515, 17477)]
[277844, (40119, 19391)]

Code

def Seq(p,q):
    x=Rational(p/q)
    A=[floor(x)]
    while not floor(x)==x:
        n=floor(x)
        x=Rational(n*(x-n+1))
        m=floor(x)
        A.append(m)
    return A

def search(r):
    m=0
    for p in range(2,r):
        for q in range(1,floor(p/2)+1):
            A=Seq(p,q)
            l=len(A)
            if l>m:
                m=l
                print([m,(p,q)])

Answer 1

I want to leave a few elementary comments, maybe they will be helpful.

The question asks about recurrence relation

$$ u_{n+1}= \lfloor u_n \rfloor (u_n − \lfloor u_n \rfloor + 1) $$

Suppose you write rational $u$ in terms of natural numbers $\frac{pq+r}{p}$. Then $\lfloor u \rfloor = q$. The recurrence relation is now

$$ u_{n+1} = q_n (\frac{pq_n+r_n}{p} − q_n + 1) \\ = q_n (\frac{pq_n+r_n− pq_n + p}{p} ) \\ = \frac{q_n(r_n + p)}{p} $$

Therefore, we can investigate the same series in natural numbers $u_{n+1}=q_n(r_n + p)$ asking when the series converges to a multiple of $p$. Now we have to deal with $r_{n+1} = q_n * r_n \mod p$ and $q_{n+1} = \lfloor u_{n+1} / p\rfloor$ but let me show the benefit. First compare to the original $u_0 = 11/5$.

Now $p=5, q_0=2,r_0=1$.

$$ u_0 = 2*5 + 1 \\ u_{n+1} = 2*(5+1) = 12 \\ u_{n+2} = 2*(5+2) = 14\\ u_{n+3} = 2*(5+4) = 18\\ u_{n+4} = 3*(5+3) = 24\\ u_{n+5} = 4*(5+4) = 36\\ u_{n+5} = 7*(5+1) = 42\\ u_{n+6} = 8*(5+2) = 56\\ u_{n+7} = 11*(5+1) = 66\\ u_{n+8} = 13*(5+1) = 78\\ u_{n+9} = 15*(5+3) = 120\\ u_{n+10} = 24*(5+0) = 120\\ $$

The sequence continues indefinitely once $r_n=0$.

---

Minor remark: $q_{n+1} \ge q_n$. By definition, $q_{n+1} = \lfloor u_{n+1} / p\rfloor \rightarrow \lfloor q_n(r_n + p) / p\rfloor$.

---

Minor remark: There are no cycles of length 1. A cycle would require $q_{n+1}=q_n$ and $r_{n+1}=r_n$. The same $q_{n+1}$ implies $q_n * r_n \lt p$. And therefore the only way for $r_{n+1} =r_n$ is if $q_n=1$, but it is required $q_n>2$ (by definition on $u_0$).

---

Now a rough sketch showing that "many" $u_0$ converge. Consider when $p=10$. The same logic will apply to other $p$ (prime and composite) but the analogy here is easiest. Note that $10=5*2$. Therefore, when $u_n$ "steps" into values $50-59$, half the time (even numbers) the following step will terminate:

$$ 50 => 5*(10 + 0) => 50\\ 51 => 5*(10 + 1) => 55\\ 52 => 5*(10 + 2) => 60\\ 53 => 5*(10 + 3) => 65\\ 54 => 5*(10 + 4) => 70\\ 55 => 5*(10 + 5) => 75\\ 56 => 5*(10 + 6) => 80\\ 57 => 5*(10 + 7) => 85\\ 58 => 5*(10 + 8) => 90\\ 59 => 5*(10 + 9) => 95 $$

This will also be the case for other values that factor to $5*m$ (for $p=10$) such as $150-159(=3*5), 250-259(=5*5)$ etc. Other composite $2*p$ behave similar, e.g., $p=14$ then half of $70-79$ terminate in one step. This can be applied to factors other than $2$. Additionally, this idea of finding "terminating zones" also applies to a number of $u_n$ for prime $p$, which can be easily decided as terminating in the area of $p^2-p$. For instance, with $p=5$, then there is a value $q_n=p-1$ and some $r$ such that $p^2<u_n<p^2+p$; in this example, $q_n=4,r_n=2\rightarrow 4*(5+2)=28$ and the sequence terminates after $5*(5+3)$.

There are still many other cases yet to prove, but maybe this post was helpful.

Answer 2

$u_{0} \in \mathbb{Q} \quad u_{n+1}=\left[u_{n}\right]\left(u_{n}-\left[u_{n}\right]+1\right)$, then $\{u_{n}\}_{n=1}^{+\infty}$ reach in integer. $\quad (*)$

This can be proved if we prove,

$p$ prime, $t\in \mathbb{N}^{*}$ $p^{t} u_{0} \in \mathbb{N}^{*}$, $\left\{u_{k}\right\}_{n=1}^{+\infty}$ reach an integer. we call this as property $I(p,t)$.

It is easy to check if we proved $I(p,t)$ $\forall t\in \mathbb{N}^{*}$. $\forall p$ prime , $I(p,t)$ is true then we proved $ (*)$.

Now we focus ourself for a fix problem $I(p,t)$, $p$ prime and we first consider the case $t=1$.

We rescaling the sequence, dilate it with $p$, and still use $u_k$ to express the new sequence, and write it in $p$-expension.

$ \quad u_{0} \longrightarrow p u_{0}, u_{0}=\sum_{k=0}^{+\infty} a_{k} p^{k}$

then the sequence satisfied, $$u_{n+1}=\left(\sum^{+\infty}_{k=0} a_{k+1}(n) p^{k}\right)\left(a_{0}(n)+p\right) \quad (**)$$

$\Rightarrow \quad a_{k}(n+1)=a_{0}(n) a_{k+1}(n)+a_{k}(n) . \quad \forall k \geqslant 0$

Where $a_k$ is the $k$-th digit of $p$-expension of $u$ and $a_k(n)$ is the $k$-digit of $p$-expension of $u_n$, then for previous $a_k$ we have $a_k=a_k(0)$.

Remark. And in general, we can not find the formula of general term, (**) is only true for the first several digits of $u_k$, how many digits can involve depending on $u_0$, because we need to avoid arithmetic carry.

then $II(p, k)$ is the following property $$\left\{u_{n}\right\}_{n=1}^{+\infty}, \exists k\in \mathbb{N}^*, a_0(k)=0$$

And it is easy to check $II(p, k)$ is equivalent to $I(p, k)$, for all $p$ prime, $k\in \mathbb{N}^*$.

---

For $II(2, 1)$ we are lucky this case is very special and can be check $II(2, 1)$ is true by directly check the first $k$-digits in the 2-expension of $u_0$, i.e. $a_i(0)$, for $0\leq i\leq k$.

If the first 2 digits of $u_0$ are 10 , then $II(2.1)$ is true.
If the first 3 digits of $u_0$ are 101 , then $II(2.1)$ is true.
If the first 4 digits of $u_0$ are 1001 , then $II(2.1)$ is true.
$......$
If the first $k$ digits of $u_0$ are $1\underbrace{00...0}_{k-2}1$ , then $II(2.1)$ is true. So the only case $II(2.1)$ false is when $u_0=1$, which corresponding to the case for original $u_0$, $u_0=\frac{1}{2}$.

Remark. And this argument itself is hopeless to prove $II(3, 1)$ is true, the new idea will be required for proving this and general $II(p, 1)$, the first main obstacle is we can not find a control(if do not lead contradiction already) from first several digits of $u_k$ to control first several digits of $u_{k+1}$ by the following strategy,
If the first $k$-th digits of $u_0$ don't fall into some special case, we get contradictions, thus restricting the first several digits of $u_0$ to a smaller set. Lose the control makes us fall into endless case checking.
$II(2, k)$ seems to be more tractable by the same reason as $II(2, 1)$ but I can not figure out a proof.