Suite de Syracuse :Problème 3_2 compressé

Avertissement : le propos n'est pas d'apporter la preuve qu'à force de diviser un entier par 2 ou à défaut de le multiplier par 3 et d'ajouter 1 on finit toujours par rallier 1

L'apparent chaos qui ressort du suivi d'une suite particulière cache un ordre subtil qui régit l'ensemble de toutes les suites possibles

Pour tourner autour du pot on examinera les algorithmes apparentés et les conditions d'apparition de boucles.

D'autres membres de la famille :

En inversant le rôle de 2 et 3: Problème 2_3

En prolongeant vers les négatifs en changeant de signe : Problème 3_2 moins

En remplaçant 3 par 5 : Problème 5_2

Par itération ou conjugaison d'autres algorithmes apparentés sont définis.

Les algorithmes sont associés à une partition finie de IN dont une ligne s'écrit : a n + b → n

Ici pour le problème 3_2 la première ligne s'écrit : 2 n → n

Problème 3_2 compressé :

U est une suite récurrente.

Soit à définir l’application F dans IN telle que U_n+1 = F(U_n)

La forme explicite de F se décompose en  :

F0(x) = x/2	pour x = 0 mod 2	ou bien en posant x = 2 n (n entier naturel) :	2 n + 0 → n
F1(x) = (3 x + 1) / 2 = 3/2(x + 1) -1	pour x = 1 mod 2	ou bien en posant x = 2 n + 1 :	2 n + 1 → 3 n + 2

On voit déjà que 0 est un point isolé et que 1, 2 forment une boucle

Illustration graphique

En rouge les points de la droite y = x / 2 ,en vert ceux de la droite y = ( 3x + 1) / 2 et en bleu la droite y = x

On peut déjà remarquer que 0 est un point isolé et que 1 et 2 forment une boucle.

Itération de l’algorithme

En dédoublant n en 2 n et 2 n+1 on obtient les formules de F² qui correspondent aux 4 composées de 2 des applications F₀ et F₁

4 n	→	n + 0	F2(x) = x / 4
4 n + 2	→	3 n + 2	F2(x) = ( 3 x + 2 ) / 4
4 n + 1	→	3 n + 1	F2(x) = ( 3 x + 1 ) / 4
4 n + 3	→	9 n + 8	F2(x) = ( 9 x + 5 ) / 4

On peut définir de proche en proche les formules de F^k qui comprend 2^k lignes.

On y trouvera en particulier :

2k n	→	n + 0	Fk(x) = (1/2k) x
2k n + 2k - 1	→	3k n + 3k - 1	Fk(x) = (3/2)k (x + 1) - 1

Algorithme conjugué

On profite ici que dans l'arbre des suites possibles un impair n'est jamais très loin d'un autre impair !

Examinons les enchaînements suivants (entre les nombres impairs de la suite) :

2 (2 n +1) + 1 → 6 n + 5 = 2(3 n +2) + 1

2 (4 n ) + 1 → 12 n + 2 → 6 n + 1 = 2 ( 3 n ) + 1

2 ( 4 n + 2) + 1 → 12 n + 8 ) → → 3 n + 2 ← 2( n ) + 1

le même « n » code les homologues 2 n + 1 et 3 n + 2 .( Le 2° étant l'image par F₁ du premier)

si on pose u(n) = 2 n + 1 on a :

	u		Fk		u-1
a n + b	→	2 ( a n + b ) + 1	→	2 ( c n + d ) + 1	→	c n + d

On définit K par u^-1 o F^k o u d'où la dénomination « conjugué »

Ces codes s'enchaînent selon l'algorithme K suivant :

2 n + 1	→	3 n + 2
4 n	→	3 n
4 n + 2	→	n

Cet algorithme peut être lui-même itéré

Si à n on substitue respectivement 2 n + 1 , 4 n ,et 4 n + 2 on trouvera dans l’ordre croissant des termes constants les 9 lignes définissant K²

16 n	→	9 n
8 n + 1	→	3 n
16 n + 2	→	3 n
4 n + 3	→	9 n + 8
8 n + 4	→	9 n + 5
8 n + 5	→	9 n + 6
8 n + 6	→	3 n + 2
16 n + 8	→	3 n + 1
16 n + 10	→	n

Examinons la suite qui démarre à 27 :

27	41	62	31	47	71	107	161	242	121
182	91	137	206	103	155	233	350	175	263
395	593	890	445	668	334	167	251	377	566
283	425	638	319	479	719	1079	1619	2429	3644
1822	911	1367	2051	3077	4616	2308	1154	577	866
433	650	325	488	244	122	61	92	46	23
35	53	80	40	20	10	5	8	4	2

Examinons la suite conjuguée qui démarre à 13

13	20	15	23	35	53	80	60	45	68
51	77	116	87	131	197	296	222	55	83
125	188	141	212	159	239	359	539	809	1214
303	455	683	1025	1538	384	288	216	162	40
30	7	11	17	26	6	1	2	0

Si on utilise K² on n’a plus qu’un terme sur 2 de la suite précédente. On a moins de terme mais on allonge le temps de calcul de chacun !

La chasse aux boucles

Pour a = 1 ou 2 , F²(a) = (3 a + a) / 4 = a

soit F²(a) / a = 3/4 + 1/4 = 1 et 3/4 apparaît comme valeur approchée par défaut de 1 par défaut.

Est-il possible de retrouver des situations comparables pour des puissances supérieures de F avec un coefficient de proportionnalité proche de 1

Si on compose h applications F_i dont k fois F₁ on a des lignes de la forme 2^h n + a → 3^k n + b dont le coefficient de proportionnalité est 3^k / 2^h

Le tableau suivant permet de débusquer h pour viser un coefficient proche de 1

k	1	2	3	4	5
k*log(3)/log(2)	1,58	3,17	4,75	6,34	7,92

Pour k=1 l’arrondi de 1,58 est 2 et cela signifie que 2² est la puissance de 2 immédiatement supérieure à 3

Pour k = 3 on obtient 2⁵ = 32 immédiatement supérieur à 3³ = 27

Dans la définition de F⁵ on relève les 10 lignes associées à la composée de 3 fois F₁ avec 2 fois F₀

32 n + 1	→	27 n + 2	32 n + 22	→	27 n + 20
32 n + 11	→	27 n + 10	32 n + 23	→	27 n + 20
32 n + 14	→	27 n + 13	32 n + 25	→	27 n + 22
32 n + 18	→	27 n + 17	32 n + 28	→	27 n + 26
32 n + 19	→	27 n + 17	32 n + 29	→	27 n + 26

Les homologues pour n= 0 sont proches mais jamais égaux !

Pour k = 5 on obtient 2⁸ = 256 immédiatement supérieur à 3⁵ = 243

Dans les 256 formules de F⁸ si on relève les lignes correspondant aux composées de 5 foisF₁ avec 3 fois F₀ on met en évidence des couples homologues et on est conduit à la même conclusion que dans le cas précédent.

On peut craindre ou espérer qu’il n’y ait qu’une seule boucle : 1,2,1,...

L’arbre des suites possibles pour l’algorithme initial :

Esquisse de l’arbre des antécédents de 3 n + 2

3 n + 2	← 2 n + 1
6 n + 4
12 n + 8 = 3 ( 4 n + 2 ) + 2	← 2( 4 n + 2 ) + 1
4k ( 3 n + 2 ) = 3 ( 4k n + 2 (4k – 1) / 3) + 2	← 2 ( 4k n + 2 (4k – 1) / 3 ) + 1

4^k = (1 + 3)^k = 1 + 3^k + 3² h (début du développement de Newton ) d'où ( 4^k – 1 )/ 3 = k + 3² h

Remarque :2 (4^k n + 2 (4^k – 1) / 3 ) + 1 est congru à 2 n + 2 k + 1 modulo 3

Une suite de la forme 4^k n sera désignée comme une branche (féconde) de l’arbre et leurs antécédents jusqu’à un impair multiple de 3 sera baptisé rameau.

On pose u : 2 n + 1 → 3 n + 2 puis v : 4 n + 1 → 3 n + 1

Remarque : ces 2 applications sont associées à l'ordre près aux 2 premières lignes de l'algorithme par conjugaison

Un rameau relie un multiple impair de 3 à un entier divisible par 4 par la composée d’un nombre quelconque d’applications u_, v

Le plus court, part d’un impair multiple de 3 ayant pour image un multiple de 4

Cela se produit pour 24 n + 21 → 36 n + 32 soit 3 ( 8 n + 7 ) → 4 ( 9 n + 8) ( qui a pour image 9 n + 8 ce dernier étant un marqueur du rameau court)

En multipliant un marqueur par 4³ on retrouvera un nouveau marqueur

4³ ( 9 n + 8 ) = 9 ( 64 n + 56 ) + 8

Une suite particulière ne peut pas déboucher sur plusieurs boucles. L’arbre des suites possibles contient a-priori plusieurs composantes connexes.

Les antécédents des nombres composant une boucle forment une des composantes connexes de l’arbre.

Les rameaux courts apparaissent dans chaque composante connexe.

Entre 8 et 512 ( pour l’ordre naturel) qui sont des antécédents de 1 on n’est pas assuré d’être dans cette même composante

On vérifie sans peine que tous ces marqueurs sont antécédents de 1 ce qui est de nature à renforcer la conviction qu’il n’y a qu’une seule composante connexe.

Cela signifierait que toutes les suites conduisent à la boucle 1,2.

D’autres régularités dans l’arbre des suites possibles

La composée de k applications u v s’exprime par : 2^h n + b → 3^k n + d

En posant p(k) = 3^k et en remontant dans l’arbre par une multiplication par 4^p(k) on retrouvera une fraction de rameaux semblable à la précédente :

(Les entiers diffèrent mais l'enchaînement des applications est le même.)

Rappelons que pour a et h entiers ( 1+ a )³ = 1 + 3 a + a² h

Supposons que 4 ^p(k) soit congru à 1 modulo p(k)  soit : 4 ^p(k) = 1 + p(k) H (avec H entier)

4 ^p(k+1) = (4^p(k))³ = 1 + 3 p(k) H + (p(k) H)² h avec 3 p(k) = p(k+1) d’où :

4 ^p(k+1) = 1 + p(k+1) + p(k+1). p(k-1) H² h ce qui prouve que pour tout k entier, 4 ^p(k) est congru à 1 modulo p(k)

Revenons au produit de :3^k n + d par 4^p(k) :

4^p(k). 3^k n + d. 4^p(k) = 3^k ( 4^p(k) n ) + (4^p(k) – 1) d + d

avec (4^p(k) – 1) multiple de p(k) c’est à dire de 3^k d’après ce qui précède

Soit h(k) tel que (4^p(k) – 1) =3^k h(k) on obtient l’expression 3^k ( 4^p(k) n + d.h(k)) + d

autrement dit, à n, on a substitué 4^p(k) n + d.h(k)

L’antécédent de 3^k n +d qui est 2^h n + b est donc remplacé par 2^h (4^p(k) n + d.h(k) + b

ces 2 derniers termes n’étant pas dans la même classe modulo 3

On retrouvera une fraction de rameau formé des mêmes applications u,v du départ portant sur des entiers beaucoup plus grands !

Dans les tableaux suivant on retrouve dans la colonne de gauche le produit du terme initial par une puissance de 4.

On « oublie » au passage les multiples qui ne sont pas dans la classe modulo 3 du terme initial

On aurait pu au contraire ne retenir que les puissances congrues à 2 modulo 3 et n’avoir que des « u » dans la première colonne des applications.

Les antécédents d’un impair multiple de 3 sont les produits de ce dernier par une puissance de 2.

Nous faisons le choix de ne pas les afficher !

La première colonne d’applications est 1- périodique ; la 2° est 3- périodique la suivante est 3²- périodique etc

La 1° ligne d’application contient « v » indéfiniment ce qui permet de « caler » le point de départ de chaque colonne puis de proche en proche pour les autres termes

Les antécédents de 5 dans le premier tableau se retrouvent dans le second

Les couleurs permettent de repérer tout ou partie de la séquence qui se répète.

1	<-v	1	<-v	1	<-v	1
4	<-v	5	<-u	3	<-p	0
16	<-v	21	<-p	0	<-p	0
64	<-v	85	<-v	113	<-u	75
256	<-v	341	<-u	227	<-u	151
1024	<-v	1365	<-p	0	<-p	0
4096	<-v	5461	<-v	7281	<-p	0
16384	<-v	21845	<-u	14563	<-v	19417
65536	<-v	87381	<-p	0	<-p	0
262144	<-v	349525	<-v	466033	<-v	621377
1048576	<-v	1398101	<-u	932067	<-p	0
4194304	<-v	5592405	<-p	0	<-p	0
5	<-u	3	<-p	0	<-p	0
20	<-u	13	<-v	17	<-u	11
80	<-u	53	<-u	35	<-u	23
320	<-u	213	<-p	0	<-p	0
1280	<-u	853	<-v	1137	<-p	0
5120	<-u	3413	<-u	2275	<-v	3033
20480	<-u	13653	<-p	0	<-p	0
81920	<-u	54613	<-v	72817	<-v	97089
327680	<-u	218453	<-u	145635	<-p	0
1310720	<-u	873813	<-p	0	<-p	0
5242880	<-u	3495253	<-v	4660337	<-u	3106891
20971520	<-u	13981013	<-u	9320675	<-u	6213783
7	<-v	9	<-p	0	<-p	0
28	<-v	37	<-v	49	<-v	65
112	<-v	149	<-u	99	<-p	0
448	<-v	597	<-p	0	<-p	0
1792	<-v	2389	<-v	3185	<-u	2123
7168	<-v	9557	<-u	6371	<-u	4247
28672	<-v	38229	<-p	0	<-p	0
114688	<-v	152917	<-v	203889	<-p	0
458752	<-v	611669	<-u	407779	<-v	543705
1835008	<-v	2446677	<-p	0	<-p	0
7340032	<-v	9786709	<-v	13048945	<-v	17398593
29360128	<-v	39146837	<-u	26097891	<-p	0