Ces suites rationnelles atteignent-elles toujours un entier?

Dec 02 2020

Ce message provient de la suggestion de Joel Moreira dans un commentaire sur Une alternative à la fraction continue et aux applications (elle-même inspirée de la vidéo Numberphile 2.920050977316 et de Fridman, Garbulsky, Glecer, Grime et Tron Florentin - Une constante représentant le premier ).

Laisser $u_0 \ge 2$ être un rationnel, et $u_{n+1}=⌊u_n⌋(u_n - ⌊u_n⌋ + 1)$.
Question : Est-ce que la séquence$(u_n)$ atteindre un entier?

$\to$ voir ci-dessous l'application à la théorie irrationnelle des nombres.

Remarque : c'est vrai pour$u_0=\frac{p}{q}$ avec $p \le 40000$ (voir l'annexe).

Proposition : C'est toujours vrai pour$u_0 = \frac{p}{2}$.
Preuve par contradiction : Supposons que la séquence n'atteigne jamais un entier, alors$u_n = k_n + \frac{1}{2}$ pour tous $n$. Notez ensuite que$u_{n+1} = k_n + \frac{k_n}{2}$, donc $k_n$ doit être étrange pour tous $n$. Laissez écrire$k_n = 2 h_n +1$, ensuite $u_n = 2h_n+1+\frac{1}{2}$ (avec $h_n \ge 1$) et $u_{n+1} = 3h_n+1+\frac{1}{2}$. Il s'ensuit que$2h_{n+1} = 3h_n$, et donc $h_n = (\frac{3}{2})^nh_0$, ce qui implique que $2^n$ se divise $h_0$ pour tous $n$, contradiction. $\square$

Pour $u_0=\frac{11}{5}$, ensuite $$(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).$$ Voici une image de la dynamique:

En considérant (par exemple) quand $u_0=\frac{15}{7}$ ci-dessous, on suppose que la preuve générale devrait être difficile. $(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)$

Pour $u_0=\frac{10307}{4513}=\frac{k_0}{q}$, la séquence $(\frac{k_n}{q})=(u_n)$ atteint un entier à $n=58254$. La séquence$(u_n)$ atteint un entier une fois $k_n \text{ mod } q=0$. Ci-dessous l'image pour$(n,k_n \text{ mod } q)$; cela semble complètement aléatoire. La probabilité pour$s$ entiers aléatoires entre $0$ et $q-1$ ne jamais être zéro, c'est $e^{-s/q}$ lorsque $q$ est assez grand.

Application à la théorie irrationnelle des nombres

Selon l'article mentionné ci-dessus, il y a une bijection entre l'ensemble des nombres$u_0 \ge 2$, et l'ensemble des séquences $(a_n)$ tel que pour tous $n$:

$a_n \in \mathbb{N}_{\ge 2}$,

$a_n \le a_{n+1} < 2a_n$.

La bijection est donnée par: $$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}.$$Une réponse positive à la question fournirait une sorte d'alternative à la fraction continue , dans le sens d'une manière naturelle de représenter les nombres, avec une caractérisation complète des nombres irrationnels, ce qui serait ici$\lim_{n \to \infty} (a_n)=\infty$.

appendice

Dans la liste suivante, la donnée $[r,(p,q)]$ signifie que la séquence $(u_n)$, avec $u_0=\frac{p}{q}$, atteint un entier à $n=r$. La liste fournit les plus longs$r$ selon l'ordre lexicographique de $(p,q)$.

Calcul

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

Réponses

10 BenBurns Dec 03 2020 at 11:19

Je veux laisser quelques commentaires élémentaires, peut-être seront-ils utiles.

La question porte sur la relation de récurrence

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

Supposons que vous écriviez rationnel $u$ en termes de nombres naturels $\frac{pq+r}{p}$. Puis$\lfloor u \rfloor = q$. La relation de récurrence est maintenant

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

Par conséquent, nous pouvons étudier la même série en nombres naturels $u_{n+1}=q_n(r_n + p)$ demandant quand la série converge vers un multiple de $p$. Maintenant nous devons faire face$r_{n+1} = q_n * r_n \mod p$ et $q_{n+1} = \lfloor u_{n+1} / p\rfloor$mais laissez-moi vous montrer les avantages. Comparez d'abord à l'original$u_0 = 11/5$.

À présent $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\\ $$

La séquence continue indéfiniment une fois $r_n=0$.

Remarque mineure: $q_{n+1} \ge q_n$. Par définition,$q_{n+1} = \lfloor u_{n+1} / p\rfloor \rightarrow \lfloor q_n(r_n + p) / p\rfloor$.

Remarque mineure: il n'y a pas de cycles de longueur 1. Un cycle nécessiterait $q_{n+1}=q_n$ et $r_{n+1}=r_n$. Le même$q_{n+1}$ implique $q_n * r_n \lt p$. Et donc le seul moyen pour$r_{n+1} =r_n$ est si $q_n=1$, mais c'est obligatoire $q_n>2$ (par définition sur $u_0$).

Maintenant, une esquisse montrant que "beaucoup" $u_0$converger. Considérez quand$p=10$. La même logique s'appliquera aux autres$p$(premier et composite) mais l'analogie ici est la plus simple. Noter que$10=5*2$. Par conséquent, quand$u_n$ "étapes" dans les valeurs $50-59$, la moitié du temps (nombres pairs) l'étape suivante se terminera:

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

Ce sera également le cas pour les autres valeurs qui prennent en compte $5*m$ (pour $p=10$) tel que $150-159(=3*5), 250-259(=5*5)$ etc. Autre composite $2*p$ se comportent de la même manière, par exemple $p=14$ puis la moitié de $70-79$terminer en une seule étape. Cela peut être appliqué à des facteurs autres que$2$. En outre, cette idée de recherche de "zones de terminaison" s'applique également à un certain nombre de$u_n$ pour prime $p$, qui peut être facilement décidée comme se terminant dans le domaine de $p^2-p$. Par exemple, avec$p=5$, alors il y a une valeur $q_n=p-1$ et certaines $r$ tel que $p^2<u_n<p^2+p$; dans cet exemple,$q_n=4,r_n=2\rightarrow 4*(5+2)=28$ et la séquence se termine après $5*(5+3)$.

Il y a encore beaucoup d'autres cas à prouver, mais peut-être que cet article a été utile.

1 katago Dec 17 2020 at 18:48

$u_{0} \in \mathbb{Q} \quad u_{n+1}=\left[u_{n}\right]\left(u_{n}-\left[u_{n}\right]+1\right)$, ensuite $\{u_{n}\}_{n=1}^{+\infty}$ atteindre en entier. $\quad (*)$

Cela peut être prouvé si nous prouvons,

$p$ premier, $t\in \mathbb{N}^{*}$ $p^{t} u_{0} \in \mathbb{N}^{*}$, $\left\{u_{k}\right\}_{n=1}^{+\infty}$atteindre un entier. nous appelons cela une propriété$I(p,t)$.

Il est facile de vérifier si nous avons prouvé $I(p,t)$ $\forall t\in \mathbb{N}^{*}$. $\forall p$ premier, $I(p,t)$ est vrai alors nous avons prouvé $ (*)$.

Maintenant, nous nous concentrons sur un problème de résolution $I(p,t)$, $p$ prime et nous considérons d'abord le cas $t=1$.

On remet à l'échelle la séquence, on la dilate avec $p$, et toujours utiliser $u_k$ pour exprimer la nouvelle séquence et l'écrire dans $p$-expension.

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

puis la séquence satisfaite, $$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$

Où $a_k$ est le $k$-ème chiffre de $p$-expension de $u$ et $a_k(n)$ est le $k$-chiffre de $p$-expension de $u_n$, puis pour le précédent $a_k$ on a $a_k=a_k(0)$.

Remarque. Et en général, nous ne pouvons pas trouver la formule du terme général, (**) n'est vrai que pour les premiers chiffres de$u_k$, combien de chiffres peuvent impliquer en fonction de $u_0$, car nous devons éviter le report arithmétique.

ensuite $II(p, k)$ est la propriété suivante $$\left\{u_{n}\right\}_{n=1}^{+\infty}, \exists k\in \mathbb{N}^*, a_0(k)=0$$

Et il est facile de vérifier $II(p, k)$ est équivalent à $I(p, k)$, pour tous $p$ premier, $k\in \mathbb{N}^*$.

Pour $II(2, 1)$ nous avons de la chance que ce cas soit très spécial et peut être vérifié $II(2, 1)$ est vrai en vérifiant directement le premier $k$-chiffres dans le 2-expansion de $u_0$, c'est à dire $a_i(0)$, pour $0\leq i\leq k$.

Si les 2 premiers chiffres de $u_0$ sont 10, alors $II(2.1)$est vrai.
Si les 3 premiers chiffres de$u_0$ sont 101, alors $II(2.1)$est vrai.
Si les 4 premiers chiffres de$u_0$ sont 1001, alors $II(2.1)$ est vrai.
$......$
Si le premier $k$ chiffres de $u_0$ sont $1\underbrace{00...0}_{k-2}1$ , ensuite $II(2.1)$est vrai. Donc le seul cas$II(2.1)$ faux c'est quand $u_0=1$, qui correspond au cas de l'original $u_0$, $u_0=\frac{1}{2}$.