Chaînes premières

>
Soit un ensemble E de chaînes numériques d’où est exclu zéro. Si une partie A de cet ensemble ne contient que des produits uniques, alors l’autre partie B ne contient que des chaînes premières.

- Une séquence est valide si elle contient au moins une fois le chiffre 1 pour les séquences inférieures à 4 chiffres et au plus une fois le chiffre 1 pour les séquences supérieures à 3 chiffres (séquence première triviale).

Ex : 11, 91, 199, 212, 2221, 32123 …

Séquences premières triviales remarquables :

123456789, 987654321.

- Une séquence est neutre si elle ne contient pas le chiffre 1.

Ex : 9, 89, 23456.

- Toute séquence inférieure à 1111 (11 x 11) est élémentaire.

Ex : 219.

- Toute séquence supérieure à 3 chiffres comprenant au moins deux fois le chiffre 1 est une CHAINE.

Ex : 12218777, 45411987, 21323317654.

Exception :

112345432 ou 36665435711 (qui sont des séquences).

- Seuls sont considérés les produits figurés, c'est-à-dire les produits de séquences (ou de chaînes) premières.

Ex :

1111 = 11 x 11.

11199 = 11 x 199.

1462581 = 14 x 62581 = 146 x 2581

61159119 = 6115 x 9119

Les produits quantitatifs (multiplication d’une séquence neutre par une séquence première) ne sont pas pris en compte.

Ex : 9 x 112, 987 x 991.

- Une chaîne formée de deux séquences premières de deux chiffres est dite « minimale ».

Ex : 1221, 2112, 3171, 7111.

- Une chaîne est constituée de séquences premières ajustables placées dans un certain ordre.

Ex : 4311324819851 = 431*13*2481*9851 =  431*132*481*9851 = 431*13248*19*851 = …

Ou encore de sous-chaînes premières : 324819851.

- Une chaîne est composée si elle est constituée de séquences ou de sous-chaînes premières placées dans un ordre croissant.

Ex : la chaîne précédente est composée car :

4311324819851 = 4311 (séquence première) x 324819851 (sous-chaîne première), et on a bien 4311 < 324819851.

- Une chaîne est première si elle est constituée de séquences ou de sous-chaînes premières placées dans un ordre quelconque mais non croissant (autrement dit, si elle n’est pas atteinte par un produit figuré).

Ex :

Si l’on place, dans la chaîne précédente, 4311 à la fin, on a :

3248198514311 = 32481*9851*4311 = 32481*98514*311 = 32481*985143*11 mais 32481 x 9851*4311 est encore composé (98514311 est premier et > 32481).

Si l’on place, maintenant, 4311 au milieu, on a :

32481*4311*9851 = 324814*311*9851 = 3248143*11*9851 (il est impossible de former, dans tous les sens, une suite croissante de facteurs premiers). 3248143119851 est donc une chaîne première.

Quelques (petites) chaînes premières :

9119 = 91*19

511217 = 51*12*17 = 511*217 = 5112*17

22111122 = 221*11*122 = 2211*1122.

6311417 = 631*14*17 = 6311*417 = 63114*17.

1611511411 = 16*11*51*14*11 = 16*11*511*411 = 16*115*114*11 = 161*151*1411

7711121122 = 771*11*21*122 = 771*112*1122 = 7711*12*1122

L’inversion de deux facteurs premiers successifs (produit simple) est généralement première :

11 91 → 9111

111 141 → 141111

881991 → 991881

1413121121 2111121314 → 21111213141413121121

Il y a pourtant de nombreuses exceptions :

1413 2111 → 2111 1413 = 21 x 111 x 413 (composé).

122 211 → 211 122 = 21 x 1122 (composé).

411 611 → 611 411 = 61 x 1411 (composé).

112 125 → 125 112 = 12 x 5112 (composé).

Un grand nombre de chaînes se comportent comme des chaînes premières mais n’en sont pas (chaînes pseudo-premières) :

122541451 = 122*541*451 mais 541451 est premier donc 122541451 composé car 122 x 541451.

1112111211 = 11*12*11*12*11 mais 1211 est premier donc 1112111211 composé car 111 x 211 x 1211.

9119811871 = 91*19*81*18*71 mais 9811871 est premier donc 9119811871 composé car 911 x 9811871.

Exercice : 91198118711761165115411431132112 est-il premier ?

Problème :

1)   Trouver de très grandes chaînes premières (à partir de 100 chiffres).

2)   Les chaînes premières sont-elles en nombre décroissant au fur et à mesure que la liste des produits augmente ?