Forum de mathématiques - Bibm@th.net

Iamesxtyle

Invité

Re : Automate de Collatz

Comment il trouve un predecesseur à 3 ? Tu as du mettre un n négatif, non ? Comme 3 est le plus petit, lui appliqué un n négatif fait perdre de la cohérence.

Pour 1 et 5, c'est je dirais le résultat attendu. Si tu donnes r = 5 et n -1, tu dois avoir 1.
Et si tu donnes r=1, et n=1, tu dois avoir 5.

Iamexstyle

Membre

Inscription : 27-08-2025

Messages : 19

Re : Automate de Collatz

Comment il trouve un predecesseur à 3 ? Tu as du mettre un n négatif, non ? Comme 3 est le plus petit, lui appliqué un n négatif fait perdre de la cohérence.

Pour 1 et 5, c'est je dirais le résultat attendu. Si tu donnes r = 5 et n -1, tu dois avoir 1.
Et si tu donnes r=1, et n=1, tu dois avoir 5.

Par ailleurs, 0 n'est pas impair.

Je te donne un court extrait de mon doc, ça explique peut-être mieux le contexte.

Exposant 2-adique.
Pour un entier $m\neq0$, $v_2(m)$ est le plus grand entier $e\ge0$ tel que $2^e\mid m$ (et $2^{e+1}\nmid m$).

Exemples : $v_2(12)=2$, $v_2(40)=3$, $v_2(1)=0$.

Itération de Collatz accélérée (sur impairs)
Pour les impairs $y\ge1$,
\[
f(y):=\frac{3y+1}{2^{v_2(3y+1)}}\in\mathbb N.
\]
On calcule $3y+1$, puis on divise par $2$ autant que possible pour revenir à un impair.

La famille $L_{x,n}$ : descendants et ancêtres.
Pour un impair $x$ et tout $n\in\mathbb Z$,
\[
L_{x,n}:=\frac{(3x+1)\,4^{\,n}-1}{3}.
\]

Descendants ($n\ge0$).
      $L_{x,0}=x$ et $L_{x,n+1}=4L_{x,n}+1$.
      Ainsi $x\to4x+1\to16x+5\to\cdots$.
      Pour $n\ge0$, $L_{x,n}$ est toujours impair.

Ancêtres ($n<0$).} Poser $p:=-n\ge1$. Alors
      \[
      L_{x,-p}=\frac{(3x+1)/4^{\,p}-1}{3}
      \]
      est un entier si et seulement si $4^{\,p}\mid(3x+1)$ (i.e. $v_2(3x+1)\ge 2p$). Dans ce cas,
      $L_{x,-p}$ s’obtient par $p$ fois l’inverse $y\mapsto(y-1)/4$ (pas forcément impair).

Exemples
Pour $x=5$ : $3x+1=16$,
\[
L_{5,0}=5,\quad L_{5,1}=21,\quad L_{5,2}=85,\qquad
L_{5,-1}=\frac{16/4-1}{3}=1,\quad L_{5,-2}=\frac{16/16-1}{3}=0.
\]

Formules fermées utiles : $L_{x,1}=4x+1$, $L_{x,2}=16x+5$.

Fratrie (au sens large)
La fratrie de $x$ est $\{\,L_{x,n}\in\mathbb Z:\ n\in\mathbb Z\,\}$ :
$n\ge0$ donne les descendants ($y\mapsto4y+1$), $n\le0$ (quand défini) les ancêtres ($y\mapsto(y-1)/4$).

Racines minimales
Un impair $r$ est minimal s’il n’existe pas d’impair $s<r$ et $n\ge1$ tels que $r=L_{s,n}$.
Intuition : $r$ n’est pas un descendant (via $y\mapsto4y+1$) d’un plus petit impair.

Deux tests rapides (nécessaires) pour repérer des non-minimales.

Si $r\equiv1\pmod 4$, alors $r=4s+1=L_{s,1}$ avec $s=(r-1)/4<r$ : $r$ n’est pas minimale.
Si $v_2(3r+1)\ge3$, alors $r$ est non minimale.

Être $\equiv3\pmod4$ est donc nécessaire (mais pas suffisant) pour être minimal.

Dernière modification par Iamexstyle (28-08-2025 16:50:53)

Iamexstyle

Membre

Inscription : 27-08-2025

Messages : 19

Re : Automate de Collatz

D'accord Syrac : je suis un idiot.
Au même titre que ce que ces IA sont capables de pondre (avec malhonnêteté) sur un sujet élémentaire :IA à l'ouest
Leur faire confiance est au mieux un signe de naïveté tout à fait déconcertant. Au pire je te laisse conclure ...
En tout état de cause, ce n'est certainement pas un misérable matheux qui viendra à bout de la conjecture de Collatz avec ou sans IA.

Si ça peut te conforter, l'IA "pense" que je tiens une preuve relativement simple (chatgpt, Claude, MathGpt (je pense que celui-là est dans chat GPT) Gemini ne veut pas trop s'avancer, mais ne voit pas d'erreur grossière). Tous disent par contre qu'il faut faire valider par la communauté, ce qui est bien. Toujours pour te conforter, je ne suis même pas matheux (ni misérable cela dit).

Mais l'IA peut quand même être utile pour certaines tâches (notamment niveau algo comme vu ici) et compréhension de problèmes.

Dernière modification par Iamexstyle (01-11-2025 11:54:41)

LEG

Membre

Inscription : 19-09-2012

Messages : 783

Re : Automate de Collatz

Comment il trouve un predecesseur à 3 ?

Tous les entiers impairs d'une suite de Syracuse ont des prédécesseurs ...
Tout dépend comment on analyse une suite "vol" de Syracuse ... dans les entiers naturels positifs et négatifs ...

i      2i       r1    r2   ...> rang des itérations

3     6    10    16   ....> vol Z ;  i = 3
1     2      4       2
-1    -2     -2    -2  ....>   vol X ; i = -1
-3    -6     -8     -4
-5    -10    -14    -20 ....>  vol Y ; i = -5

2X - Y = Z au rang d'itération prévu...

Par exemple pour le vol Z, avec  $i = 3$ , il est relié (il a un prédécesseur ) au rang $r = 2$  , avec le vol $X$ , $=i$ , $= -1$ ; le $r 2 = -2$

relié lui même au vol $Y$ avec $i = -5$ qui au rang $r2$  vaut $-20$

Suivant la formule $2X - Y = Z$ ce qui donne bien : (2*-2) - (-20) = 16 qui est bien le successeur au rang 2 de ces deux vols i inférieur ...

Dans les entiers négatifs il y a 3 boucles , et , ce n'est pas un hasard ...

C'est une conséquence de la structure arithmétique de Syracuse : L'AS2 , avec sa fonction. dans les itérations  pairs .

(« Fonction de l’AS2, que l’on peut réduire ; avec $x = 2i $ : $f(x)= 1,5x + 1 $ ou $0,5x$ , si $x$ multiple de 4. »)
On peut donc relier tous les vol $i$ ayant un écart entre eux de de $2^n$ , par leurs itérations au rang $r$ ....

Bonne continuation....

Iamexstyle

Membre

Inscription : 27-08-2025

Messages : 19

Re : Automate de Collatz

Merci pour ta réponse.  Il me semble qu'elle dépasse la cadre de la fonction dont je parlais, et de son utilisation. Je m'étais sans aucun doute mal exprimé quand je l'ai introduite la première fois, mea culpa. Je t'invite à prendre en considération le message en haut de cette page qui est certainement mieux cadré.

Sinon, intéressant ce que tu dis. Je vais voir comment ça s'intègre avec ma "preuve" (qui n'en est sans doute pas une, pour le moment je n'aurais que no-cycle, non divergente/borné, et donc par déduction de ces deux là, tend vers 1).

Dernière modification par Iamexstyle (02-11-2025 13:59:17)

syrac

Membre

Inscription : 27-05-2014

Messages : 201

Re : Automate de Collatz

Je ne voudrais pas jouer les trouble-fête mais je trouve que vos débats n'ont plus de lien que lointain avec le problème $3n+1$. Mais aussi avec l'automate de Collatz, sujet de ce fil.

Iamexstyle

Membre

Inscription : 27-08-2025

Messages : 19

Re : Automate de Collatz

Ok, c'est compatible avec ma preuve, sauf que ton modèle semble casser à un moment donné.

Toujours est-il que ca n’implique pas qu’il existe un préimage impair de 3 dans l’automate impair-seulement. En classique : un impair y a un parent impair ssi y non 0 mod 3.

Si tu es intéressé par ma "preuve" et le pont qui existe avec ta fonction, dis le moi.

Pardon Syrac, tu as raison de le rappeler. Je créerais un topic dédié si ça intéresse.

syrac

Membre

Inscription : 27-05-2014

Messages : 201

Re : Automate de Collatz

Je t'ai déjà répondu page précédente : tu découvres des prédécesseurs à 3 alors qu'il n'en a aucun. Ou plutôt, ta formule
$$\textbf{Fratrie} : L_{r,n}=\dfrac{(3\,r+1)\,4^n-1}{3}$$
lui en trouve. A partir de ce constat, quel lien pourrait-il exister avec l'automate ?

Iamexstyle

Membre

Inscription : 27-08-2025

Messages : 19

Re : Automate de Collatz

Il trouve 0 avec un n négatif qui dépasse la borne. J'ai clairement expliqué qu'avec n négatif, pour trouver un impair plus petit ayant le même lien, il ne fallait pas dépasser la borne.
0 n'est pas un impair positif.

Bref, de toute façon cette formule n'est pas révolutionnaire, elle est juste plus "sophistiqué" que X4+1, ou -1 puis divisé par 4. L'intérêt étant peut-être par contre qu'on peut trouver un frère lointain sans iterrer (de préférence plus grand, car on ne connait pas la borne négative). A priori sans aucune utilité pour ton automate.

Dernière modification par Iamexstyle (02-11-2025 17:55:10)

syrac

Membre

Inscription : 27-05-2014

Messages : 201

Re : Automate de Collatz

J'ai clairement expliqué qu'avec n négatif, pour trouver un impair plus petit ayant le même lien, il ne fallait pas dépasser la borne.

Je suppose que ce que tu nommes "un impair positif plus petit ayant le même lien" est un entier plus petit que 3, par exemple, mais qui a le même successeur que lui (5). Ça signifierait que $L_{3, -1}=1/2$ n'est pas un prédécesseur de 5, pas plus que ne l'est un quelconque nombre rationnel obtenu avec $n<0$, mais qu'il existe quand même un entier plus petit que 3 et prédécesseur de 5, sans qu'on sache encore à quoi il ressemble. C'est bien ça ? Je ne me paie pas ta tête, il se trouve seulement que je ne comprends rien à ce dont tu parles. Tout ce que je vois est que $L_{r,n}$ renvoie des résultats erronés et que tu le nies.

Iamexstyle

Membre

Inscription : 27-08-2025

Messages : 19

Re : Automate de Collatz

3 est le plus petit. Dans la modélisation impairs seulement, on n'autorise pas les nombres impairs négatifs.

Juste pour être sur de bonne base :

Exemple clair avec Y = 5 (version “impairs seulement”)

Question : Quels impairs r ont pour prochain impair 5 ?
(Autrement dit : oddize(3r+1) = 5.)

Étape 1 — Les pairs qui mènent à 5
Ce sont les multiples de 5 par des puissances de 2 :
10, 20, 40, 80, 160, 320, 640, ...

Étape 2 — On enlève 1
5·2^k − 1 donne :
9, 19, 39, 79, 159, 319, 639, ...

Étape 3 — On garde ceux divisibles par 3
On veut 5·2^k − 1 = 3r, donc on conserve :
9, 39, 159, 639, ...

Étape 4 — On divise par 3
On obtient les impairs r qui précèdent 5 :
3, 13, 53, 213, 853, ...

Vérification rapide :
3 → 3·3+1 = 10 → oddize = 5
13 → 3·13+1 = 40 → oddize = 5
53 → 3·53+1 = 160 → oddize = 5
etc.

Conclusion (liste) :
Les impairs prédécesseurs de 5 sont exactement 3, 13, 53, 213, 853, ...

--------------------------------------------
À quoi sert la formule “lrx” (navigation sans itérer)

Règle simple entre deux voisins de la liste :
r ↦ 4r + 1

Exemples :
3 → 13 → 53 → 213 → 853 → ...
(Parce que 3(4r+1)+1 = 4(3r+1) : on multiplie juste par 4 l’étape “pair” avant de ré-oddizer, donc l’impair final reste 5.)

n négatif (remonter) :
Remonter d’un cran revient à r ↦ (r−1)/4.
C’est autorisé uniquement si (r−1)/4 est encore un impair positif.

Exemples :
- Depuis 13 : (13−1)/4 = 3  (ok)
- Depuis 3  : (3−1)/4  = 1/2 (pas un impair positif) → hors domaine

Moralité :
• lrx sert de “GPS” pour aller d’un frère à un autre sans dérouler Collatz
• Avec n < 0, on retire des facteurs 2 : encore faut-il que le nombre en possède assez ET que (r−1)/4 reste un impair positif. Sinon, on sort du domaine (ce n’est pas “faux”, c’est simplement hors des impairs positifs).

Autre façon de retrouver tous les prédécesseurs impairs d’un nombre impair Y
(sans itérer, sans formule lrx)

Principe :
Tout prédécesseur impair r de Y vérifie
   3r + 1 = Y · 2^k
pour un certain entier k ≥ 1.

Donc :
   r = (Y · 2^k − 1) / 3

→ Il suffit de parcourir les puissances de 2, et de garder celles
   pour lesquelles (Y · 2^k − 1) est divisible par 3.

Astuce : la parité de k dépend de Y mod 3
   • si Y ≡ 1 (mod 3), il faut que k soit pair
   • si Y ≡ 2 (mod 3), il faut que k soit impair
   • si Y ≡ 0 (mod 3), aucun prédécesseur impair

Exemple avec Y = 5 (car 5 ≡ 2 mod 3 → k impair)
-----------------------------------------------
k = 1 → (5·2 − 1)/3 = 3
k = 3 → (5·8 − 1)/3 = 13
k = 5 → (5·32 − 1)/3 = 53
k = 7 → (5·128 − 1)/3 = 213
...

→ On retrouve la même liste 3, 13, 53, 213, ... sans jamais itérer Collatz.

Remarque :
Si on essaye un k “mauvaise parité”, le résultat n’est pas entier,
ce qui indique simplement que ce k ne correspond pas à un prédécesseur impair valide.

J'espère que c'est plus clair maintenant. Rien de révolutionnaire là-dedans (à mon grand regret ;)).

Dernière modification par Iamexstyle (03-11-2025 00:35:22)

syrac

Membre

Inscription : 27-05-2014

Messages : 201

Re : Automate de Collatz

@lamexstyle,

Page précédente j'ai mentionné comment calculer les prédécesseurs $p_i$ impairs du terme $n$ impair d'une suite de Collatz, où $p_0$ est le plus petit d'entre eux. Je reviens dessus pour l'expliquer autrement que par du code Python :

$u=3 - n \; \mathrm{mod} \; 3$

Si $u=3$ alors $n$ est un multiple de 3 : on abandonne.

$p_0= \dfrac{n \cdot 2^u - 1}{3}$

Les $p$ suivants sont obtenus par récurrence :

$p_i = 4 \; p_{i-1} + 1$

Pour reprendre l'exemple de $n=5$ on a :

$u=3 - 5 \; \mathrm{mod} \; 3=1$

$p_0= \dfrac{5 \cdot 2^1 - 1}{3}=3$

$p_1=4 \cdot 3+1=13$
$p_2=4 \cdot 13+1=53$
$p_3=4 \cdot 53+1=213$
etc.

Mais on peut également procéder comme suit, où $u$ est incrémenté de 2 à chaque itération afin de conserver sa parité :

$p_i = \dfrac{n \cdot 2^{\,u + 2i} - 1}{3}, \qquad i = 0, 1, 2, \dots$

Dernière modification par syrac (04-11-2025 02:30:59)

Iamexstyle

Membre

Inscription : 27-08-2025

Messages : 19

Re : Automate de Collatz

Merci pour cette illustration, très clair !