La suite de Syracuse

[spacemax]

Bonjour,

Je vous propose de faire chauffer vos neurones et vos petites machines préférées. En 1928, Lothar Collatz a eu une vision et inventa le problème dit 3x+1. Selon lui, tout entier >1 obéit à la règle suivante : S'il est pair on le divise par 2.S'il est impair on le multiplie par 3 et on ajoute 1. Du résultat obtenu, on obtient un entier. L'itération de cet alorithme fait que l'on obtient toujours 1 quelque soit l'entier choisi au départ...Gloups ! Fallait y penser.
Le plus beau, c'est qu'aucun autre mathématicien n'est arrivé à démontrer qu'il existait un entier pour lequel cela ne se vérifait pas. A ce jour, le plus grand nombre calculait est 1.25x2^62 mais cela ne suffit pas à démontrait qu'il n'existe pas un nombre pour lequel la récurrence tend vers l'infini.

Je vous propose de chercher dans les 500 ou 1000 premier nombres celui qui à la plus haute altitude et la plus haute durée en sachant que :
Le nombre d'itération nécessaire pour obtenir 1 est appelé la durée du vol.
Le plus grand nombre obtenu dans la suite est appelé l'altitude maximale
Un+1 = Un/2 si n est pair
Un+1 = 3Un + 1 dit Un est impair

exemple :
2 1 durée 1 altitude 2
5 16 8 4 2 1 durée 5 altitude 16

Ca prend du temps mais c'est suprenant. Pour 27 la durée du vol est 111 et pour 301 seulement 16.
On pourrait également chercher le nombre le plus élevé avec la durée la plus faible...
Voilou.

[Marge]

Bonsoir, spacemax,

Très belle initiative !
Malheureusement (ou heureusement, selon les points de vue), la suite de Syracuse a déjà été présentée par Céline le 23 mars 2014, trois jours à peine après son inscription sur le site ! - un envol printanier en quelque sorte - dans ce que nous avons l'habitude d'appeler les MPO (pour Misez P'tit, Optimisez ! référence à la série d'article du même nom dans l'Ordinateur de Poche). C'est dans cette série de posts, ou dans le MRA tout récent (Misez Rapide... j'ai oublié la suite...), que les Siliciens ont classé ces défis mathématiques divertissants (pas pour tout le monde, mais qu'importe).

Le MPO n°53 avait d'ailleurs intéressé beaucoup de monde ; je pense que tu seras content de le découvrir.

[spacemax]

Mince alors...pour une fois que je trouve une suite intéressante.
C'est que partie remise !

[C.Ret]

Bonjour,

Même si le sujet est effectivement celui de MPO-53, la question posée n'est pas exactement la même, et il pourrait être interessant et amusant de traiter une nouvelle fois ce thème avec une approche et un objectif diffèrent.

En effet, si l'on suit le contenu du MPO-53, on se rend compte que l'on a recherché à minimiser le code et optimiser la détermination des temps de vol et altitude maximale produitent par un nombre donné. Des astuces et des codes fort efficaces et petits ont été proposés qui optimisent la détermination de ces deux grandeurs pour un seul nombre initial.

Or la question de spacemax concerne tout un intervalle de valeurs !

Je ne suis pas sûr que les codes proposés dans le MPO-53 soient ideaux pour rapidement ou facilement déterminer les temps de vols et altitude de croisière de 1000 (ou même 500) entiers successifs.
Car même à 7.5s par entier, il faudra encore près de 2h5min pour le faire sur 1000 entier !
J'avais d'ailleurs posé une question dans ce sens, mais personne à l'époque n'y avait fait très attention.

Alors, jeunes pockéteux à vos claviers !

Pour ma part, je prends mon bloc-note car je ne sais pas encore comment m'y prendre...
... établissons déjà une stratégie.

Y-a-t-il un moyen de ne pas répéter 1000x les mêmes calculs pour déterminer Temps de Vol et Altitude maxmiale de tous les entiers compris dans l'intervella [A B] ?

Avec d'ailleurs A non nécessairement égal à 1 - hein! On est pas non plus des débutants ou des ramollis du bulbe cortexal (ou si c'est le cas on a des pockets et micros qui ont plusieurs dizianes d'années d'expérience et rattrapent le coup) -.

[caloubugs]

J'ai passé pas mal de temps sur ce MPO avec zpalm en particulier à optimiser le temps de calcul sur une 71B.

Il y a un message où j'ai d'ailleurs repris le code assembleur qui était réalisé par le JPC pour faire un calcul sur un intervalle (les 10000 premiers sont calculés alors en 7 minutes).

Quant à trouver une stratégie pour optimiser alors le traitement sur cet intervalle, why not ? Ca ressemble fort alors à ce qu'on a fait sur le MRA n°2 et je sens bien l'utilisation de tableaux de valeurs pour limiter les redondances de calculs.

Du coup, ce serait bien de renommer ce fil en MRA n°3, et on repart à l'aventure.

[C.Ret]

Exellente idée, c'est bien un M.R.A !!

Et oui, nous allons certainement nous servir des execellents algorithmes développés en juin 2014 pour accélérer tout cela.

Et même si l'on refait un peu la même chose, une piqûre de rappel c'est toujours un bon vaccin pour traiter notre maladie !!!

[gege]

Bonjour,
Intuitivement je verrais bien un tableau sont les cases seraient vides initialement et qu'on remplirait avec le temps de vol. Au bout de quelques trajectoires, pas mal de cases seraient remplies...
Lorsqu'on avance d'une étape et qu'on tombe sur une case non vide, inutile d'aller plus loin car on peut calculer tous les prédécesseurs.
Ok c'est incompréhensible... je vous mitonnerai un petit code.
A+
G.E.

[spacemax]

Bonjour,

Voici mon optimisation réalisée sur mon portable avec rfo basic mais c'est tout a fait faisable sur un pocket a condition d'avoir suffisamment de ram pour gérer un table de 1000 entiers. Les lignes commençant par ! Sont des commentaires.

REM Start of BASIC! Program
a=1:b=1:valmax=1:volmax=0
dim v[1000]
t=time()
while b<>1000
a=b:vol=0
!--print a;" ";
while a<>1

if a<1000 then
if v[a]<>0 then
vol=vol+v[a]:a=1:goto suite
endif
endif

if a/2=int(a/2) then
a=a/2
else
a=((3*a)+1)/2:vol=vol+1
endif
!--print a;" ";
vol=vol+1
suite:
repeat
!--print
v=vol
if vol>volmax then
volmax=vol:valmax=b
print valmax;" ";volmax
endif
b=b+1
repeat
print valmax;" ";volmax
print " Terminé ";time()-t

Avec la table, il faut 2'5'' et sans 13'1''
Je testerai sur mes pockets pour les temps.

[spacemax]

Testé sur psion lz:
Avec table : 4 minutes 12 secondes
Sans table : 35 minutes

Ça fait un beau gain. Reste a adapter pour un intervalle [a,b] mais je pense qu'on perdra progressivement le gain car plus a est élevé, plus le nombre de valeurs antérieures aussi...

[C.Ret]

Intuitivement je verrais bien un tableau sont les cases seraient vides initialement et qu'on remplirait avec le temps de vol. Au bout de quelques trajectoires, pas mal de cases seraient remplies...

C'est le principe auquel je pensais.

La difficulté est que sur mes SHARP PC-1211, SHARP-PC-1360, ma TI-74 BASICALC ou mon HP-41C dopée de deux modules RAM, je ne peux pas mémoriser les 1000 valeurs.

Il me faut donc trouver une stratégie ad'hoc pour que rapidmeent les "valeurs inconnues " se remplissent.

Par chance, mon Commodore C128D va pouvoir m'aider, car ces 64 ko réservé aux variables devrais permettrent quelques expérimentations.

Dans un premier temps, observons comment les suites de suites de Syracudse se ramifient. (Eh! Oui, encore une fois je vais faire de la botanique d'arbres, de la sylviculture pour arbres à valeurs entières.

Code : Tout sélectionner

0:1:2:3::4::5::6:::7:::8:::9:::10:::11:::12:::13::::14::::15::::16:::::17:::::18:::::19::::::20...

1─2─4─8─16─32─64─128─256─512─1024─2048─4096─8192─16384─32768─65536─131072─262144─524288─1048576---
    └(1) │     '       '        '         '          '           '             '              '
         └──5─10──20──40──80──160──320──640─1280──2560──5120─10240──20480──40960──81920──163840---
               │       │        │         '          '           '             '              '
               │       │        └───53──106──212───424───848──1656───3312───6624──13248───26496---
               │       │                  │          '
               │       │                  └───35────70───140───280────560───1120───2240────4480---
               │       │                             │           '             '              '
               │       │                             └────23────46─────92────184────368─────736---
               │       │                                         │             '              '
               │       │                                         └─────15─────30─────60─────120---
               │       │
               │       └──13───26───52──104──208───416───832──1664───3328───6656──13312───26624---
               │           °         │         '           '            '             '
               │                     └───17───34────68───136───272────544───1088───2176────4352---
               │                               │           '            '             '
               │                               └────11────22────44─────88────176────352─────704---
               │                                           │            │             '
               │                                           │            └─────29─────58─────116---
               │                                           │                          │
               │                                           │                          └──────19---
               │                                           │                                  ° 
               │                                           └─────7─────14─────28─────56─────112---
               │                                                 °             │              '
               │                                                               └──────9──────18---
               │
               └───3───6──12───24───48───96──192───384───768──1536───3072───6144──12288───24576---

On voit que l'Arbre à Syracuse possède un certain nombre de branches subsidiaires commençant par un nombre impair et s'étendant à l'infinie par des rameaux tous composés d'éléments pairs.
Tous les éléments de ces ramaux ne sont pas fertiles et ne peuvent donner naissance à un éventuel nouveau rameau dont le bourgeons est impair pouis tous les éléments suivants pairs. J'ai noté à l'aide d'une petite quote ['] les point méristématique qui pourraient donner naissance à des rameaux subsidiaires.

Il y a donc certainement moyen de tirer profit de cette structure de l'Arbre Syracuse afin d'en faciliter la mémorisation (ou mémonization) sans avoir à mobiliser un registre mémoire pour toutes les valeurs.
Même, si j'en convient, cette solution, quand elle est accessible est certainement la plus simple et la plus efficace (et donc la plus rapide). La vitesse s'obtenant ici grâce à un important espace mémoire.

Mais comment faire, si l'on ne peut mémoriser que 100 ou 200 éléments ?

[spacemax]

Hello C.Ret

J'avoue que là c'est de l'art abstrait. L'arbre, les ramifications, les bourgeons, rien ne luit là haut !!!

Peux-tu expliquer ton schéma et comment le lire.
Escomptes-tu mémoriser les vols ?

[C.Ret]

Euh! Oui pardon, je n'ai pas expliqué mon tableau de nombres.

Il s'agit en fait très simplement d'une représentation des Suites de Syracuse sous la forme d'un arbre.

Dans cette figure, les nombres sont rangés de droite à gauche selon la relation de récurrence de la suite.
La première ligne marquée 0::::1::::2::::3:::: indique simplement le temps de vol.

Les nombres pairs sont liés à leur voisin divisé par deux et représentés sur la même ligne.(c'est à dire la même branche)
Par contre, les nombres impairs produisent un noeud, car leur successeur dans la suite de Syracuse est un nombre pair situé sur une autre ligne (une autre branche).
Les nombres impairs sont donc chacun à l'origine d'une sous-branche, c'est à dire un rameau qui lui aussi sera constitué uniquement de nombres pairs multiples du nombre impair iniitateur du rameau.


Par exemple, on peut déterminer d'après cette figure la Suite de Syracure issue du nombre n=14 en parcourrant l'arbre dessiné vers la gauche.
On obtient :

Code : Tout sélectionner

0:1:2:3::4::5::6:::7:::8:::9:::10:::11:::12:::13::::14::::15::::16:::::17:::::18:::::19::::::20...

1─2─4─8─16---
         └──5─10──20──40---
                       └──13───26───52---
                                     └───17───34---
                                               └────11────22---
                                                           └─────7─────14---
                                           

[A B] = 14 - 14
14:              14  7 22 11 34  17 52  26 13 40 20 10 5 16 8 4 2 1 4 2 1 4 ...      TOF:17  MAX:52 

Le nombre 14 fait partie du rameau généré par le bourgeon 7 lui-même rattaché au rameau issue de 11 au niveau du noeud 22.
Le rameau 11 prend naissance au noeud 34 du rameau issu de 17 qui lui-même se rattache au noeud 52 du rameau issu du bourgeon 13.
Le noeud 52 est le noeud de valeur la plus élevée et sera donc l'altitude maximale du vol provenant de 14.
Pour atteindre le bourgeon du rameau il faut passer par l'intermédiaire 26.
Le rameau 13 se rattache au rameau issu de 5 au niveau du noeud 40
Le bourgeon 5 n'est pas atteind directement, il faut passer par les feuilles intermédiaires 20 et 10.
Puis le rameau est lié au noeud 16 qui conduit à la racine initiale 1 par l'intermédiaire des intermédiaire 8, 4 et 2.

Le temps de vol de la Suite de Syracuse issue de 14 est donc de 17. Son altitude maximale est 52.


En conclusion: cette représentation des nombres permet, donc de déterminer un certain nombre des suites de Syracuse.
Mais, elle me sert surtout à figurer la façon dont les suites se dessinent et s'organisent au travers de l'Arbre de Syracuse.