Les nombres premiers... Le cœur de l'arithmétique, où existent le plus grand nombre de conjectures irrésolues, dont l'hypothèse de Riemann, au coeur de la cryptographie et des avancées technologiques... Mais cela reste également un moyen pour tout amateur de graver son nom dans la roche, en cherchant les plus jolis nombres premiers, ou les plus jolis assemblages de nombres premiers !
Ca ne sert à rien, certes, mais c'est joli... Et puis, comment peut-on être si sûr que cela ne servira jamais à rien ?

Nombres premiers composé seulement de 1, nombres premiers symétriques ou nombres premiers qui ne craignent pas de se faire couper en morceaux...
Tant que l'on peut imaginer un motif original de nombre et qu'il n'y a aucune raison valable pour qu'ils ne soient pas premiers, alors, on en trouvera des premiers ! Pas très mathématique comme énoncé, mais très souvent vérifié !

Les rep-units
Un nombre repunit est un nombre qui s'écrit seulement avec des 1. Par exemple, 1, 11 ou 1111111111111111111 (que je vais plutôt noter (1)19) sont des repunits. Mais lesquels sont premiers ?

Jusqu'à présent, on ne connait que 5 repunits premiers : 11, (1)19, (1)23, (1)317 (Williams - 1978) et (1)1031. (Williams et Dubner - 1985). Pour tous les autres n inférieurs à 30 000, il n'y a pas de repunits premiers. Après, les calculs deviennent un brin compliqués...

Pour limiter les recherches, on a quand même quelques petits théorèmes sur les repunits.
* Déjà, on se pose la question de la primalité des (1)n, mais quand est-il de la primalité des k...k(n) avec k un autre chiffre ? Là, c'est pas compliqué de voir que (k)n>1=k×(1)n , pas de nombres premiers fabriqués avec un seul chiffre autre que le 1 !
* Maintenant, pour les repunits, on sait que 1...1(n) ne peut être premier que si n est premier. Prenons par exemple 111 111 (n=6=3×2). On trouve facilement que 111 111 = 1 001 × 111. En généralisant, on peut facilement factoriser les 1...1(n) avec n non premier.
* Par contre, on ne sait toujours pas s'il y en a une infinité de premiers...

Depuis 1985, donc, on a pas trouvé de nouveaux repunits premiers. Mais on en a trouvé quelques uns de probablement premiers (les algorithmes testant la primalité des nombres sont doués pour savoir si un nombre est composé, moins pour savoir s'ils sont premier, d'où le doute quant au résultat).
Les repunits probablement premiers sont (1)49 081 (Dubner - 1999), (1)86 453 (Baxter - 2000), (1)109 297 (Dubner - 2007) et (1)270 343 (Voznyy - 2007). Et on s'arrête là, c'est déjà pas mal !

Ca, c'est pour la base 10, mais quand est-il si on choisit une autre base ? Jusqu'à présent, on était en base 10, si bien que (1)n = (10n-1)/9. Mais si on se place dans la base k, le nombre composé seulement de 1 dans la base k est (1)n = (kn-1)/(k-1).

Dans la base 2, les repunits sont les nombres de la forme 2n-1, et les nombres premiers de cette forme sont appelés les nombres premiers de Mersenne ! (Le plus grand nombre premier de Mersenne connu est 232 582 657-1, ce qui en fait un nombre composés de 9 808 358 de chiffres)

Pour ce qui est des repunit généralisés, on a (19561801-1)/(1956-1), qui s'écrit avec 1801 chiffres 1 dans la base 1956 ! En notation traditionnelle en base 10, il est composé de 5 925 chiffres décimaux.

Les nombres premiers palindromes

Si les palindromes existent dans la langue française (les mots comme kayak qui se lisent dans les deux sens), il n'y a pas de raisons de ne pas les transposer dans le monde des chiffres, et encore moins à le transposer parmi les nombres premiers.

Grande question, donc, quels sont les nombres premiers palindromes ?
2, 3, 5, 7... Jusqu'à là, pas de problèmes.
Pour les nombres à deux chiffres, on a 11, les autres seront des multiples de 11.
101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929 sont tous ceux de 3 chiffres...
Entre 1000 et 9999, il n'y a pas un seul nombre premier palindrome !
On en trouve ensuite 93 entre 10000 et 99 999. Évidement, on ne sait pas s'il y en a un nombre infini, comme souvent dans ce genre de questions.

En fait, on peut facilement voir que tout nombre palindrome de longueur paire est divisible par 11, car il vérifie le critère de divisibilité par 11 !

Pour les curiosités des nombres premiers palindromes, on a :
* 1 023 456 987 896 543 201, le plus petit palindrome premier qui contient tous les chiffres de 0 à 9
* 1(0)749997426247(0)749991, ((0)74999, c'est une suite de 74999 zéros) est le plus grand palindrome premier prouvé comme tel ! (Joblin - 2005 - 150 007 décimales)
* 1(0)56514661664(0)56511 est un nombre premier triplement palindrome : il est premier, il est palindrome, et son nombre de chiffres, 11311, est également palindrome et premier !

Les nombres premiers raccourcissablesRacc_gauche
Il y a aussi ces nombres qui ne craignent pas de perdre leur décimales !

Le nombre 35 768 631 264 6216 567 629 137 est le plus long nombre premier connu qui reste premier si on lui enlève son premier chiffre. Un nombre premier de ce type est appelé "raccourcissable à gauche".

Evidemment, pour la beauté de la pyramide, on exclut les nombres contenant le chiffre zéro ; ça serait trop facile de faire la même chose avec 20000003, qui devient 3 dès qu'on lui enlève son premier 2.

Racc_droiteQui dit "raccourcissable à gauche" dit "raccourcissable à droite". De tels nombres ont encore plus de contraintes : pas de 2, 4, 5, 8 ou 0, sous peine d'être facilement divisible par 2 ou 5.
Le plus long connu, est 73939133, mais si on s'autorise une petite entorse au règlement en admettant 1 comme un nombre premier, le plus long nombre premier raccourcissable à droite est 1979339333.

Et histoire de mélanger toutes les contraintes, on pyramide_2peut chercher les palindromes raccourcissables à droite et à gauche ! Cela forme de jolies pyramides premières. Mais cela ne laisse que 2 possibilités de pyramides de cette hauteur.
En effet, on ne dispose que de 4 sommets possibles (2, 3, 5 et 7). Pour chacun de ces sommets, il est facile de tester toutes les marches possibles. Les pyramides plus petites ont pour bases 11311, 71317, 93739, 1335331, 3315133 et 9375739.

Mais on peut se permettre un peu plus de liberté, et se permettre des marches un peu plus grandes. En limitant la taille des marches, on conjecture que toutes les pyramides seront de hauteur finie, peut importe le palindrome premier choisit au sommet. Mais cela reste à prouver.
Si on ne s'impose pas de taille de marche, et que l'on prend le premier premier qui correspond (on suppose qu'on peut le faire infini, mais rien est prouve), on trouve :

pyramide

(Au sommet, on doit pouvoir lire 2... La pyramide fait 57 marches, la dernière marche est composée de 297 chiffres... Mais on est pas sûrs à 100% de la primalité des nombres de la base)

Nombres premiers permutables

Et des nombres premier qui restent premiers si on mélange tous les chiffres ? Si c'est imaginable, c'est que ça existe, et ça s'appelle "nombre premier permutable". En fait, on en connait pas tant que ça : 2, 3, 5, 7, 11, 13, 17, 37, 79, 113, 199 et 337 (à un mélange près). Il y a aussi les repunits premiers qui rentrent dans cette catégorie.

Et si on en a marre des nombres premiers ?
Waclaw Sierpinski, dans les années 50, s'est demandé s'il existait un nombre composé (non premier) qui reste composé lorsque l'on change des chiffres de son écriture.
Le nombre 200, par exemple, reste composé si on change n'importe lequel de ses chiffres

Et si on se fixe deux chiffres à changer ? Le résultat est tombé en octobre dernier : ce nombre est 977 731 833 235 239 280, et c'est le plus petit ! Merci à Witold Jarnicki et Maciej Żenczykowski pour ce résultat !


Sources :
La factorisation de tous les repunits
A propos des pyramides [pdf]
On a property of the number 977731833235239280 [pdf]
Pour tout le reste, il y a Prime Curios !