Inscription / Connexion Nouveau Sujet
Niveau énigmes
Partager :

Premiers palindromes

Posté par
dpi
25-08-18 à 18:24

Bonjour à tous,

Nous avons eu récemment un exercice sur les premiers palindromes.
Pour changer des figures ,qui trouvera le plus grand premier palindrome soit
à la main...soit sur tableur....soit sur ordi.

Petit conseil éviter ceux qui commencent par un chiffre pair

Posté par
mijo
re : Premiers palindromes 25-08-18 à 19:18

Bonjour  dpi
Je suis bien incapable de le trouver avec les 3 façons que tu cites

 Cliquez pour afficher

Posté par
derny
re : Premiers palindromes 25-08-18 à 22:09

Bonsoir
je connais le plus petit premier palindrome mais je crois que personne ne peut connaître le plus grand.

Posté par
dpi
re : Premiers palindromes 26-08-18 à 09:49

Bon dimanche,
Comme le problème est ouvert on peut ne pas blanker

2 chiffres :11 bien sûr
3 chiffres : 929
4 chiffres : aucun  ( une petite démo serait bienvenue...)
5 chiffres  (problème récent ) :98689
6 chiffres : aucun (voir 4)
sans aller sur internet trouvez-vous un 9 chiffres (car pas de 8 )?

Posté par
LittleFox
re : Premiers palindromes 27-08-18 à 10:15


Il n'y a pas de nombre premier palindrome avec un nombre pair de chiffres car tout nombre palindrome avec un nombre pair de chiffres est divisible par 11. En effet, un nombre est divisible par 11 si la somme de ses chiffres de rangs pairs moins la somme de ses chiffres de rangs impairs est divisible par 11. Or pour un palindrome avec un nombre pair de chiffres, ces deux sommes sont identiques.


Il y a 602 nombres premiers palindrome de 7 chiffres, le plus grand est 9989899.

Il y a 4721 nombres premiers palindrome de 9 chiffres, le plus grand est 999727999.

Il y a 38107 nombres premiers palindrome de 11 chiffres, le plus grand est 99999199999.

Il y a 318839 nombres premiers palindromes de 13 chiffres, le plus grand est 9999987899999

Voici la liste des plus grands nombres premiers palindromes de n chiffres avec n < 200 :

 Cliquez pour afficher

Posté par
derny
re : Premiers palindromes 27-08-18 à 14:15

Bonjour. Personne ne peut connaître le plus grand nombre premier palindrome parce que ce nombre n'existe pas. Quel que soit "ce nombre" on pourra toujours en trouver un plus grand.
LittleFox, as-tu trouver ces nombres par un programme personnel ou les as-tu "piqués" sur un site Internet ? Impressionnant cette liste.

Posté par
LittleFox
re : Premiers palindromes 27-08-18 à 14:30


Je les ai calculés avec un petit programme python en quelques secondes, j'aurais pu continuer bien plus loin mais sans grand intérêt et sans être sûr à 100% qu'ils sont bien premiers.

m = 1 # Moitié de la longueur de p
while True:
   n = 10**m-1 # On commence avec le plus grand nombre possible
   while n > 0:
      s = str(n)
      s = s[:-1] + s[::-1] # La partie droite de p est le miroir de la partie gauche
      p = int(s)
      if isProbablePrime(p): # On a un palindrome, est-ce qu'on a un nombre premier?
         print(len(s),p)
         break
      n -= 1
   m += 1


isProbablePrime(n) vient d'une librairie que j'ai codé il y a bien longtemps et est basé sur le test de Rabin-Miller. Mon test étant probabiliste pour p > 264 je ne suis en fait pas sûr à 100% quand les nombres dépassent 20 chiffres  :

 Cliquez pour afficher

Posté par
derny
re : Premiers palindromes 27-08-18 à 14:48

Merci LittleFox. Je ne connais pas (encore) ce langage mais les premiers supérieurs à 2x3x5x7x11x13x17 semblent incertains. Est-ce bien ça ?

Posté par
LittleFox
re : Premiers palindromes 27-08-18 à 15:27

Non, il a été vérifié (pas par moi) que le test de Miller Rabin avec les facteurs que j'utilise marche à coup sûr pour les nombres inférieur à 2^{64} = 18446744073709551616 > 2 \times 3\times5\times7\times11\times13\times17\times19\times23\times29\times31\times37\times41\times43\times47 . Pour les nombres plus grand, la probabilité d'avoir un nombre composé déclaré premier est inférieure à 1:2^{14} = 1:16384 < 0.006\%

Ça reste quand même très probable que mes résultats soient corrects . J'en ai testé quelques uns en ligne et ceux que j'ai testé sont premiers.

Posté par
dpi
re : Premiers palindromes 27-08-18 à 17:21

Bravo à vous,

Les solutions proposées dépassent de loin mes espérances.

Posté par
dpi
re : Premiers palindromes 27-08-18 à 17:55

Pour le plaisir,
Pour moi le plus beau des premiers palindromes est:
11 111 111 111 111 111 111 111

Posté par
Sylvieg Moderateur
re : Premiers palindromes 28-08-18 à 18:53

Bonjour,

Citation :
Bonjour. Personne ne peut connaître le plus grand nombre premier palindrome parce que ce nombre n'existe pas. Quel que soit "ce nombre" on pourra toujours en trouver un plus grand.
Je suis curieuse de voir une démonstration

Posté par
LittleFox
re : Premiers palindromes 29-08-18 à 10:33


En fait je poserai même la conjecture suivante (qui est plus  générale que la proposition de Derny):

Citation :
Pour tout palindrome n, il est possible de construire un palindrome m dont n serait la partie centrale. Et tel que m soit premier.


Mais ce n'est qu'une conjecture et ça ne va pas être facile à démontrer
Mais essayez de trouver un contre exemple

Posté par
LittleFox
re : Premiers palindromes 29-08-18 à 10:35

Note : n doit être de longueur impaire

Posté par
Sylvieg Moderateur
re : Premiers palindromes 29-08-18 à 17:49

Bonjour,
Si on démontre cette conjecture alors on démontre qu'il y a une infinité de nombres palindromes premiers.
Or, à ma connaissance, l'infinité des nombres palindromes premiers est une conjecture ...
Mais ça ne doit pas décourager les bonnes volontés

Posté par
LittleFox
re : Premiers palindromes 29-08-18 à 17:51

Exactement

Posté par
derny
re : Premiers palindromes 29-08-18 à 21:14

Bonsoir
Les démos en théorie des nombres, quand elles existent sont très pointues hors de ma portée en général.
dpi, les nombres formés uniquement de "1" s'appellent des multi-as je crois. Une condition nécessaire (mais pas suffisante) pour que ce soit un nombre premier est que le nombre de 1 soit un nombre premier.  Je crois avoir lu aussi que leur nombre serait infini.

Posté par
carpediem
re : Premiers palindromes 29-08-18 à 21:40

derny :

Posté par
derny
re : Premiers palindromes 30-08-18 à 09:19

Bonjour
oui carpedien mais ils s'appellent aussi multi-as (j'ai retrouvé un ancien article de 1991). On ne connait actuellement que 5 multi-as premiers et on en connait des probables. Pour leur nombre qui serait infini ma mémoire a des ratés et j'ai confondu avec d'autres nombres.

https://wikimonde.com/article/Répunit



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !