Suite qui ressemble à Syracuse

Discussions générales concernant les mathématiques.
[forum modéré par les modérateurs globaux du site]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
elhi
Utilisateur confirmé
Utilisateur confirmé
Messages : 12
Inscription : samedi 20 septembre 2014, 23:41
Statut actuel : Autre

Suite qui ressemble à Syracuse

Message par elhi »

Bonjour à tous,
Inscrit sur ce forum en 2014 (pourquoi ? je ne sais pas) , un mail de l'admin m'y a ramené en 2020 alors que, coïncidence, ayant oublié les maths pendant des années, je m'intéressais ces jours-ci à la suite de Syracuse.

La question plus générale qui m'anime est : comment faire surgir du compliqué à partir du simple ?
J'ai testé différentes variantes de cette suite avec un tableur, un peu décevantes.
Et puis je suis tombé sur celle-ci qui pourrait vous amuser :

A partir d'un nombre N
Si N est divisible par 2 , le terme suivant est N/2
Si N est divisible par 3 , le terme suivant est N/3
Sinon, le terme suivant est 7N+1
Je la baptise Syracuse déconfinée.

Avec un tableur, pour vous faire gagner 2 minutes :
- La colonne 1 contient les 2 constantes, en A2 et A3 (plus précisément la cellule \$A\$2 contient la constante "7", et \$A\$3 contient "1" )
- Avec le nombre N de départ en ligne 1 on peut mettre cette formule dans la ligne 2 (et tirer ensuite) :
Pour la colonne B :

Code : Tout sélectionner

=SI((B1/2)=ENT(B1/2);B1/2;( SI((B1/3)=ENT(B1/3);B1/3;B1*$A$2+$A$3)))
J'ai exploré quelques dizaines de cas et je remarque déjà :
- Une bonne proportion de nombres "convergent" plus ou moins vite vers la série 8, 4, 2, 1
- Des séries apparaissent contenant 19 : appelons-les "séries du 19", elles ont une longueur de 34 termes
- Le reste des entiers ( 31, 53, 79 ...) semblent déboucher sur des suites divergentes.

- Il me paraît amusant d'explorer les nombres par lesquels passent les séries divergentes, et de voir si il y a des séries "parallèles"
- Les divergents ont-ils une caractéristique ?
- Dans les multiples de 19, la plupart sont des suites du 19, d'autres divergent, d'autres convergent vers 8,4,2,1 ... La première à diverger semble être 13x19, alors que 13 converge ...

Bon amusement !
Michel038
Dernière modification par MB le mardi 12 mai 2020, 12:44, modifié 2 fois.
Raison : Saisie correcte des dollars (il faut utiliser un backslash devant le dollar).

MB
Administrateur
Administrateur
Messages : 7189
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Re: Suite qui ressemble à Syracuse

Message par MB »

Bonjour, j'ai déplacé le sujet dans la tribune des mathématiques.
Au lieu d'utiliser le tableur, voici un petit programme Python qui permet d'étudier de de représenter cette suite.

Code : Tout sélectionner

import matplotlib.pyplot as plt
import numpy as np

def plot_syracuse(u):
    y = [u]
    while (not u in y[:-1]) and (len(y) < 1000) :
        if u%2 == 0:
            u = u//2
        elif u%3 == 0:
            u = u//3
        else:
            u = 7*u+1
        y.append(u)
    x = list(range(1,len(y)+1))
    plt.plot(x,y,linestyle='--',marker='o',markerfacecolor='red',markersize=6)
    plt.annotate(str(y[-1]),xy=(x[-1],y[-1]),xytext=(0.9*len(x),0.5*max(y)),arrowprops=dict(arrowstyle="->",color="0.5",shrinkB=6,connectionstyle="arc3,rad=-0.3"))
    plt.savefig('figure_{}.png'.format(y[0]),bbox_inches='tight')
    plt.close()

plot_syracuse(19)
Ce programme va produire l'image suivante.
figure_19.png
Le programme représente tous les termes de la suite jusqu'à retomber sur un terme déjà obtenu (ou bien dépasser les 1000 termes calculés afin d'éviter des boucles infinies).
Vous ne pouvez pas consulter les pièces jointes insérées à ce message.
MB (Pas d'aide en Message Privé)
Merci d'utiliser MathJax (voir ici) et d'éviter le style SMS pour la lisibilité des messages.

elhi
Utilisateur confirmé
Utilisateur confirmé
Messages : 12
Inscription : samedi 20 septembre 2014, 23:41
Statut actuel : Autre

Re: Suite qui ressemble à Syracuse

Message par elhi »

Merci pour votre intervention (et la mise en forme de mon message)

En regardant plus loin, 247 (13x19) converge en un peu plus de 200 itérations (temps de vol), et culmine à 8235396.

Je subodore qu'aucun nombre ne diverge ... mais on devrait trouver d'autres séries que celle du 19.
31 et 475 dépassent la capacité de calcul du tableur .... (Open office)
79 fait un joli parcours si OO calc ne fait pas d'erreurs, avec 1215 itérations.
19 au carré est pas mal aussi.


En programmation, en effet on peut définir la longueur de la suite jusqu'à obtenir le chiffre 19, ou la séquence 8,4,2,1, ou détecter une série répétitive.
( Il faudra que je me mette à Python. Ce qui me rebute c'est l'installation de l'environnement, la prise en main, et les premiers pas : vous avez des liens pour les newbies ?) Après, pour coder, ça ira.
Il serait amusant d'avoir un graphe avec la longueur des suites en fonction de N ...

PC sous windows 7.

Framboise
Utilisateur chevronné
Utilisateur chevronné
Messages : 1159
Inscription : lundi 21 mai 2007, 13:57
Statut actuel : Autre
Localisation : Dordogne

Re: Suite qui ressemble à Syracuse

Message par Framboise »

Hello elhi,

Merci pour ce petit (?) casse tête sympathique.
Cela nous change de l'oppression de ces temps de pandémie, avec ses gros risques de réactivation.
La suite originelle se Syracuse avait incité à bien des conjectures.

C'est l'occasion de faire tourner nos ordis sur ces longues suites.
On va vite arriver à des nombres au delà des capacités numériques des programmes.
Je vais peut être reprendre UBASIC dans une DOSBOX vu ses formidables capacités numériques ou PARI/GP.

https://pari.math.u-bordeaux.fr/download.html

Krystal
J'ai le virus des sciences, ça se soigne ?

elhi
Utilisateur confirmé
Utilisateur confirmé
Messages : 12
Inscription : samedi 20 septembre 2014, 23:41
Statut actuel : Autre

Re: Suite qui ressemble à Syracuse

Message par elhi »

A défaut de me lancer dans Python, j'ai installé Small Basic de Microsoft , et me suis remis au codage, abandonné depuis 40 ans ...
Small Basic semble gérer jusqu'à 30 chiffres sur les entiers d'après mes premiers tests.

Il y a malgré tout des erreurs sur les nombres de 15 chiffres dans les séries (après de milliers de divisions par 2 et 3 et multiplications par 7) , erreurs que j'ai essayé de résoudre avec un arrondi, sans trop savoir si c'est juste ou non ...
A vérifier...

Si c'est juste, ce que je croyais être des séries divergentes seraient des boucles d'environ 900 termes, passant par des nombres de plus de 15 chiffres.

Sinon, les séries convergentes les plus longues semblent plafonner vers 2000 termes (exemple N=26587, 2001 termes) pour des nombres N raisonnables jusqu'à 50000.

Je n'ai pas encore vérifié quels nombres autres que des multiples (de 2 et 3) de 19 aboutissent à "la série du 19" ...

elhi
Utilisateur confirmé
Utilisateur confirmé
Messages : 12
Inscription : samedi 20 septembre 2014, 23:41
Statut actuel : Autre

Re: Suite qui ressemble à Syracuse

Message par elhi »

Mon programme commence a fonctionner ...
Toujours à condition que je n'aie pas d'erreurs avec les arrondis, la précision de small basic dépendant de la nature des opérations réalisées ...

Sur les 1500 premiers nombres N, il y a 1159 suites qui terminent sur la boucle triviale 8,4,2,1 et qui plafonnent vers 1500 termes, niveau déjà à peu près atteint par N= 79 (1215 termes) et en moyenne il y a environ 180 termes , avec de grosses disparités.

En plus de la boucle B19 de 34 termes dont j'ai déjà parlé, le N=31 génère donc une boucle de 988 termes, ces deux boucles sont le point d'atterrissage des 341 autres nombres N.
Ayant encore des erreurs, je n'ai pas bien observé ceux qui tombent dans la B19 ou la B31, ni poussé mes recherches au-delà de 1500 ...

(J'ai donc abusivement parlé de "convergentes" précédemment et me suis planté pour les "divergentes", elles tombent apparemment toutes sur la boucle B31)

MB
Administrateur
Administrateur
Messages : 7189
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Re: Suite qui ressemble à Syracuse

Message par MB »

C'est un peu surprenant les erreurs d'arrondi alors que normalement il n'y a que des opérations entières.
Sinon, voilà un programme (que j'espère correct car pas trop vérifié) en Python.

Code : Tout sélectionner

stop = []

def syracuse(u):
    y = [u]
    while (not u in y[:-1]):
        if u%2 == 0:
            u = u//2
        elif u%3 == 0:
            u = u//3
        else:
            u = 7*u+1
        if u in stop:
            return u
        y.append(u)
    stop.append(y[-1])
    return y[-1]

results={}
for n in range(5000):
    u = syracuse(n)
    results.setdefault(u,0)
    results[u] += 1

for key, value in sorted(results.items()):
    print('{:>4}: {}'.format(key, value))
Et voilà le résultat affiché.

Code : Tout sélectionner

   0: 1
   1: 3871
  19: 1128
Les résultats concernent les premiers termes compris entre 0 et 4999. En oubliant le cas 0, on constate qu'ils retombent tous sur la série du 1 ou sur celle du 19. La série du 31 ne retombe pas sur celle du 19 ?
MB (Pas d'aide en Message Privé)
Merci d'utiliser MathJax (voir ici) et d'éviter le style SMS pour la lisibilité des messages.

gigiair
Utilisateur chevronné
Utilisateur chevronné
Messages : 2578
Inscription : samedi 08 juillet 2006, 20:56
Localisation : Saint Bonnet Elvert

Re: Suite qui ressemble à Syracuse

Message par gigiair »

Je ne suis pas sûr que les logiciels généralistes soient bien appropriés pour effectuer des calculs mathématiques.
La valeur des nombres est en général limitée par le nombre d'octets qui leur est réservé, surtout les tableurs qui ne sont vraiment pas fait pour ça.

Il vaut mieux utiliser un logiciel spécialisé en calcul mathématique.

Pour ma part, j'utilise calc/Emacs qui est une calculatrice ultra-puissante capable de calculs symboliques. Mathematica ferait aussi bien, mais calc est gratuit et a l'avantage d'être disponible sous à peu près toutes les plates-formes (j'ai ça sur mon smartphone android à 150 euros -- sous Termux)

J'ai testé toutes les suites engendrées par les nombres inférieurs à 100 000. La longueur maximale de la suite atteinte avant convergence est 7800 atteinte pour 93235.
JJR.
LaTeXien migrateur.

elhi
Utilisateur confirmé
Utilisateur confirmé
Messages : 12
Inscription : samedi 20 septembre 2014, 23:41
Statut actuel : Autre

Re: Suite qui ressemble à Syracuse

Message par elhi »

Merci pour vos interventions.

Je vais regarder calc/emacs, mais avec small basic, j'ai fini par prendre la partie entière de (u/2) , (u/3) et (7u +1), et là tout va bien, apparemment on peut aller a plus de 25 chiffres significatifs.

Après 40 ans "d'abstinence" (l'époque de "BASIC" et "COBOL" ! !) l'avantage de small basic c'est qu'il m'a fallu 5 minutes pour télécharger, installer, et écrire un premier programme. Et 1h pour lire un tuto et démarrer l'écriture de ce programme.
Pour ceux qui n'ont jamais codé, c'est peut-être le bon moyen pour débuter ...
Et puis l'investissement peut être "rentabilisé" en développant d'autres applis que des maths ...

Bon, j'avais perdu les bons réflexes, et ce problème n'est pas si facile.
Au début j'avais décidé de ne pas bufferiser du tout les résultats intermédiaires , mais d'arrêter le calcul des termes dès qu'un des termes était inférieur à N (c'est à dire un cas traité précédemment) ; ça ne permet pas de compter précisément le nombre de termes, mais c'est 100 fois plus rapide.
Puis j'ai repris la méthode de MB, plus rigoureuse, mais il me faut plus de 5 minutes de calcul pour aller jusqu'à N=1000.
Pour aller à 100 000 ça ferait 10 heures ...à moins que je puisse optimiser ...

Variantes.
Et cerise sur le gâteau, en regardant des variantes, il semble y avoir des cas intéressants en utilisant notamment (7u+5).

(Dans cette variante je rencontre un cas particulier que je n'avais pas vu ailleurs, le 71 atterrit dans la boucle 139 (de longueur 278). Cette boucle "devrait se nommer" B139 mais mon programme la nomme B71. Le 91 fait pareil.
Edit 20h : c'est corrigé, je detecte les B1, B5, B11, B95, B139 dans la variante 7u+5 )


Et pour la variante (7u+2), gigiair, vous qui avez un calculateur costaud, vous pouvez essayer de voir où va N=5 ?
Et pourquoi (7u+2), (7u+3) (7u+4), (7u+6) n'auraient-elles pas du tout le même comportement que (7u+1) et (7u+5) ?

MB
Administrateur
Administrateur
Messages : 7189
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Re: Suite qui ressemble à Syracuse

Message par MB »

Je viens de faire tourner le programme jusqu'à 100000. Voici les résultats.

Code : Tout sélectionner

$ time python syracuse.py 
   0: 1
   1: 78147
  19: 21852

real 5m22,239s
user 5m21,939s
sys 0m0,033s
Donc plus de 5 minutes avec Python sur un i7-3770 de 2012.
MB (Pas d'aide en Message Privé)
Merci d'utiliser MathJax (voir ici) et d'éviter le style SMS pour la lisibilité des messages.

MB
Administrateur
Administrateur
Messages : 7189
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Re: Suite qui ressemble à Syracuse

Message par MB »

Pour la suite 19, voici les informations que j'obtiens.

Code : Tout sélectionner

premier terme: 19
premier terme redondant: 19
rang du premier terme redondant: 34
altitude maximale: 20168
Voici tous les termes de cette suite.

Code : Tout sélectionner

[19, 134, 67, 470, 235, 1646, 823, 5762, 2881, 20168, 10084, 5042, 2521, 17648, 8824, 4412, 2206, 1103, 7722, 3861, 1287, 429, 143, 1002, 501, 167, 1170, 585, 195, 65, 456, 228, 114, 57, 19]
Et pour la suite 31.

Code : Tout sélectionner

premier terme: 31
premier terme redondant: 1646
rang du premier terme redondant: 1668
altitude maximale: 515804484810045123540
On constate que cette suite retombe sur le terme 1646, qui est bien un terme de la suite 19. On va bien retomber sur la même boucle.
MB (Pas d'aide en Message Privé)
Merci d'utiliser MathJax (voir ici) et d'éviter le style SMS pour la lisibilité des messages.

elhi
Utilisateur confirmé
Utilisateur confirmé
Messages : 12
Inscription : samedi 20 septembre 2014, 23:41
Statut actuel : Autre

Re: Suite qui ressemble à Syracuse

Message par elhi »

Ah, ça débusque une faiblesse de small basic !
Les variables n'ont pas de type. Une hérésie pour certains, un atout pour d'autres ...

Vous allez rire :
Voici un programme de 4 lignes pour afficher le nombre max indiqué par MB et ajouter 1

Code : Tout sélectionner

a="515804484810045123540"
textwindow.writeline(515804484810045123540)
textwindow.writeline(515804484810045123540+1)
TextWindow.WriteLine(a)
TextWindow.WriteLine(a+1)
et voici le résultat affiché :

Code : Tout sélectionner

515804484810045000000
515804484810045000001
515804484810045123540
515804484810045123541
Visiblement dans le premier cas il est arrondi ou tronqué à 15 chiffres significatifs à l'initialisation, et dans les autres cas il ne l'est pas.
La doc en ligne est absconse ...

Dommage, j'avais trouvé une extension pour optimiser la vitesse de calcul (Litdev), je gagne un facteur 6 facile

MB
Administrateur
Administrateur
Messages : 7189
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Re: Suite qui ressemble à Syracuse

Message par MB »

Encore un produit Microsoft à éviter on dirait. :mrgreen:
MB (Pas d'aide en Message Privé)
Merci d'utiliser MathJax (voir ici) et d'éviter le style SMS pour la lisibilité des messages.

elhi
Utilisateur confirmé
Utilisateur confirmé
Messages : 12
Inscription : samedi 20 septembre 2014, 23:41
Statut actuel : Autre

Re: Suite qui ressemble à Syracuse

Message par elhi »

La fonction arrondi ne marche que pour des nombres inférieurs à 15 chiffres.

Pour les grands nombres je les découpe en tranches de 10 chiffres, j'arrondis ce qui reste à droite, et je recolle les morceaux ...
mais il faut des tests, et je n'ai pas de moyen commode pour vérifier

Bon, je vais faire des jeux en small basic, et pour les Syracuse, je vais faire autrement.

Encore merci de vous être penchés sur le sujet.
J'espère que mes (longs) messages serviront un jour à quelqu'un !

Dans Python, ça passe comment les grands chiffres ?
Il faut déclarer un type ?

gigiair
Utilisateur chevronné
Utilisateur chevronné
Messages : 2578
Inscription : samedi 08 juillet 2006, 20:56
Localisation : Saint Bonnet Elvert

Re: Suite qui ressemble à Syracuse

Message par gigiair »

Je ne connais pas particulièrement Python, mais selon toute vraisemblance, les nombres entiers sont représentés dans une séquence d'octets de taille fixe et quand on manipule des grand nombres, il y a forcément débordement. Dans ce cas le résultat est du grand n'importe quoi et je ne prend pas grand risque à dire que l'utilisateur n'en est pas averti.
Pas plus que Basic, Python n'est pas fait pour explorer les nombres entiers de grande taille.
On peut utiliser Calc/Emacs, Xcas, Maxima, Maple, Mathematica et sans doute d'autres logiciels capables de calculs symboliques. Les calculs sont alors plus lents car les représentations des entiers sont des suites d'octets potentiellement infinies.
JJR.
LaTeXien migrateur.

MB
Administrateur
Administrateur
Messages : 7189
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Re: Suite qui ressemble à Syracuse

Message par MB »

En ce qui concerne Python 3, les entiers n'ont pas de limite théorique, uniquement une limite physique liée à la mémoire disponible sur la machine qui fait tourner le programme. Par ailleurs, pas de déclaration de type en Python.
MB (Pas d'aide en Message Privé)
Merci d'utiliser MathJax (voir ici) et d'éviter le style SMS pour la lisibilité des messages.

elhi
Utilisateur confirmé
Utilisateur confirmé
Messages : 12
Inscription : samedi 20 septembre 2014, 23:41
Statut actuel : Autre

Re: Suite qui ressemble à Syracuse

Message par elhi »

Trop fort Small Basic ...
Voici un programme :

Code : Tout sélectionner

u=2125960299540795
TextWindow.WriteLine (u)

v=4251920599081590
TextWindow.WriteLine (v)
TextWindow.WriteLine (v/2)
et voici le résultat

Code : Tout sélectionner

2125960299540800
4251920599081590
2125960299540795
le premier, bien que (moitié) plus petit, prend (+5) sans raison
si quelqu'un trouve une explication ... :shock: :shock:
( ceci n'est qu'un exemple, valable surtout si u est le résultat d'un calcul, il ne suffit pas de mettre des guillemets pour affecter u="chaine" pour parer à l'apparition inopinée de ce bug dans les calculs)
Le pire c'est que tous les bugs sont "silencieux", pas de message d'avertissement, j'ai du les débusquer un à un dans les 1000 termes de U31 grâce aux informations que vous m'avez données !

Par exemple, quand je découpe les nombres en tranches de 10 chiffres comme une chaine de caractères, si le plus à gauche est un zéro, celui-ci disparait au moindre traitement, je suis obligé de coller un caractère alphanumérique avant, puis l'enlever au dernier moment, etc, une tambouille infâme.
Dernière modification par elhi le dimanche 17 mai 2020, 10:36, modifié 4 fois.

MB
Administrateur
Administrateur
Messages : 7189
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Re: Suite qui ressemble à Syracuse

Message par MB »

Il n'existe pas un type Long pour gérer des entiers un peu grands ?
MB (Pas d'aide en Message Privé)
Merci d'utiliser MathJax (voir ici) et d'éviter le style SMS pour la lisibilité des messages.

elhi
Utilisateur confirmé
Utilisateur confirmé
Messages : 12
Inscription : samedi 20 septembre 2014, 23:41
Statut actuel : Autre

Re: Suite qui ressemble à Syracuse

Message par elhi »

Edit : J'ai un peu modifié mon précédent message pour le rendre encore plus fou : 5 = 0 (u - v/2 = 0 )

- Non, il n'existe aucun type de variable en small basic, finalement croyant simplifier, ils ont compliqué terriblement.

Par exemple pour concaténer a et b (respectivement "123" et "456" ) il faut faire

Code : Tout sélectionner

Text.GetSubTextToEnd(("$"+a+b),2)
c'est à dire ajouter un caractère quelconque , et l'enlever ensuite, sinon on obtient "579".

Sinon, sur tous les systèmes Linux (et Unix depuis 1975) on peut appeler BC (basic calculator) ou "calculatrice à précision arbitraire" qui ne limite pas les calculs du tout, au risque d'obtenir des milliards de chiffres et un temps de calcul infini.
( par défaut, il arrondit à 0 chiffres après la virgule, 1/3 affiche 0 , il faut spécifier le nombre de chiffres qu'on veut afficher pour les non-entiers)

MB
Administrateur
Administrateur
Messages : 7189
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Re: Suite qui ressemble à Syracuse

Message par MB »

La commande Text.Append(123,456) donne 579 ?
MB (Pas d'aide en Message Privé)
Merci d'utiliser MathJax (voir ici) et d'éviter le style SMS pour la lisibilité des messages.