Depuis l'apparition de l'algorithmique, la suite de Syracuse, dont on ne parlait jamais est devenue incontournable, et je l'ai redécouverte et ses propriétés mystérieuses sont toujours inviolées.
Ce problème ma donné envie d'examiner le processus un peu mieux.
Déjà, grâce à l'informatique on a examiné un grand nombre de cas ce qui permet d'obtenir de nouveaux records de temps de vol qui forment une suite croissante et qui tend vers +inf
(car T(2^N)=N).
par exemple T(6171)=261, T(26623)=307, T(52527)=335, T(77031)=350 et T(63728127)=949.
Pour aller un peu plus loin, j'ai essayé de voir un peu se qui se passe en travaillant en binaire puisque diviser par 2, c'est diviser par"10" et que multiplier par 3, c'est multiplier par "11".
On exclut de l'étude les puissances de 2 et on va même considérer que U est initialisé par un nombre impair.
3 situations se présentent:
situation 1: U se termine par k "1"(k>1); 3U+1 se termine par 011..10 (k-1) "1" et après l'opération U/2, U se termine par k-1 "1" et a augmenté; si enfin U se termine par 01,
3U+1 se termine par 00 et il y aura donc une opération U/4 qui stoppe le processus de croissance.
En résumé, il y aura k-1 opération de croissance 3U+1->U/2 et une dernière opération
3U+1->U/4. ce n'est pas la situation idéale!
Situation 2: U se termine par 1010...101 (2k+1 chiffres, k>0). Commençons par le cas U=10101...101,
seul cas qui conduit à une puissance de 2; 3U=1111..11 avec 2k+2 "1" et 3U+1=2^(2k+2); remarquons que l'on obtient une puissance de 2 paire et que donc une puissance de 2 impaire ne peut pas arriver.
Sinon, 3U se termine par 2k+1 "1" et 3U+1 par 2k+1 "0" et on aura U/2^(2k+1); situation beaucoup plus intéressante.
Situation 3: U se termine par 100..001(k "0", k>1), 3U se termine par 10..011 (k-2 "0") et 3U+1
Par 100 donc l'opération suivante sera U/4; si k-2=0, un autre cycle recommencera; si k-2=1, U finira par 010 et 3U+1 finira par 000 donc une opération U/8; encore une situation intéressante!
Longueur de l'écriture binaire de U, L(U):
2 cas sont possibles: U commence par 11 ou U commence par 10
si U commence par 11, 3U commencera par 10 et on aura L(3U)=L(u)+2;
le cas 3U =10111...1111 n'est possible que si on initialise U par cette valeur, sinon si on utilise le critère de divisibilité par
Si U commence par 10, 3U commence par 11 et L(3U) =L(U)+1 sauf si U commence par 1011 où L(3U)=L(U)+2 et commence aussi par 10.En fait on a toujours au pire après l'opération U->3U+1
->U/2 une augmentation de 1 ou de 0 et si l'on teste quelques nombres, on voit que l'évolution de L(U) est lente.
En terme de valeurs, U étant grand (les 10^7 premiers nombres, au moins, ayant été testés), on peut considérer qu'une opération 3U+1-> U/2 se traduit, en valeur par une multiplication par 1,5 et qu'une division par 4 correspond à une multiplication par 3/4, la situation 1 donne une multiplication par 1,5^k-1x3/4, la situation 2 correspond à une multiplication par3/2k+1 et la situation 3 à une multiplication par 3/(k/2).
Donc, si on considère qu'initialiser la suite par un nombre U génère un processus aléatoire (ce qui n'est pas faux!), les trois situations sont équiprobables et si on prend k=4, on aura comme situation +1,5^3x4x4x3/2^5x3/2^3=0,89, donc sur le plan aléatoire une décroissance, mais c'est de la mathématique-fiction!
A la recherche d'une puissance de 2: commençons par traiter le cas 101(5) qui donne après l'opération 3U+1, 10000 (16); 101 ne peut être issu d'une opération 3U+1, donc ne peut arriver qu'après une suite de division par 2, donc d'un nombre 1010..0, mais ce nombre doit être issu d'une opération 3U+1 donc 3U=10011..1 doit être multiple de 3, ce qui implique que la suite de "1" doit être impaire (critère de divisibilité par"11"), donc si le processus se termine ainsi, c'est qu'on arrivera soit à 10, soit qu'on arrivera à 40 ou 160 etc....
Le cas suivant est U= 10101 , qui ne peut provenir d'une opération 3U+1 puisque U-1 (20) n'est pas un multiple de 3; peut il provenir de 3U+1=1010100..0 qui donne 3U=10100111.1 qui ne sera jamais un multiple de 3! Donc 2^6 n'apparaîtra jamais!
Pour les cas suivants la seule possibilité d'apparition d'une puissance de 2 après une opération 3U+1 est que 3U s'écrive 1010..10011 et que ce nombre soit divisible par 3, ce qui implique que le premier nombre qui convient est 101010011(soit 675), U+1=101010100 qui divisé par 4 donne U=1010101 et après l'opération 3U+1-> 2^8( remarque, avant d'obtenir 3U, on obtient U=1110001, ce qui ne doit pas être courant).
pour l'étape suivante,il faut ajouter 101010 pour avoir un nombre divisible par 3, ce qui donne pour 3U,101010101010011 et U=10001110001; il se dégage quelque chose , mais qui doit être rare; sinon 3U+1 donne 101010101010100 puis après l'opération U/4, 3U+1 fournit 2^14 (16384)
La prochaine puissance de 2, issue d'une opération 3U+1 ne pourra être que 2^20; quand est il des autres puissances paires de 2?
Pour l'instant, peuvent apparaître 2^4, 2^8 puis les puissances de la forme 2^(8+6k) .
Prenons 2^10 comme exemple; 2^10 ne peut apparaître que si 3U+1= 10101010100...0 arrive, donc si 1010101011..11 est un multiple de trois; ce qui est impossible!
Si l'on prend 2^12 , il faut que 101010101010100...00-1 soit 1010101010111..1 soit un multiple de 3, se qui est possible si le nombre de "1" terminaux est impair.
En résumé, les puissances impaires de 2 sont hors jeu; quand au autres elles ne font que de rares apparitions; en gros une puissance de 2 sur trois peut arriver.
Voilà les résultats de mon petit bricolage; toute remarque,tout commentaire,tout résultat théorique ou numérique seront les bienvenus, surtout si vous êtes aussi intrigués par ces suites diaboliques,
merci à tous!
PS: cette petite réflexion permet de trouver facilement des situations intéressantes. Pour U=1137, T(U)=18,pour U=1138, T(U)=57; Pour U=1535, T(U)=60,et pour U=1536, T(U)=16; une suite vraiment pas monotone.
On peut aussi demander aux élèves, après le calcul de U d'afficher U puis pause, ils verrons rapidement l'évolution de la suite et on peut leur demander de choisir dix fois un nombre impair compris entre 10001 et 99999 et de compter combien de fois apparaissent les nombres 3, 6,12,21,24,42,48,84; si il y a 35 élèves, ça fera 350 expériences. :we: