Une drôle de suite convergente
dans Arithmétique
On considère deux entiers $a$ et $b$ premiers entre eux non nuls.
On note $(i)_j$ le reste de la division euclidienne de $i$ par $j$.
Soit la suite $U_k$ définie par $U_0>ab$ et $U_{k+1}=U_k-(U_k)_a-(U_k)_b$
Démontrer que la suite $U_k$ est constante à partir d'un certain rang.
Amusez-vous bien,
Al-Kashi
On note $(i)_j$ le reste de la division euclidienne de $i$ par $j$.
Soit la suite $U_k$ définie par $U_0>ab$ et $U_{k+1}=U_k-(U_k)_a-(U_k)_b$
Démontrer que la suite $U_k$ est constante à partir d'un certain rang.
Amusez-vous bien,
Al-Kashi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
On peut établir que la plus longue somme des restes, qui est équivalente donc au nombre de départ, vaut :
2ab - 2b - a + b[a].......................... si a < b.
Donc bien < 2ab.
Mais c'est long à décrire......
Lui ôter ses restes donne :
x1 = x0 - (x0 + y0) = - y0 [ a ]
y1 = y0 - (x0 + y0) = - x0 [ b ]
(x1 [ a ] , y1 [ b ] ) = ( -y0 [ a ], -x0[ b ] )
x1 ne dépend que de y0 alors que y1 ne dépend que de x0.
Intéressons nous à la suite : x0, y1, x2, y3, ...
x0........y1.........x2
0........b(0).........r.......................r est l'opposé de b[ a ]
1........b-1.........r+1
2........b-2.........r+2
...
r.........b-r.........r + r = 2r
La sous-suite x0, x2, x4 est donc une suite arithmétique de raison r [ a ]. Elle aboutit à 0 puisque b premier avec a, donc r premier avec a.
La sous-suite y1, y3, y5 est aussi une suite arithmétique de raison -r [ b ]. Elle aboutit aussi à 0 pour la même raison.
En partant du couple (r, b-r) on aboutit à 0 par une chaîne unique qui contient toutes les valeurs x modulo a et toutes les valeurs y modulo b > b-a.
Exemple avec a = 7 et b = 19
r = 7 - reste (19 / 7) = 2
Chaîne complète : 2 , 17, 4 , 15 , 6 , 13 , 1 , 18 , 3 , 16 , 5 , 14 , 0 .
Pour l'autre suite : y0, x1, y2, x3, ...on a évidemment la même chaîne que précédemment, la seule distinction est qu'elle commence par un nombre y [ b ] au lieu de x [ a ].
Nota : le y0 d'origine peut prendre une valeur < = b-a, mais tous les y suivants reprendront une valeur > b-a.
Un couple (x0, y0) est donc une superposition de 2 fois la même chaîne dont seules les valeurs initiales sont variables.
Pour suivre notre exemple (x0, y0 ) = ( 6 , 15 ) se modélise ainsi :
6 , 13 , 1 , 18 , 3 , 16 , 5 , 14 , 0 . 0
15 , 6 , 13 , 1 , 18 , 3 , 16 , 5 , 14 , 0 .
Et le nombre le plus grand : (2 , 17 )
2 , 17, 4 , 15 , 6 , 13 , 1 , 18 , 3 , 16 , 5 , 14 , 0
17, 4 , 15 , 6 , 13 , 1 , 18 , 3 , 16 , 5 , 14 , 0 . 0
Les nombres initiaux, concrètement, se calculent tout simplement en sommant la somme des nombres des 2 chaines, puisque ce sont les restes successifs et qu'on aboutit à 0.
Le nombre le plus long se calcule facilement, d'une manière générale, en sommant 2 fois les nombres de b-1 à b-a+1 et de 1 à a, auquel on ôtera r.
Nmax = (a-1) 2b - r < 2ab.
Ce qui répond à la question posée.
Je donnerai une preuve assez simple à comprendre dans quelques jours si personne ne trouve entre temps.
Al-Kashi
Il y a par exemple cet argument.
Je suppose $a<b$ et je note: $\forall n \in \N$, $a_n$ et $b_n$ les restes respectifs de la division de $U_n$ par $a$ et $b$.
Il faut prouver : $\exists N\in \N$ tel que $a_N=b_N=0$
Prouvons d'abord: $\boxed{\forall n \in \N, a_n \neq 0 \implies a_{n+2} \equiv a_n-b \mod a} \:\:\:\:(\star)$
En effet: Soit $n$ fixé tel que $a_n \neq0$. On a: $ b_{n+1} \equiv U_{n+1} \equiv (U_n -b_n) -a_n \equiv - a_n\mod b\:$ et $\:\:\:-b< -a<-a_n<0 $. Il en résulte $b_{n+1} = -a_n +b$. On déduit alors: $ a_{n+2} \equiv U_{n+2} \equiv ( U_{n+1} -a_{n+1}) - b_{n+1} \equiv - (-a_n +b) \mod a\:\:\square$
Désignons par $q$ le plus petit entier naturel tel que $a_0 \equiv qb \mod a$. ( $q$ existe car $a\wedge b =1$) . Alors , en appliquant $q$ fois $(\star)$, on obtient $a_{2q}\equiv 0 \mod a,\:\:$ c'est à dire $a_{2q} = 0$
Donc $\exists k \in N$ tel que $a_k =0$. . Il est alors facile de voir que: $\forall n \in N,\:\: b_{k +2n
+1}=0$
En appliquant à nouveau $(\star)$,on obtient : $\forall n \in \N ,\:a_{k+2n+1} \neq 0 \implies a_{k+2n+3}\equiv a_{k+2n+1} - b \mod a$, puis comme précédemment, on déduit que: $\exists r \in \N$ tel que $a_{k+2r+1}= 0$
En notant $N= k+2r+1$, on a bien: $a_N =b_N =0 \:\: \square$
Concernant ta première étape, je suis d'accord avec l'ensemble du raisonnement mais celui-ci tient à la première congruence $b_{n+1}\equiv U_{n+1}$ modulo $b$ que je ne comprends pas.
Sauf erreur de ma part il me semble que c'est plutôt $a_{n+1}\equiv U_{n+1}$, non ?
Al-Kashi
Al-Kashi
Cela est très élégant en tout cas(tu).
Al-Kashi
Merci pour ta participation,
Al-Kashi
Plus rien à dire vraiment ? J'ai quand même envie de poser quelques questions.
0. D'où sort cette suite $(U_k)_{k \ge 0}$ ? Faut-il se contenter de résoudre des exercices sans savoir ce qu'il y a dessous ? Mais peut-être qu'une personne de bon matin, après le café, s'est dit : tiens, je vais prendre $a, b$ premiers entre eux, et construire la suite $(U_k)_{k \ge 0}$ ... etc... Allons, allons.
1. Et si la contrainte initiale $U_0 > ab$ en fait n'était pas la bonne ? Je veux dire : est ce que la clause $U_0 \ge 2g$ ne suffirait pas où $g$ est le genre du semi-groupe $a\N + b\N$. I.e. $g = (a-1)(b-1)/2$ le nombre de gaps i.e. le cardinal de $\N \setminus (a\N + b\N)$. De sorte que $2g-1$ est le plus grand gap et $[2g .. \infty[ \subset a\N + b\N$.
2. Est ce que par hasard (sic) la suite $U_k$ ne resterait pas dans le semi-groupe $a\N + b\N$ (en étant décroissante) ?
3. Et la valeur stationnaire, en partant de $U_0$, c'est dans les combiens ?
4. J'en ai d'autres. Mais peut-être que se poser des questions, ce n'est pas la mode.
Bienvenue tout d'abord.
Je n'ai pas dit que je n'avais plus rien à dire du problème posé.
J'ai dit que je n'avais plus rien à redire sur la preuve de Lou16.
Je te rassure tu es sur la bonne voie, ce problème à son origine dans.....mais je laisse le temps au lecteur.
Et il y aura pas mal de choses qui devraient t'intéresser.
Plus précisément je peux répondre à tes 4 questions.
Al-Kashi
Sur la bonne voie ? Mais cela ne m'intéresse absolument pas. De mon côté, je ne cache JAMAIS ce que j'estime être ``une certaine vérité''. C'est tellement dur de comprendre même en ayant l'origine de la chose. Et pourquoi as tu remplacé la borne $2g$ par la borne $ab + 1$ ?
En effet, l'algo proposé est bien plus intéressant que la question qu' Al Kashi lui a attachée.
Sinon, non, Claude, U0 > (a-1)(b-1) n'est pas suffisant.
J'ai écrit dans ma réponse que U0 max, à partir d'un (a,b) donné, a < b , valait : ........ (a-1)2b - r avec r = a - b[a].
Si tu choisis par exemple Uo max - ab, tu vas avoir des problèmes en tombant sur des nombres négatifs.
Mais je reste très surpris par les propriétés de cet algorithme curieux. D'où vient ta question, Al Kashi ?
En parlant du nombre de Frobénius, je pense que la recherche de beaucoup aurait été ciblée sur les semi-groupes et je voulais que le problème soit plus ouvert.
@Nogdim:
La condition proposée par Claude est correcte. Je répondrais à toutes les questions prochainement.Je reste curieux de voir si d'autres approches sont proposées.
@Claude et @Nogdim:
Pour joindre les deux, remarquons que Lou16, que je remercie, dans sa preuve ne fait aucune hypothèse sur $U_0$ alors que me concernant ma preuve nécessite une contrainte la dessus. Cela montre que le fait d'ouvrir le problème amène parfois des résultats en plus.
Al-Kashi
@Al-Kashi : nombre de Frobenius, comme tu y vas fort. Effectivement, si tu mets d'abord ce terme sur le tapis, cela glace le sang. Est ce vraiment utile d'en parler pour $a\N + b\N$ ? Moi je prétends que non, je prétends que l'on peut dire des choses élémentaires et pertinentes sur ce semi-groupe, en particulier sur ce que l'on appelle la symétrie (et que l'on peut expliquer à un enfant si on prépare son coup, que je dis).
Même si j'ai dit que cela ne m'intéresse pas (enfin, ce qui ne m'intéresse pas c'est que l'on cache les objets structurels), j'avais bien vu que LOU16 n'utilisait pas la clause $u_0 > ab$. Il aurait pu se tromper ? Hum, je ne crois pas, disons que j'ai une très grande confiance en lui. Mais, mais, il est parfois euh .. un peu compact. Je dis bien compact et pas cachotier.
Bref, j'ai besoin de dégager le structurel (ici mon premier semi-groupe de quand j'étais petit).
Voilà ce que j'en dis : en données, $a, b \in \N$ avec $a\wedge b = 1$, $u_0 \in \Z$ (carrément, finie la période timorée $u_0 \ge 2g = (a-1)(b-1)$) et la suite $(u_k)_{k \ge 0}$ définie par $u_{k+1} = u_k - (u_k \bmod a) - (u_k \bmod b)$. Alors
1. La suite (d'entiers) $(u_k)_{k \ge 0}$ est décroissante (évident) et minorée (cela se mérite). Donc stationnaire. Je note $u_\infty$ cette valeur stationnaire ; c'est un entier de $\Z$ (pour éviter de confondre avec entier de $\N$).
2. L'entier $u_\infty$ est multiple de $ab$ (facile, voir évident car $u_{k+1} = u_k$ si et seulement si $a \mid u_k$ et $b \mid u_k$).
3. Cet entier $u_\infty$ se détermine comme suit à partir de $u_0$. On effectue la division euclidienne de $u_0$ par $ab$ : $u_0 = qab + r$ avec $q \in \Z$ et $0 \le r < ab$ (une division euclidienne, quoi). Alors :
$$
{u_\infty \over ab} = \cases {q &si $r \in a\N + b\N$ \cr q-1 &sinon}
$$
D'accord avec tes 3 points.
Al-Kashi
Je résume comment je vois les choses (sans dévoiler le pot aux roses puisque tu le souhaites pas). Au départ $a, b \in \N$ premiers entre eux. Ceci permet de définir une certaine fonction $f_{a,b} : \Z \to \Z$ : c'est celle qui réalise $f_{a,b}(u_0) = {u_\infty \over ab}$ où $u_\infty$ est la valeur stationnaire de la suite $(u_k)_{k \ge 0}$ définie par récurrence $u_{k+1} = u_k - (u_k \bmod a) - (u_k \bmod b)$.
Ce que j'ai établi dans mon dernier post, je l'ai établi sans connaître cette fonction $f_{a,b}$. Seulement en utilisant la relation de récurrence et quelques propriétés de $a\N + b\N$. Avec cependant une certaine insatisfaction de ne pas savoir la vraie vérité sur $f_{a,b}$. En me doutant bien que toi, tu étais parti de $f_{a,b}$, qui mesure quelque chose de tangible (mais non, je ne dirais pas) du type $f_{a,b}(n) = \text {le nombre de ..}$ pour $n \in \N$. Et que tu as établi ensuite la relation de récurrence. Enfin, quelque chose de cette nature là, je ne veux pas jouer les devins.
Et en prenant un peu de temps, j'ai fini par mettre la main sur le truc (d'ailleurs, j'aurais pu trouver plus tôt).
Voilà, voilà. Est ce que certaines personnes vont participer ? Je n'en sais rien.
Tu as bien résumé l'histoire.
Bon, si j'ai le temps ce soir, je dévoilerais le pot aux roses:-D
Al-Kashi
Je pense que la démo de @LOU16, n'est pas valable. La relation qu'il encadre et l'équivalence entre $b_{n+1}$ et $U_{n+1}$, n'est pas évidente si elle est vraie.
Il me semble que la question a été répondue.
Peut être s'agit-il maintenant d'établir la relation entre cette suite et aN + bN ?
L'équivalence est immédiate par définition même de $b_{n+1} $.
$Nodgim
Oui
Al-Kashi
Soit n = a * k + b * j, avec a < b.
On pose b = r [a] ce qui donne U0(n) = jr [a]
Comme c*b < n < (c+1) * b avec c > j (si a k > b). Et c*b = c * r [a]
Chaque itération consiste à ôter les restes de " b " et " a " et conduit à toujours décrémenter d'une unité le multiple de b.
Modulo " a ", ça donne ceci :
U0 = j*r
U1 = c*r - j*r = ( c- j )* r
U2 = (c-1) * r - (c-j) * r = (j-1) * r
U3 = (c-2) * r - (j-1) * r = (c - j - 1 ) * r
Les U pairs sont décrémentés de 1 à chaque étape, Idem les U impairs.
Le plus petit des 2, entre j et c-j, arrivera à 0 forcément avant épuisement de c, car j+(c-j) = c donc l'un est < = c / 2.
Or lorsque l'un des restes de " a " ou " b " est nul, on aboutit forcément à 0 [ab].
A contrario, si " n " ne peut s'écrire de la forme " a * k + b * j " , la même démarche que précédemment conduit à avoir U0 = j*r + s, un " s " qui persiste à chaque étape.
Lemme :
Soit $n$ un nombre entier.
Les équations $ax+by=n $ $(1)$ et $ai+bj=n-(n)_a-(n)_b$ $(2)$ ont le même nombre de solutions.
Preuve:
Si $ax+by=n$ alors nécessairement $x\le\lfloor\dfrac{n}{a}\rfloor$ et $y\le\lfloor\dfrac{n}{b}\rfloor$
Posons $i=\lfloor\dfrac{n}{a}\rfloor-x$ et $j=\lfloor\dfrac{n}{b}\rfloor-y$
On obtient alors $ai+bj=n-(n)_a-(n)_b$ .On prouve alors qu'il y a une bijection entre les solutions de $(1)$ et $(2)$.
A partir de ce Lemme , on peut alors obtenir de nombreuses propriétés curieuses et en grande partie citées par Claude.
Ainsi la suite que je vous ai proposée conserve le nombre de solutions.
Al-Kashi
Al-Kashi
Indépendamment de cette relation, je vais poser une question pas simple, plus directement en rapport avec cette curieuse suite : Pour un triplet donné (n,a,b) combien de fois peut-on remonter la suite en sens inverse ?
A faire à la main bien entendu.
En lisant le message de Claude, je suis convaincu, comme il le dit, qu'il a trouvé ce fameux truc.
Concernant ta question, on ne peut pas remonter la suite au delà de $2ab$ termes car ma suite $U_k$ comme je l'ai dit à cette élégante propriété de conserver le nombre de solutions
Al-Kashi
Al-Kashi
Je reformule ma question.
Soit un triplet (n,a,b), a et b premiers entre eux.
De combien de termes MAX exactement peut on remonter la suite décrite dans cet énoncé ?
Par exemple, avec le triplet (522,19,31) combien peut-on remonter de termes la suite ?
Tu as la réponse à ta question ?
Je la trouve intéressante.
Al-Kashi
Je vous laisse réfléchir, ce n'est pas pressé.
Il y a un souci sur ta question.
La suite est parfaitement définie dans le sens que j'ai proposée. Par contre si on cherche à aller dans le sens inverse il y a plusieurs chemins.
À titre d'exemple:
$a=5$ et $b=6$
$11/5/0$
$12/10/6/5/0$
Ainsi en partant de $0$ il y a plusieurs chemins.
Il faudrait donc apporter une précision sur ta question.
Parles-tu du maximum de termes ?
Al-Kashi
Ta 1ère réponse donnait un max large, ce n'est pas du tout ce que je voulais. J'ai donc corrigé la formulation en oubliant au passage de rappeler MAX.
Pour les 2 cas que tu cites :
- Tu peux remonter 7 termes à partir de 11, le premier valant 49.
- Tu peux remonter 5 termes à partir de 12, le premier valant 37.
La valeur du 1er terme est également accessible, même pour des grands nombres, mais il faut du calcul en plus, même si ça reste dans le possible en manuel.
J'ai pu par exemple, à partir du triplet (1000,29,41) trouvé qu'on pouvait remonter la suite de 20 termes, le 1er valant 1816.
Gros indice, la solution est implicitement contenue dans ma toute première réponse, plutôt ignorée. Cela dit, d'autres approches sont sans doute possibles.
Je suis probablement le seul à m'interroger et donc ce n'est pas très grave. Oui, au bout d'un certain temps, j'avais fini par comprendre qu'intervenait pour $a,b \in \N$ fixés premiers entre eux, la fonction $\N\ni n \mapsto \#\{(x,y) \in \N \times \N \mid ax + by = n\}$, fait masqué initialement par l'auteur.
Et l'auteur fournit le pot aux roses in http://www.les-mathematiques.net/phorum/read.php?5,1739178,1741860#msg-1741860. Dans une première version, il y avait une définition erronée de $j$ (cela se voit tout de suite). J'en ai déduit que soit personne ne lisait en détail les posts en ou bien tout le monde rectifiait le truc. La définition de $j$ a été corrigée depuis.
Ce qui m'étonne un peu/beaucoup. Un lemme est énoncé (bien sûr, il faut y comprendre que $x,y, i,j$ sont dans $\N$, mais on s'en doute un peu).
Ensuite, vient le mot preuve. Dans laquelle quelque chose (de facile disons) est amorcé. Mais cette ``preuve'' se termine par ``On prouve alors''. Quel est le statut d'une preuve dans laquelle figure ``On prouve alors'' ?
Que faut-il en penser ? Que le ``On prouve alors'' est une évidence ? Mais si c'est une évidence, pourquoi ne pas donner les détails puisqu'en un premier temps $(i,j)$ a été fourni en fonction de $(x,y)$ ? Ou alors, ce n'est pas si évident que cela et l'auteur ne veut pas rentrer trop dedans (ce que je peux comprendre).
En effet j'avais corrigé l'erreur en me relisant en $j$ et je pense que beaucoup ont du la corriger instantanément sans me le dire.
Concernant la preuve, en effet je n'ai pas tout détaillé, mais si des précisions sont nécessaires je veux bien y répondre.
Al-Kashi
Si n est de la forme aN+bN cela implique que tous les nombres qui suivent dans la suite le sont aussi. Là c'est OK.
Maintenant, un nombre qui est hors format aN + bN ne peut il être dans une suite qui arrivera à 0 [ab] ?
Pour être sûr de la bijection, il faut le prouver.
Il y a donc bien bijection des solutions.
Al-Kashi
Dans http://www.les-mathematiques.net/phorum/read.php?5,1739178,1740636#msg-1740636 Etrange. L'auteur dispose d'une preuve de ``l'invariance'' et fait tout de même l'hypothèse $U_0 > ab$. Je m'interroge.
J'ai prouvé que ma suite conserve le nombre de solutions.
Lorsque j'ai posé mon problème j'ai émis l'hypothèse que $U_0>ab$ car c'est grâce à celle ci que je m'assure qu'il y a au moins une solution et ainsi la suite ne peut pas aller sous $0$..
Sans cette hypothèse je ne savais pas si la suite était stationnaire ou non, mais Lou16 a apporté un complément la dessus grâce à sa preuve.
Je ne vois vraiment pas sur quoi tu t'interroges.
Al-Kashi
Je suis convaincu, je n'avais émis une réserve que pour la forme, que pour voir écrit que la propriété marche également à reculons. Il y a bien bijection.
La suite proposée par @Babsgueye est constante et vaut $b$.
Al-Kashi
Tu pourrais nous expliquer comment tu obtiens le nombre maximum de termes avant une valeur $n$ donnée pour cette suite.
Al-Kashi
Pour comprendre comment je fais, il est nécessaire de comprendre ce que j'ai écrit au 2ème message de ce fil http://www.les-mathematiques.net/phorum/read.php?5,1739178,1740034#msg-1740034 .
Comme je ne sais pas ce qui bute dans la compréhension de ce qu'il y est écrit, je ne peux pas vraiment aller plus loin. Une fois ce message compris, ce sera presque terminé pour l'explication.
[Ajout du lien. :-) AD]