Problème 3_2 moins

C’est le problème 3 _2 étendu aux entiers négatifs en changeant le signe

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

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

Le graphique permet de vérifier que 1 est un point double donc un point de convergence et que la suite 5 – 7 – 10 – 5 est une boucle. Il en existe une autre un peu plus loin.

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	→	3 n + 1
4 n + 1	→	9 n + 1
4 n + 3	→	3 n + 2

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

Il ressort de ces premières lignes que 0 est un point fixe isolé et 1 un point de convergence.

On a ici une autre façon de révéler la boucle 5 – 7 – 10 – 5 pour n = 0 dans F ³ .

La chasse aux boucles :

Parmi les lignes de F ³ on relève : 8 n + 5 → 9 n + 5, plus loin : 8 n + 7 → 9 n + 7 puis : 8 n + 10 → 9 n + 10

Les formes explicites sont F_a³ (x) = ( 9 x – a) / 8 où a vaut respectivement 5 , 7 , 10 et le rapport F_a³(x) / x vaut 1 pour x = a

1 apparaît donc comme une valeur approchée par défaut de 9/8

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

1	2	3	4	5	6	7
1,58	3,17	4,75	6,34	7,92	9,51	11,09

7 log(3) / log(2) étant légèrement supérieur à 11 , 3⁷ est « légèrement » supérieur à 2¹¹

Dans la définition de F¹¹ on retrouve 11 lignes de la forme 2¹¹ n + a → 3⁷ n + a avec a prenant les valeurs 17, 25, 37, 55, 82, 41, 61, 91, 136, 68, 34 d’où la boucle

Un algorithme par conjugaison

examinons les enchaînements suivants :

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

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

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

Si x = 2 n +1 le paramètre n sert de code à x ainsi qu’à la relation entre x et F(x) . Les codes s’enchaînent selon l’algorithme suivant :

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

A partir de 8 on a : 8, 12, 18, 27, 20, 30, 45, 11, 8 qui sont les codes de 17, 25, 37, 55, 41, 61, 91, 23 .

Le dernier 23 est l’image réciproque de 34.

La recherche d’une nouvelle conjugaison se heurte à l’apparition d’une infinité de lignes

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

On distingue 3 composantes connexes Les antécédents de 1 ,ceux de 5 et ceux de 17. On ne peut exclure l’existence d’autres composantes connexes.

Début de l’arbre des antécédents de 1

1
2					1
4
8				3
16				6
32		11		12
64		22		24
128	43	44	15	48

Début de l’arbre des antécédents de 5

5
10
20			7
40			14			5
80		27	28
160		54	56		19
320	107	108	112		38	13
640	214	216	224	75	76	9

Début de l’arbre des antécédents de 17

17
34
68					23
136					46
272	91				92		31
544	182		61		184		21
1088	364		122	41	368	123	42
2176	728	243	244	82	736	246	84

En gras les antécédents de 17 de la boucle.

Les antécédents des multiples de 3 sont des multiples de 3 et constituent des branches mortes de l’arbre. Ex 21, 42, 84,..

Les antécédents des multiples de 3 plus 2, n’ont qu’un antécédent leur doubles

Les antécédents des multiples de 3 plus 1 ont 2 antécédents : leur double (en dessous) et l’antécédent par F₁ (à droite)

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

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

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

Ainsi 2 (4^k n + ( 4^k - 1)/3 ) + 1 est congru à 2 n + k + 1 modulo 3

Dans une suite de trois lignes bleues à gauche on a un antécédent vert à droite

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.

Si on pose u telle que 2n + 1 → 3 n + 1 et v telle que 4 n + 3 → 3 n + 2 un rameau relie un multiple impair de 3 à un entier divisible par 4 par la composée d’un nombre quelconque d’applications u ou v

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

Autrement dit : 24 n + 3 --> 36 n + 4.

Pour n = 0 on retrouve 3 et 4 dans les antécédents de 1

Par ailleurs comme 36 n + 4 → 18 n + 2 → 9 n + 1 ce dernier est un marqueur de ces rameaux les plus courts.

Sur une même branche on retrouve un tel marqueur en multipliant par 4³ =64

64 (9 n + 1) = 9 _x 64 + 63 + 1 = 9 ( 64 n + 7 ) +1

En donnant à n des valeurs entre 1 et 6 on n’est plus nécessairement sur la même composante connexe de l’arbre des suites :

10 → 5

19 → 28 → 14 → 7 → 10 → 5

28 → 5

37 → 55 → 82 → 41 → 61 → 91 → 136 → 68 → 34 → 17

46 → 23 → 34 → 17

55 → ...17

et avec 64 on revient aux antécédents de 1

On n’a pas prouvé ici qu’il n’y a pas d’autres composantes connexes à l’arbre des suites possibles

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

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

(h – k correspondant au nombre d’applications u)

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 :

Rappelons que pour a et h entiers ( 1+ a )³ = 1 + 3 a + a² h et notons que 4 est égal à 1 modulo 3

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 et v du départ portant sur des entiers beaucoup plus grands !