24
$\begingroup$

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:
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(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)])
$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ Dec 2 '20 at 12:35
  • 1
    $\begingroup$ 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}^*$ $\endgroup$
    – katago
    Dec 17 '20 at 8:11
  • $\begingroup$ @katago: I know the proof for $2$, but not for $3$ or $2^k$, $k \ge 2$. Please write it as an answer. $\endgroup$ Dec 17 '20 at 8:23
10
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ 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 $\endgroup$
    – Ben Burns
    Dec 3 '20 at 4:22
  • $\begingroup$ 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? $\endgroup$ Dec 3 '20 at 10:21
1
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – katago
    Dec 17 '20 at 13:47
  • $\begingroup$ 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)$ $\endgroup$
    – katago
    Dec 17 '20 at 13:57
  • $\begingroup$ It should be $a_0(k)$, already corrected. $\endgroup$
    – katago
    Dec 17 '20 at 13:58
  • 1
    $\begingroup$ 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$)? $\endgroup$ Dec 17 '20 at 14:01
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 17 '20 at 14:51

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.