Bonjour,

Les indices dans ce genre d'exercices sont souvent très orientés et n'aident vraiment que ceux qui sont sur la même longueur d'onde . J'utiliserais plutôt , le reste est assez simple .

Imod

salut Sylvieg , est ce qu'on connait le terme initial Uo ?

Non, c'est un entier naturel non nul. On ne sait rien de plus.

La suite est bornée. Aucun terme ne peut dépasser u₀+a  ( ou 2a si u₀<a)
La suite étant bornée, il y a forcément au moins un terme par lequel elle passe une infinité de fois. (2 fois suffisent en fait) Et du coup, la suite est périodique.

D'accord ty59847
Utilises-tu l'inégalité de Imod, ou as-tu fait autrement ?

Non, je ne partais pas sur cette piste.

Peut-on caractériser les cycles?

Par exemple, il existe un seul cycle de longueur 2, un seul cycle de longueur 3 et un seul de longueur 4:
a -> 2a -> a
a/3 -> 4a/3 -> 2a/3 -> a/3
a/7 -> 8a/7 -> 4a/7 -> 2a/7 -> a/7

Bonjour,
Absent quelques jours,j'ai toujours du plaisir en rentrant

On remarque que si a=2 quel que soit le départ  on  n'a pas de cycle.

Fallait bien que je la fasse

Bonjour,

Je me décide à poster :

Tout entier naturel s'écrit sous la forme unique   où est un entier naturel éventuellement nul lorsque est impair et impair.
À partir de cette prémisse, j'étais persuadé d'aboutir.
Je n'y suis pas parvenu.

Bonjour,
Pas très disponible ces temps-ci, mais je regarde et réfléchis sur vos réponses
Je reprends l'idée de ty59847 en fusionnant les 2 cas dans cette inégalité :
u_n sup(a,u₀) + a .
Avec une démonstration par récurrence (un peu indélicate ? ) :

 Cliquez pour afficher

L'inégalité est vraie pour n = 0 et n=1.

Pour un n fixé entier supérieur ou égal à 1, on suppose que si m n alors
u_m sup(a,u₀) + a .

Si u_n est pair, on a u_n+1 = u_n / 2 ; donc u_n+1 u_n sup(a,u₀) + a .

Si u_n est impair, on a u_n+1 = u_n + a .
Mais un terme impair ne peut provenir que d'un terme pair. D'où
u_n = u_n-1 / 2 ( sup(a,u₀) +a ) / 2 ( sup(a,u₀) + sup(a,u₀) ) / 2 = sup(a,u₀)
D'où u_n+1 sup(a,u₀) + a .

@Sylvieg :

 Cliquez pour afficher

Indélicatesse : j'ai toujours trouvé ridicule la multiplication des blankés sur les questions ouvertes .

Bonsoir,
J'ai commencé à regarder les cycles.
Effectivement il n'y a qu'un type de cycle de longueur 2, de longueur 3, de longueur 4 (qui ne soit pas en fait de longueur 2).

Il y a un cycle trivial de longueur T en partant de a / (2^T-1-1) .
Avec a multiple impair de 2^T-1-1 .

Il y a deux types de cycles de longueur 5 : Le trivial et un autre.

C'est tout pour le moment

Pour les cycles j'ai regardé sous un autre angle en fixant a , il y a des choses amusantes à noter . On peut faire varier le premier terme de la suite dans l'intervalle [1,2a] et regarder la boucle finale . Je l'ai fait à la main pour les 8 premières valeurs de a , c'est en fait assez simple car on tombe assez vite sur les mêmes boucles .

En fonction de a donc :

Le nombre de boucles : 1 ; 2 ; 2 ; 3 ; 3 ; 2 ; 2 ; 5 .

Taille de la plus grande boucle : 2 ; 3 ; 6 ; 5 ; 9 ; 15 ; 18 ; 7 .

Choses curieuses à noter pour a donné :

Il n'y a deux boucles de la même taille .

Le cardinal de l'ensemble des valeurs prises par les boucles est exactement   .

Imod

Bonjour ,
J'ai testé au hasard:
u137 et a11
la boucle est 12  6  3  14  7  18  9  20  10  5  16  9  4  2  1 soit 15 valeurs
aurais-je compris que  3a+1/2=17 ??

Il faut que tu ajoutes la boucle de taille 2 : 11->22->11 pour obtenir le total de 17 .

Imod

Explication du décompte de (3a+1)/2 :
On a tous les nombres entre 1 et a,
plus les nombres pairs de a+1 jusqu'à 2a. (=les doubles des nombres entre (a+1)/2 et a )

En effet

En fait pour une même valeur de a , il peut y avoir plusieurs cycles de même taille et j'ai l'impression que pour une infinité d'entre elles il n'y a que 2 cycles :

Le cycle trivial : a -> 2a -> a

Et un autre : 1 -> a+1 -> (a+1)/2 -> ... -> ... -> 1 .

En tout cas c'est vrai pour a = 3 , 5 , 11 , 13 , 19 , ...

Imod

>Imod
Je te donne ma boucle ,pas vu 2 11 22 11

@Dpi

Je me suis mal expliqué , nous ne parlons pas de la même chose .

Pour a=11 , la plus grande boucle est de taille 15 comme sur ton exemple .

Mais il y a une deuxième boucle : 11 ->22 ->11 .

Il y a en tout 17 termes dans l'ensemble des boucles .

Imod

Bonjour,
@Imod,

Bonjour,
Je viens de comprendre :
La boucle générale  B1  fait place à  B2   =(a,2a,a ) quand  u=ka
et il semblerait à une troisième  boucle B3 quand  a=k u  avec  k>1.
  

Tu as bien compris Sylvieg , je mettais rendu compte de mon erreur et j'avais corrigé au message suivant

Un autre exemple , pour a=17 , il y a deux boucles de taille 12 .

Imod

D'accord, tu t'étais rendu compte
Mais dans

J'aurais mieux fait de réaliser un tableau à la Dpi , ça aurait été plus clair .

La première ligne représente le nombre de boucles quand a = 1 , 3 , 5 , ...

La deuxième ligne la taille de la plus grande boucle , toujours pour a= 1 , 3 , 5 , ...

Une chose amusante , quand a = 15 , la taille des boucles est : 2 , 3 , 5 , 6 , 7 . Il ne manque que le 4 pour faire carton plein .

Imod

Merci.
J'ai continué dans mon optique (ou plutôt celle de LittleFox) :
Il y a deux types de cycles de longueur 6 : Le trivial et un autre.
Idem pour la longueur 7.

Bonsoir,
il me semble qu' Imod a énoncé une conjecture intéressante :

Citation :
Le cardinal de l'ensemble des valeurs prises par les boucles est exactement .

Pour préciser avec un exemple :
en partant de u₀=5 avec a=3 on ne repasse jamais par la valeur 5 qui n'est donc pas dans une boucle.
Comment montrer que l'on ne peut pas avoir un phénomène de ce genre pour une valeur de u₀ inférieure à a ?

Effectivement,
la 1ère implication est assez évidente à démontrer :  si n est dans une boucle alors n est dans la liste des (3a+1)/2 valeurs détectées
Mais l'implication réciproque n'est pas aussi évidente : si n est dans cette liste des (3a+1)/2 valeurs, alors est-il dans une boucle ?  

On peut s'intéresser à une suite compressée :
U₀ quelconque ... mais on va se limiter aux U₀ inférieurs à a
U_n+1 = U_n/2 si U_n est pair et U_n+1=(U_n+a)/2 si U_n impair.

On a donc une suite avec des termes tous entre 1 et a-1.
Et on a même une structure parfaitement symétrique :
on a les 2 bornes 0 et a , on va noter ces 2 bornes b₁ et b₂ pour mettre en avant cette symétrie. b₁ et b₂ ne sont pas de même parité.
U_n+1 =( U_n+ b₁)/2 ou U_n+1 =(U_n+b₂)/2,  sachant qu'on choisi soit b₁, soit b₂, on choisit celui qui est de même parité que U_n.

Cette présentation un peu différente donne une autre vision, mais ça ne prouve toujours pas que tout élément de l'intervalle ]b₁, b₂[ serait dans une boucle.

Donc, suite du précédent message, en regardant toujours la suite compressée, où tous les termes sont dans l'intervalle ]b₁,b₂[, on a une certaine fonction f, celle définie par U_n+1 = f(U_n)
Cette fonction est une bijection (je l'affirme, c'est un peu court, il faudrait certainement mieux argumenter ce point).
Si on note g la bijection inverse, g est définie par :
g(x) = b₁ + 2 (x-b₁) si ce nombre est dans l'intervalle ]b₁,b₂[ (c.a.d si x est plus proche de b₁ que de b₂)

g(x) = b₂ + 2 (x-b₂) si ce nombre est dans l'intervalle ]b₁,b₂[ (c.a.d si x est plus proche de b₂ que de b₁)


Quelque soit le point de départ U₀, on sait que la suite va boucler à partir d'un certain élément.
Supposons que U₀ ne soit pas dans cette boucle, et soit p l'indice du premier élément qui est dans cette boucle.
Du coup U_p aurait 2 antécédents par la fonction f : un des antécédents est U_p-1, qui n'est pas dans la boucle, et l'autre est dans la boucle.
Et c'est contradictoire avec le résultat : f est une bijection.
Donc U₀ est nécessairement dans la boucle 'finale'.
Cqfd

>ty59847
Il me semble que est dans la boucle que si  est a+1

Je regardais une suite légèrement différente de la suite initiale, celle que j'ai appelée la suite 'compressée' .
Je l'ai définie de [0,a-1] vers [0, a-1], mais on pourrait l'étendre au point a, et donc la définir de [1,a] vers[1,a]

@LittleFox,
Impossible de remettre la main sur ce que j'ai fait pour la longueur 7
En fait, il est vraisemblable que je ne l'avais pas traité.
J'étais tombée sur 5a/31 avec le cycle a22a222 en travaillant sur la longueur 6. Ça, j'en ai la trace.
Je l'aurais recopié sur une feuille résumé avec le trivial a/63 ; et quand j'ai repris mes notes quelques jours après, j'ai sans doute cru que j'avais terminé la longueur 7.

Pour compenser, je donne les deux de longueur 5 et 6.
Longueur 5 : En partant du trivial a/15 avec le cycle a2222 , et de 3a/7 avec le cycle a2a22 .
Longueur 6 : En partant du trivial a/63 avec le cycle a22222 , et de a/5 avec le cycle a2a222 .

J'aime bien ta notation pour décrire les cycles, et merci pour le lien

Salut.
Je veux surtout dire merci à ty59847.

L'approche de LittleFox me semble très intéressante, mais j'ai continué sur la piste d'Imod.
Il est clair que si a est un multiple de b et que b présente un cycle de longueur k alors a présente un cycle de longueur k.
Mais les cycles obtenus à partir d'un nombre donné ( même premier ) semblent quand même assez imprévisibles.
Par exemple
en prenant a=41 on a deux cycles de longueur 30 et un de longueur 2 ;
en prenant a=43 on a trois cycles de longueur 21 et un de longueur 2 ;
en prenant a=47 on a trois cycles de longueurs respectives 32, 37 et 2.

On reprend tout et on combine tout

Je reprend la notation compressée de ty59847:
Si au lieu des opérations x -> x+a et x -> x/2, on prend les opérations x -> (x + a)/2 et x -> (x+0)/2, tout cycle du premier système s'écrit dans le second et vis-versa.
Dans le second, il est évident que tout x dans [1, a] restera dans [1, a] et que tout x > a mènera à un x inférieur et donc il ne peut y avoir de cycle que dans [1,a] et il y a au moins un cycle.

On peut montrer comme Imod le fait remarquer que le cardinal est (3a+1)/2 pour le premier système en montrant qu'il est a pour le second.
En effet, tout x dans [1,a] a un (et un seul) prédécesseur dans [1,a]: Soit x est plus grand que a/2 et 2x-a est dans [1, a]. Soit 2x est dans [1,a] (Et jamais les deux en même temps).

On peut changer ma notation en la compressant en remplaçant 'a2' par '1' et '2' par '0'.
On peut trouver une belle relation pour tout x qui est départ d'un cycle de longueur n.

Regardons le cycle a22a2a2a2a2a22a222222 de longueur 21 pour a=43.
En notation compressée, ça donne 10111110100000. On a :
x -10111110100000-> x
x -1011111010000-> 2x
...
x -101111101-> 32x
x -10111110-> 64x-a
x -1011111-> 128x-2a
x -101111-> 256x-5a
...
x --> 2¹⁴x-381a
=> x = 381a/(2¹⁴-1) => x = a/43

On retrouve le 2^T-1-1 de Sylvieg ou presque. En effet, on a nécessairement une relation de la forme x = 2^Tx - Ka.

On peut voir aussi que 10111110100000 est la notation inversée en binaire de 381 (10111101).
On peut voir aussi que les deux autres séquences (qui commencent par 3 et 7) correspondent à l'inverse de la notation en binaire sur 14 bits de 3(2¹⁴-1)/43 = 1143 (00010001110111) et 7(2¹⁴-1)/43 = 2667 (00101001101011).

Et ça, ça n'est pas une coïncidence
Pourquoi une longueur de 14? Parce que 2¹⁴ est la plus petite puissance de 2 qui laisse un reste de 1 lors de la division par 43.

Dans le premier système, la longueur du cycle est cette puissance plus le nombre de 1 dans la notation du quotient. Ce qui est un peu plus variable.

Je trouve ça pas mal comme résultats

Ça m'a l'air très intéressant
Mais je ne suis pas sur de tout bien comprendre.
Je regarderais précisément plus tard, et j'essayerais d'autres exemples.

En tous cas merci beaucoup

Continuons à 'prendre du recul'.

On a notre suite compressée ... de [1,a] vers [1,a].  Et on a une parfaite symétrie : 4 donne 2, qui donne 1, et de la même façon, a-4 donne a-2, puis a-1  

a est impair, donc a est de la forme 2k+1.
Et donc on peut s'intéresser à une autre suite, définie sur [-k,k]
Si x est pair, g(x)=x/2, sinon g(x)= (x-2k-1)/2.
En particulier g(0)=0

Cette nouvelle suite est la copie exacte de la suite étudiée. Mais on voit mieux la symétrie. On a juste  recodé les nombres entre (a+1)/2 et a-1 ,
(a+1)/2 devient -k,
...
a-2 devient -2
a-1 devient -1
et a devient 0.  

Correctif/complément

Continuons à 'prendre du recul'.

On a notre suite compressée ... de [1,a] vers [1,a].  Et on a une parfaite symétrie : 4 donne 2, qui donne 1, et de la même façon, a-4 donne a-2, puis a-1  

a est impair, donc a est de la forme 2k+1.
Et donc on peut s'intéresser à une autre suite, définie sur [-k,k]
Si x est pair, g(x)=x/2,
sinon si x est positif : g(x)= (x-2k-1)/2, et si x est négatif, g(x)=(x+2k+1)/2
n particulier g(0)=0

Cette nouvelle suite est la copie exacte de la suite étudiée. Mais on voit mieux la symétrie. On a juste  recodé les nombres entre (a+1)/2 et a-1 ,
(a+1)/2 devient -k,
...
a-2 devient -2
a-1 devient -1
et a devient 0.

Et comme g est une bijection, et que les divisions, c'est embétant, on peut s'intéresser à la bijection inverse, notée h :
h(x)=2x si 2x est dans l'intervalle [-k,k]
h(x)=2x+2k+1 si 2x n'est pas dans l'intervalle [-k,k], et x négatif
h(x)=2x-(2k+1) si 2x n'est pas dans l'intervalle [-k,k], et x positif


  

J'aime bien l'idée d'utiliser la bijection inverse.
Au final on a juste une multiplication par 2 modulo a.

Effectivement, multiplication par 2 modulo a, c'est une formulation plus concise, et ça doit renvoyer vers des théories connues.

J'ai fait quelques tests, avec la dernière formulation ( intervalle [-k,k] ...)
Résultat n°1 : les boucles ont toutes la même longueur , avec un petit arrangement : Par exemple, pour k=101 (ou a=203 avec l'autre notation), les boucles ont une longueur de 84,  ou un diviseur de 84
Résultat n°2 : dans chaque boucle, la somme des termes donne systématiquement 0 !

C'est un constat expérimental, ce n'est pas démontré.

Oui , avec la fonction g : x -> 2x on rentre dans la théorie classique des anneaux . Trouver la taille des boucles réduites revient à déterminer l'ordre de 2 dans le groupe multiplicatif

La somme nulle sur les cycles de ty59847 se justifie instantanément en remarquant que si 2 est d'ordre k et alors .

Imod

Il n'y a pas de formule fermée donnant l'ordre de 2 dans ces groupes . Il faut voir en plus que la taille des boucles de cette fontion n'est pas réellement celle de la fonction initiale mais on doit pouvoir trouver le nombre de boucles et dans certains cas particuliers la taille de chacune d'entre elles . Mais là , c'est une autre histoire

Imod

Merci à Sylvieg pour la question, merci à chaque intervenant qui a amené se pierre à l'édifice. Je ne sais pas si on a fait le tour de la question, mais j'ai vraiment apprécié ce petit travail d'équipe

Même si on ne pourra jamais dévisser complètement le problème , on peut en extraire quelques énigmes amusantes

est choisi au hasard dans un intervalle [[0,M]] avec M très grand . Quelle est la plus petite valeur de a pour laquelle la suite   a moins d'une chance sur 1000 de ne jamais passer par 1 ?

Imod

PS : le travail collaboratif , je n'aime que ça

Salut Imod.
Pour ton énigme, si on prend a=32 767 on a moins d'une chance sur 1000 de tomber sur 1.
Je soupçonne que c'est la plus petite valeur qui convient.