# Do these rational sequences always reach an integer?

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)])

• Just to remark that the denominator of $u_{n+1}$ is a factor of the denominator of $u_n$, so a counterexample would end up on infinitely many rational numbers all with the same denominator. Dec 2 '20 at 12:35
• A remark is this can be prove when the denominator of $u_0$ is 2 by directly computation, and it is already a little bit complicated when changing the denominator to $2^k$ or $3$, another remark is we only need to consider the case of $p^k, p$ prime, $k\in \mathbb{N}^*$ Dec 17 '20 at 8:11
• @katago: I know the proof for $2$, but not for $3$ or $2^k$, $k \ge 2$. Please write it as an answer. Dec 17 '20 at 8:23

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

$$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; 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.

• Not related to anything, but I am amused that the ambiguity of spoken word operator precedence is now defined in a sequence of interest. The sequence injects parentheses and then drops them, $2*5+1 \rightarrow 2*(5+1) = 2*5+2 \rightarrow 2*(5+2)$ etc Dec 3 '20 at 4:22
• It is good that it can reduce to a sequence of natural numbers. I coded your way in order to get a better checking than I already did. My problem is that the integers become huge so that I cannot use computer integer (64-bit), which would make the computation 100 times quicker. Can the sequence be reduced to bounded natural numbers, for example, to integers mod p? Dec 3 '20 at 10:21

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

• Sebastien Palcoux； yes but I do not claim for all $n\in \mathbb{N}^*$, $1\leq a_k(n)\leq p-1$, I just requre $a_k=a_k(0)$ is the k-th digit of $u_0$ in the base $p$ expension. Dec 17 '20 at 13:47
• Sebastien Palcoux： yes I try to calculate for $a_k(n)$ where $a_k(n)$ is the k-th digit of p expansion in $u_n$, but the recurrence formula only true when there is no arithmetic carry in $a_0(n), a_1(n),...,a_k(n)$ Dec 17 '20 at 13:57
• It should be $a_0(k)$, already corrected. Dec 17 '20 at 13:58
• I am confused with the rescaling $u_0 \to pu_0$. Is it possible to avoid it, and to just write $u_0=\sum_{k=-1}^{\infty}a_kp^k$ (and in general, $\sum_{k=-t}^{\infty}a_kp^k$)? Dec 17 '20 at 14:01
• So you only know a proof for $2$, but not yet for $2^k$ or $3$, right? Your framework is promising for a more general proof, but for $2$, there is the following shorter proof by contradiction: assume that $(u_n)$ never reach an integer, then for all $n$ we must have $u_n=k_n + \frac{1}{2}$, but $u_{n+1} = k_n + \frac{k_n}{2}$, so $k_n$ must be odd for all $n$. So $k_n=2h_n+1$, $u_n=2h_n+1 + \frac{1}{2}$, and $u_{n+1} = 3h_n+1+\frac{1}{2}$, which means that $2h_{n+1}=3h_n$, it follows that $h_n = (\frac{3}{2})^nh_0$, and so $2^n$ divides $h_0$ for all $n$, contradiction. Dec 17 '20 at 14:51