Automate de Collatz

Michel Coste · 30-04-2025 17:43:11

syrac a écrit :

$$T(n)=\frac{3n+1}{2^{\frac{1}{2}(3n+1)}} \quad \small (n \, impair)$$

Exemple avec $n=7$
$$T(7) = \frac{22}{2^{11}} = \frac{11}{1024}$$

syrac · 30-04-2025 17:50:46

Le code Python et Javascript que je viens de fournir fonctionne parfaitement : 5 étapes pour $n_0=7$, et pour moi c'est le principal. Le reste concerne Riho Terras et ses successeurs.

syrac · 30-04-2025 18:16:33

J'ai oublié de préciser que 11 est bien le successeur impair de 7 dans une suite impaire. Si maintenant tu fais $n_0=11$ tu obtiens $17/65536$, puis avec $n_0=17$ tu obtiens $13/16777216$, etc. Au final, tu as bien la suite impaire de 7 : 7, 11, 17, 13, 5, 1, le tout sans avoir fait une seule division par 2.

Dernière modification par syrac (30-04-2025 18:17:28)

Michel Coste · 30-04-2025 21:13:13

Le $2^{(3n+1)/2}$ au dénominateur est complètement farfelu.
"le tout sans avoir fait une seule division par 2." Wouaf wouaf ...

syrac · 30-04-2025 23:17:09

Je ne comprends pas de quoi tu parles. Après définition de n, terme impair d'une suite de Collatz, et calcul de $T(n)$, le numérateur EST le successeur de n. Quant au dénominateur, sur lequel tu sembles faire une fixation, on s'en tape. Qu'y a-t-il de difficile à comprendre là-dedans ?

$T(7)=\color{red}{11}/1024$
$T(11)=\color{red}{17}/65536$
$T(17)=\color{red}{13}/16777216$
$T(13)=\color{red}{5}/131072$
$T(5)=\color{red}{1}/16$

Suite impaire de 7 : 7, 11, 17, 13, 5, 1

Sans faire une seule division par 2 (juste une puissance de 2, mais on se comprend). Pour ceux qui ont un problème de compréhension, qui cherchent la petite bête ou à détourner l'attention de la vraie portée d'un post parce qu'ils se sentent frustrés, c'est plus évident sous la forme $m / (m \: \& \: -m)$, qui elle ne fait strictement aucune division par 2.

Ça y est, ça commence à rentrer ? Wouaf wouaf.

Dernière modification par syrac (30-04-2025 23:57:49)

syrac · 01-05-2025 13:09:32

Certaines sources sont plus précises que d'autres. Voici les explications fournies par ChatGPT o4-mini-high sur le lien entre la fonction réduite et le code m/(m & -m).

On connait ce raccourci depuis les années 1960 et pourtant on continue 60 ans après à faire des divisions par 2 ! Mais il est possible qu'il n'ait été (ne soit) connu que des programmeurs (dont je suis).

EDIT : on peut télécharger gratuitement le PDF du livre Hacker’s Delight (2002), mentionné par ChatGPT (en anglais) : https://ia801600.us.archive.org/3/items/random-papers9/Henry%20S.%20Warren%20-%20Hacker's%20delight-Addison-Wesley%20(2003).pdf

Dernière modification par syrac (01-05-2025 13:21:50)

syrac · 01-05-2025 13:37:55

[suite du précédent]

On trouve même la seconde édition de ce livre, datée de 2012 : https://ia801600.us.archive.org/3/items/random-papers9/Henry%20S.%20Warren%20-%20Hacker's%20Delight%20(2nd%20Edition)-Addison-Wesley%20Professional%20(2012).pdf

Hacker's Delight signifie "Le bonheur des hackers". Il se pourrait qu'il fasse également le bonheur des matheux... :-)

syrac · 01-05-2025 14:14:43

[suite des précédents]

Je viens de comprendre l'erreur que j'ai commise ci-dessus. J'ai noté la fonction réduite de la manière suivante parce que je n'avais pas accès au code LaTeX :

$T(n)=\dfrac{3n+1}{2^{\frac{1}{2}(3n+1)}} \quad \small (n \, impair)$

on remarque le $2^{\frac{1}{2}(3n+1)}$, qui en réalité devait être $2^{\nu_2(3n+1)}$, la valuation 2-adique de l'entier 3n+1. La forme sous laquelle je l'ai présentée ne permettait pas d'en tirer grand chose... Pour ma défense je dirai que j'utilise le code $m/(m \: \& -m)$ depuis plusieurs années, si bien que la fonction réduite est le cadet de mes soucis. mea culpa.

DrStone · 01-05-2025 18:01:17

syrac a écrit :

Certaines sources sont plus précises que d'autres. Voici les explications fournies par ChatGPT o4-mini-high sur le lien entre la fonction réduite et le code m/(m & -m).
On connait ce raccourci depuis les années 1960 et pourtant on continue 60 ans après à faire des divisions par 2 ! Mais il est possible qu'il n'ait été (ne soit) connu que des programmeurs (dont je suis).

Parce que ça n'a aucun intérêt et ce n'est pas "un raccourci". Au contraire, non seulement ce bout de code est cryptique au possible mais en plus il est légèrement plus lent. La preuve en est ici : https://godbolt.org/z/qW8xd1aoq

Les compilateurs et interpréteurs modernes sont tous capables de réaliser bien plus d'optimisations que tu ne pourras jamais espérer retenir, et écrire du code à la fois parfaitement clair, limpide et prévisible est, aujourd'hui, la méthode la plus sûre et recommandée*.

Maintenant, ça serait bien d'arrêter de propager le bullshit de chatGPT et d'arrêter tout autant de boire ses paroles comme si elles étaient paroles d'évangile.

* Même s'il reste bien sûr des cas où un humain fera mieux… mais ça ne sera jamais sur un cas aussi simple que ça.

Dernière modification par DrStone (01-05-2025 18:16:07)

syrac · 02-05-2025 00:36:20

DrStone a écrit :

ce bout de code est cryptique au possible mais en plus il est légèrement plus lent.

Lol. Je viens d'écrire un script Python qui mesure le temps que la méthode traditionnelle (qui divise par 2 comme une folle) et celle qui utilise le hack en question, mettent pour traiter tous les entiers impairs de 3 à 500 001 (c'est-à-dire le calcul du nombre de termes de leur suite impaire). Résultat :

Temps méthode traditionnelle : 2.3 secondes
Temps méthode hack : 1.3 secondes

Dans son travail de recherche du plus grand entier vérifiant la conjecture de Syracuse ($5 \times 2^{60}$), T. Oliveira e Silva a utilisé ce hack pour gagner le maximum de temps, sans parler de quelques autres astuces permettant de réduire le nombre de calculs. Vu la quantité d'entiers qu'il a testés, le gain de temps total s'est-il mesuré en heures ou en jours ?

Concernant le "bullshit de ChatGPT", je retrouve là le bon vieux réflexe pavlovien anti-ChatGPT, fréquent chez ceux qui n'ont aucune connaissance de ce dont ils parlent. Désolé pour toi que l'IA t’intimide ou t'effraie au point de ne pas l'utiliser et donc de parler sans savoir, mais en ce qui me concerne j'ai parlé plus haut de résultats concrets, pas de croyances personnelles. Sans ChatGPT o3 pour résoudre le problème que j'ai rencontré avec le nombre 478173025621 il m'aurait fallu plusieurs heures pour trouver une solution en cherchant sur Google et plus probablement sur Stack Overflow. En programmation, tomber sur un problème particulièrement difficile est assez fréquent et souvent chronophage ; avec ChatGPT on a la solution en quelques secondes, et pas seulement, on est également gratifié des explications qui accroissent notre savoir et donc nous évitent de retomber dans le même piège.

Donc deux croyances fausses : la méthode traditionnelle est plus rapide que le hack, et les IA produisent du bullshit (je reconnais toutefois que ça peut arriver).

Dernière modification par syrac (02-05-2025 00:39:24)

syrac · 02-05-2025 01:12:53

[Suite du précédent]

Je n'avais pas fait gaffe au code que tu as concocté à mon intention (ce dont je te remercie :-)) :

int div_habituel(int n) {
return n/2;
}

int div_syrac(int n) {
return n / (n & -n);
}

Je ne suis pas sûr que ce soit la bonne méthode pour mesurer la différence de temps d'exécution entre les deux approches. Déjà, tu as omis le 3n + 1, mais surtout je viens d'expliquer avoir testé tous les entiers impairs entre 3 et 500 001, soit 250 000 entiers, et surtout calculé la longueur de la suite impaire de chacun d'eux, ce qui a pris 2.3 et 1.3 seconde au total. Donc la mesure du temps d'exécution de tes deux scripts tu peux déjà le diviser par au moins 250 000 pour obtenir une estimation pas trop mauvaise (à moins que tu ais défini quelque part une plage de valeurs importante, ce que je n'ai pas vu). Résultat : ta méthode de calcul n'est pas fiable (on ne peut pas se baser sur des millionièmes de seconde), alors je te propose de reproduire la mienne et de prendre la peine de m'annoncer les résultats. Tu peux voir les deux scripts Python dans le dernier message de la page 3.

LEG · 02-05-2025 08:35:58

Dans son travail de recherche du plus grand entier vérifiant la conjecture de Syracuse (5*2⁶⁰ )

....
Tu peux aussi t'amuser avec ce nombre qui vérifie la conjecture : $5*2^{127} - 1$ et ensuite avec un autre : $5*2^{521} - 1$...

DrStone · 02-05-2025 11:02:58

Je ne suis pas idiot. J'ai testé avant de parler (et quand je dis tester, ce n'est pas juste dans un morceau de trois lignes de code, bien entendu).

Quoi qu'il en soit, j'obtiens toujours, pour "return n/2" un code allant de 1.15 à 1.33 fois plus rapidement.
Peut-être que mes machines aux configs et architectures un peu particulières y jouent, même si j'en doute, je testerais à l'occasion sur différentes configs et différents types d'architectures (x86, x86-64, MIPS, RISC-V, armv8 64-bits, …, bref, j'aurais de quoi faire) : peut-être serais-je surpris du résultat ? Qui sait!

Enfin bref, de toute façon je ne vais pas me battre des heures j'ai bien d'autres choses à faire ! Sur ce, bon weekend à tous et à la prochaine !

Dernière modification par DrStone (02-05-2025 11:13:43)

syrac · 03-05-2025 12:01:30

J'ai supprimé mes deux précédents messages pour faire un peu de ménage, parce ce que cette histoire de "qui est le plus rapide" devenait bordélique. En remplacement j'ai construit la suite de Collatz des 10 premiers millions d'entiers impairs, à l'aide de la méthode standard, c'est-à-dire en divisant à profusion par 2, puis en utilisant le hack binaire $m/(m \: \& -m)$, le tout en mesurant leur temps respectif d'exécution. Résultat :

Temps méthode traditionnelle : 118 s
Temps méthode hack : 64 s

Le hack ne prend que 54 % du temps de l'autre méthode. On peut donc en déduire qu'il est environ deux fois plus rapide.

PS : je suis tombé hier soir sur une vidéo Youtube datant de 3 semaines, dans laquelle Etienne Klein exprime son opinion sur l'IA. Ça change radicalement du discours ambiant. Il commence par expliquer que dans "Intelligence Artificielle", le mot Intelligence est anglais (eh oui, c'est outre-atlantique que tout ça a commencé) et peut se traduire par "renseignement", "collecte d'informations", ce qui est nettement plus proche de la réalité que son acception française, ou du moins l'était à l'origine. Voir les 24 premières minutes de cette conférence : https://www.youtube.com/watch?v=31GPmankg0A

Bernard-maths · 06-05-2025 07:32:31

Bonjour à tous !

IA ... à rapprocher de ... IS = Intelligence Service, of England ...

Iamesxtyle · 31-07-2025 23:27:07

Bonjour,

J'ai trouvé une fonction fermé pour connaître les prédécesseurs (impairs) de tout entier impair. Cela vous serait-il utile, ou pas vraiment dans votre cas ?

Iamesxtyle · 01-08-2025 11:14:40

Par corrélation, j'ai PEUT-ÊTRE aussi un outil de test.
C'est-à-dire dire que pour un x donné et son temps de vol connue, on peut vérifier si c'est juste.

En gros c'est une forme de signature. Alors évidemment, ça change rien à la durée pour déterminer le temps de vol, mais ça permet de le vérifier (je crois). Donc si on tente des résolutions par d'autres modèles, peut-être que ça peut être utile.

Iamesxtyle · 01-08-2025 17:32:17

Iamesxtyle a écrit :

Par corrélation, j'ai PEUT-ÊTRE aussi un outil de test.
C'est-à-dire dire que pour un x donné et son temps de vol connue, on peut vérifier si c'est juste.
En gros c'est une forme de signature. Alors évidemment, ça change rien à la durée pour déterminer le temps de vol, mais ça permet de le vérifier (je crois). Donc si on tente des résolutions par d'autres modèles, peut-être que ça peut être utile.

Bon finalement non. Je pensais avoir identifié un pattern de fin dans la compression, mais que nini ;)

syrac · 04-08-2025 17:06:18

lamesxtyle a écrit :

J'ai trouvé une fonction fermé pour connaître les prédécesseurs (impairs) de tout entier impair.

Bonjour, voici une fonction qui permet de calculer les 9 premiers prédécesseurs impairs d'un terme impair dans une suite de Collatz. Version compréhensible :

"""

Calcul des prédécesseurs de n impair.

d = 0 (défaut) : les 9 premiers prédécesseurs sont affichés,

d = 1 : parmi eux, seuls sont affichés les non multiples de 3

"""

def preds(n, d=0):

    m = 3 - n % 3

    if m == 3:

        print("Multiple de 3")

        return None

    else:

        lst = []

        k = (n * 2**m - 1) // 3

        lst.append(k)

        for j in range(1, 9):

            k = 4 * k + 1

            lst.append(k)

        if d == 1:

            print([k for k in lst if k % 3 > 0])

        else:

            print(lst)

Exemples :
preds(17) = [11, 45, 181, 725, 2901, 11605, 46421, 185685, 742741]
preds(17, 1) = [11, 181, 725, 11605, 46421, 742741]

Version optimisée par ChatGPT 4o, dite "juste pour le sport" :-) :

def preds(n, d=0):

    if n % 3 == 0:

        print("Multiple de 3")

        return None

    k = (n * 2**(3 - n % 3) - 1) // 3

    lst = [k] + [k := 4 * k + 1 for _ in range(8)]

    print([x for x in lst if x % 3 > 0] if d else lst)

Dernière modification par syrac (05-08-2025 00:38:30)

lamexstyle · 27-08-2025 17:03:49

Oui, c'est pareil, juste formulé différemment ... ;)

[tex]\textbf{Fratrie} : L_{r,n}=\dfrac{(3r+1)4^n-1}{3}.[/tex]

J'imagine que je n'ai fait que de la redite finalement dans ma petite étude (en même temps, ce serait logique) ;)

L'IA ça peut être pratique, mais me concernant, il me fait beaucoup balader ;)

Dernièrement, en lui donnant un encodage particulier, il est parti sur une théorie de liens de congruence. En gros, il considère qu'il y a des congruences qui vont déclencher nécessairement t divisions par 2. Il m'a fait faire plein de LP pour démontrer ceci...

A priori, "on" aurait démontré le cas t = 2 (2 divisions par 2), et il semblerait que c'est semblable pour d'autres, mais ça on ne peut pas le prouver... Je ne sais même pas si c'est juste, ou si c'est encore une fois de la redite...

Si ça intéresse... mais j'ai peur de vous faire perdre votre temps.

syrac · 27-08-2025 17:12:43

Merci pour ce retour, mais ç'aurait été bien de définir les variables $r$ et $n$.

Je me doute que $r$ est un entier impair, mais $n$ c'est quoi ?

lamexstyle · 27-08-2025 17:20:14

Pardon.

En effet, r est n'importe quel entier impair.
n est la position du frère par rapport à r.
n peut être négatif ou positif.
Par contre, si n est négatif, il donnera un entier cohérent tant qu'on n'a pas dépassé le plus petit r de la fratrie (j'appelle ça une racine minimale).

Donc si on donne r = 13, et n = -1, on aura bien 3. Par contre, avec n = -2, on aura un nombre non entier.

syrac · 27-08-2025 17:35:28

Et c'est quoi le frère de $r$ ? Puisque tu as répondu à mon post dans lequel je proposais un script Python pour le calcul des prédécesseurs impairs d'un entier impair, tu voulais sans doute parler de prédécesseur plutôt que de frère, non ? Il est nécessaire de se mettre d'accord sur une terminologie, sinon on n'a aucune chance de se comprendre ! :-)

lamexstyle · 27-08-2025 18:18:53

En effet, je n'ai pas les termes académiques.

Mon étude porte sur le(s) tableau(x) compressé(s) dont voici un extrait.

Lien f(r) | Racine r | L_{r,1} | L_{r,2} | L_{r,3}

----------+----------+---------+---------+---------

        | 1        | 5       | 21      | 85

        | 3        | 13      | 53      | 213

       | 7        | 29      | 117     | 469

        | 9        | 37      | 149     | 597

       | 11       | 45      | 181     | 725

       | 15       | 61      | 245     | 981

       | 17       | 69      | 277     | 1109

       | 19       | 77      | 309     | 1237

       | 23       | 93      | 373     | 1493

       | 25       | 101     | 405     | 1621

n permet de naviguer relativement à la position de x (r dans mon tableau).

Racine r permet de déterminer tous les liens (colonne liens f(r)), il a des "frères" (colonne L_{...}), c'est-à-dire des entiers impairs qui en effet peuvent être des prédécesseurs (grâce à leur double) avec r, et qui ont le même lien.

syrac · 27-08-2025 23:05:45

Je joins une capture de quelques calculs basés sur ta formule, dans Mathematica. Je regrette de le dire mais tes résultats sont erronés. Ta formule trouve des prédécesseurs à 3, qui en tant que multiple de 3 n'en a aucun. Les prédécesseurs de 5 sont identiques à ceux de 1.

La fonction preds[] est l'équivalent en langage Wolfram du script Python que j'ai posté plus haut. Ce qu'elle produit est juste.

Mais c'est bien d'avoir essayé, il vaut mieux faire des erreurs que de ne rien tenter ! :-)

prédécesseurs

Dernière modification par syrac (27-08-2025 23:14:45)

Forum de mathématiques - Bibm@th.net

#76 30-04-2025 17:43:11

Re : Automate de Collatz

#77 30-04-2025 17:50:46

Re : Automate de Collatz

#78 30-04-2025 18:16:33

Re : Automate de Collatz

#79 30-04-2025 21:13:13

Re : Automate de Collatz

#80 30-04-2025 23:17:09

Re : Automate de Collatz

#81 01-05-2025 13:09:32

Re : Automate de Collatz

#82 01-05-2025 13:37:55

Re : Automate de Collatz

#83 01-05-2025 14:14:43

Re : Automate de Collatz

#84 01-05-2025 18:01:17

Re : Automate de Collatz

#85 02-05-2025 00:36:20

Re : Automate de Collatz

#86 02-05-2025 01:12:53

Re : Automate de Collatz

#87 02-05-2025 08:35:58

Re : Automate de Collatz

#88 02-05-2025 11:02:58

Re : Automate de Collatz

#89 03-05-2025 12:01:30

Re : Automate de Collatz

#90 06-05-2025 07:32:31

Re : Automate de Collatz

#91 31-07-2025 23:27:07

Re : Automate de Collatz

#92 01-08-2025 11:14:40

Re : Automate de Collatz

#93 01-08-2025 17:32:17

Re : Automate de Collatz

#94 04-08-2025 17:06:18

Re : Automate de Collatz

#95 27-08-2025 17:03:49

Re : Automate de Collatz

#96 27-08-2025 17:12:43

Re : Automate de Collatz

#97 27-08-2025 17:20:14

Re : Automate de Collatz

#98 27-08-2025 17:35:28

Re : Automate de Collatz

#99 27-08-2025 18:18:53

Re : Automate de Collatz

#100 27-08-2025 23:05:45

Re : Automate de Collatz

Réponse rapide

Pied de page des forums