Skip to main content
10 of 11
addition of an application: explanation in what sense a positive answer would provide an alternative to continued fraction
Sebastien Palcoux
  • 27k
  • 5
  • 74
  • 186

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 32000$ (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:
enter image description here

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.

enter image description here

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(32064)
[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)]

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)])
Sebastien Palcoux
  • 27k
  • 5
  • 74
  • 186