Problème 5_ 2

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) = (5 x + 1) / 2	pour x = 1 mod 2	ou bien en posant x = 2 n + 1 :	2 n + 1 → 5 n + 3

Illustration graphique

On peut suivre en rose la boucle 1 – 3 – 8 – 4 – 2 – 1

En rouge les points de la droite y = n / 2

En vert les points de la droite y = ( 5 n + 1 )/ 2

En jaune les points de la droite y = n pour renvoyer les points de (Oy) sur (Ox)

Itération de l’algorithme

En dédoublant n en 2 n et 2 n+1 on obtient les formules de F²

4 n	→	n + 0
4 n + 2	→	5 n + 3
4 n + 1	→	52 n + 8
4 n + 3	→	5 n + 4

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

On a ici une autre façon de révéler la boucle 1– 3 – 8 – 4 – 2 - 1 pour n = 0 dans F ⁵ .

La chasse aux boucles :

Parmi les lignes de F ⁵ on relève :

25 n +1	→	52 n + 1
25 n +3	→	52 n + 3
25 n +8	→	52 n + 8
25 n +4	→	52 n + 4
25 n +2	→	52 n + 2

Pour n= 0 on voit apparaître la boucle 1 – 3 – 8 – 4 – 2 – 1

En notant que 2⁵ – 5² = 7, le rapport F(x) / x = 5² / 2⁵ + 7 a / 32 x , pour a prenant chaque valeur de la boucle . De plus f(a) / a vaut 1 .

De ce fait 1 apparaît comme valeur approchée par excès de 5² / 2⁵

Pour révéler une éventuelle nouvelle boucle il convient d’examiner les puissances de 5 légèrement inférieures à une puissance de 2 autrement dit la proximité du rapport k log(5)/log(2) avec un entier :

1	2	3	4	5	6	7
2,32	4,64	6,97	9,29	11,61	13,93	16,25

Pour k=3 on a 6,97 qui est très légèrement inférieure à 7 ce qui illustre la proximité de 5³ = 125 avec 2⁷ = 128

On a ici 2 boucles 13 – 33 – 83 – 208 – 104 – 52 – 26 – 13 et 17 – 43 – 108 – 54 – 27 – 68 – 34 – 17

F(x)/x = 53/27 + 3 a / 27 x

ainsi F(a)/a vaut 1 pour chaque valeur des 2 boucles.

On retrouve des situations favorables pour 5⁹ et 2²¹ puis 5³¹ et 2⁷²

Un algorithme par conjugaison

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 → 10 n + 3 = 2(5 n +1) + 1

2 (4 n + 3) + 1 → 5 (4 n + 3) + 3 → 10 n + 9 = 2 ( 5 n + 4 ) + 1

2 ( 8 n + 5) + 1 → 5 (8 n + 5 ) + 3 = 40 n + 28 → 20 n + 14 → 10 n + 7 = 2( 5 n + 3) + 1

2 (16 n + 1) + 1 → 5 ( 16 n + 1 ) + 3 → → → 2( 5 n ) + 1

2 ( 16 n + 9 ) + 1 → 5 ( 16 n + 9 ) + 3 → → → → 5 n + 3 ← 2 n + 1

le même « n » code les homologues 2 n + 1 et 5 n + 3 .( 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	→	5 n + 1
4 n + 3	→	5 n + 4
8 n + 5	→	5 n + 3
16 n + 1	→	5 n
16 n + 9	→	n

La boucle 1 – 3 – 8 – 4 – 2 – 1 devient la boucle 0 – 1 – 0

La boucle 13 – 33 – 83 – 208 – 104 – 52 – 26 – 13 devient la boucle 6 – 16 - 41 – 2 – 6

On remarque 2 est le code de 5 qui n'est pas explicitement dans la boucle initiale.

La boucle 17 – 43 – 108 -54 – 27 – 68 – 34 – 17 devient 8 – 21 – 13 – 8

Cet algorithme peut s'itérer mais pas se conjuguer de nouveau

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

On distingue plusieurs composantes connexes:En particulier les antécédents de 1 ,ceux de 13 ceux de 17. et de nombreuses branches de divergence vers l'infini.

Début de l’arbre des antécédents de 1 . Les premiers antécédents sont 2, 4, 8

Les couleurs illustrent la classe modulo 5 des entiers cités.

8
3			16
1	6		32
12			64
24			128
48			51	256
19		96	102	512

Pour explorer l'arbre des suites possibles on peut dérouler l'algorithme à partir des multiples impairs de 5 et regrouper les suites qui débouchent sur les boucles déjà détectées ou sur des suites qui semblent diverger vers l'infini

boucle de 1 : {15, 65, 105, 155, 175 ,...}

boucle de 13: {5, 185, 215, 245, …}

boucle de 17 : {275, ..}

Branche de 35 : {35, 115, 135, 225, 235, …}

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

5 n + 3	← 2 n + 1
10 n + 6
20 n + 12
40 n + 24
80 n + 48 = 5 ( 16 n + 9 ) + 3	← 2( 16 n + 9 ) + 1
16k ( 5 n + 3 ) = 5 ( 16k n + 3 (16k – 1) / 5) + 3	← 2 ( 16k n + 3 (16k – 1)/5 ) + 1

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

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

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

On pose

u : 2 n + 1 → 5 n + 3

puis v : 4 n + 3 → 5 n + 4

puis w : 8 n + 3 → 5 n + 2

et enfin x : 16 n + 3 → 5 n + 1

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

Un rameau relie un multiple impair de 5 à un entier divisible par 16 par la composée d’un nombre quelconque d’applications u_, v,..,x

Remarquons au passage que l'ensemble des rameaux ne recouvre pas l'ensemble de toutes les suites : les images successives de 275 se perdent dans la boucle 17 sans jamais aboutir sur un multiple de 16 !

Le plus court part d’un impair multiple de 5 pour aboutir à un multiple de 16

Cela se produit pour 160 n + 115 → 400 n + 288 soit 5 ( 32 n + 23 ) → 16 ( 25 n + 18) ( qui a pour image 25 n + 18 ce dernier étant un marqueur du rameau court)

En multipliant ce marqueur par 16⁵ on retrouvera un nouveau marqueur : 25 x 16⁵ n + 18 x 16⁵ = 25 ( 16⁵ n + 18 (16⁵ -1 )/25 ) + 18

Le marqueur qu’on peut écrire 5 ( 5n + 3) + 3 est lui même l’image de 2 ( 5n + 3) + 1 qui appartient à la même composante connexe que le marqueur initial.

pour n = 0 on trouve 16*18 = 288 qui est l'image de 115 . On est dans la composante connexe de 35 :

pour n = 34078 on a 13631488 (13*16⁵) qui est l’image de 5452595 .On est dans la composante connexe de 13 :

remarque :le rameau qui commence à 35 se termine par 19894208 = 16* 1243388

On aurait pu dire qu’il est associé à 2x3+1 = 7 qui est bien dans la composante connexe de 35.

Pour n= 1 ou n= 2 on est dans la composante connexe de 17.

Pour n= 3 ou n= 4 on est dans la composante connexe de 75

Il est légitime de se demander si la liste très longue des composantes connexes est illimitée !?

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

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

En posant p(k) = 5^k et en remontant dans l’arbre par une multiplication par 16^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 + 5 a + a² h et notons que 16 est égal à 1 modulo 5

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

16 ^p(k+1) = (16^p(k))⁵ = 1 + 5 p(k) H + (p(k) H)² h avec 5 p(k) = p(k+1) d’où :

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

Revenons au produit de :5^k n + d par 16^p(k) :

16^p(k). 5^k n + d. 16^p(k) = 5^k ( 16^p(k) n ) + (16^p(k) – 1) d + d

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

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

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

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

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

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

C'est une généralisation de ce qui a été étudié précédemment concernant les rameaux courts.

Les tableaux suivants représentent les antécédents de l’entier situé en haut à gauche.

En dessous on trouve une branche féconde formée par le produit de ce nombre par un puissance de 16 (qui vaut 1 modulo 5)

Horizontalement on retrouve des rameaux interrompus par l’apparition d’un multiple impair de 5.

Il n’y a plus en amont, que le produit de ce nombre par des puissances de 2 qu’on a fait le choix de ne pas représenter.

Dans la première colonne les applications se reproduisent avec une période de 1, dans la deuxième colonne avec une période de 5 ensuite avec une période de 25 qu’on se contentera d’imaginer

les couleurs permettent d’identifier au moins en partie les motifs qui se reproduisent

Les boucles assurent un développement infini vers la droite et en particulier un point de départ pour chaque colonne d’applications.

1	← u	3	← w	1	← u	3
16	← u	51	← u	163	← w	65
256	← u	819	← x	655	← p	0
4096	← u	13107	← v	20971	← u	67107
65536	← u	209715	← p	0	← p	0
1048576	← u	3355443	← w	1342177	← v	2147483
16777216	← u	53687091	← u	171798691	← u	549755811
268435456	← u	858993459	← x	687194767	← v	1099511627
4294967296	← u	13743895347	← v	21990232555	← p	0
68719476736	← u	219902325555	← p	0	← p	0
27	← v	43	← w	17	← v	27
432	← v	691	← u	2211	← u	7075
6912	← v	11059	← x	8847	← v	14155
110592	← v	176947	← v	283115	← p	0
1769472	← v	2831155	← p	0	← p	0
28311552	← v	45298483	← w	18119393	← w	7247757
452984832	← v	724775731	← u	2319282339	← x	1855425871
7247757312	← v	11596411699	← x	9277129359	← x	7421703487
115964116992	← v	185542587187	← v	296868139499	← x	237494511599
1855425871872	← v	2968681394995	← p	0	← p	0
13	← w	5	← p	0	← p	0
208	← w	83	← w	33	← w	13
3328	← w	1331	← u	4259	← x	3407
53248	← w	21299	← x	17039	← x	13631
851968	← w	340787	← v	545259	← x	436207
13631488	← w	5452595	← p	0	← p	0
218103808	← w	87241523	← w	34896609	← x	27917287
3489660928	← w	1395864371	← u	4466765987	← v	7146825579
55834574848	← w	22333829939	← x	17867063951	← u	57174604643
893353197568	← w	357341279027	← v	571746046443	← w	228698418577
9	← x	7	← v	11	← u	35
144	← x	115	← p	0	← p	0
2304	← x	1843	← w	737	← v	1179
36864	← x	29491	← u	94371	← u	301987
589824	← x	471859	← x	377487	← v	603979
9437184	← x	7549747	← v	12079595	← p	0
150994944	← x	120795955	← p	0	← p	0
2415919104	← x	1932735283	← w	773094113	← w	309237645
38654705664	← x	30923764531	← u	98956046499	← x	79164837199
618475290624	← x	494780232499	← x	395824185999	← x	316659348799