Les nombres premiers de la forme 10 puissance N + 1

Enoncé : Trouver un nombre premier, de la forme: 10^n + 1, autre que ces 2 premiers: 11, et 101. J’ai écrit un programme Python sous Windows 7 (oui, je ne suis pas toujours sous Linux).

Code source :

n = 1

while (n <= 100):  

q = 1 + (10 ** n)  

d = 2  

p = 1.0  

r = int(q ** 0.5)  

while (d <= r):  

w = q % d  

p = p * w / 2  

if (d == 2):   

d = d + 1  

else:   

d = d + 2     

if (p == 0):  

print(« 1 + 10 PWR « +str(n)+ » is composed »)

 if (p != 0):  

print(« 1 + 10 PWR « +str(n)+ » is PRIME »)   

 n = n + 1   

Attention, il existe une indentation à respecter dans l’écriture du code Python. Résultat : Les nombres 11 et 101 sont premiers. Mais les suivants paraissent tous composés, pour n supérieur à 2. Cette assertion est vraie pour tout n inférieur ou égal à 17 (à l’exception des nombres 11 et 101 qui sont premiers), au moment ou je rédige les résultats disponibles. Au-delà de 17, mystère…

  • Comment démontrer que 10^n + 1 est composé, pour tout n supérieur à 2 ?

 

Réédition du 8 avril 2015 :

J’ai amélioré le programme Python, j’en ai aussi fait une version pour Linux (le code s’écrit différemment notamment pour l’instruction PRINT, probablement parce que les versions de Python diffèrent entre elles).

#!/usr/bin/python
n = 1
while (n <= 100):  
 q = 1 + (10 ** n)  
 d = 2  
 p = 1.0  
 r = int(q ** 0.5)  
 while (d <= r):  
  w = q % d  
  if (w == 0):
   p = 0
   d = r
  p = p * w / 2  
  if (d == 2):   
   d = d + 1  
  else:   
   d = d + 2     
 if (p == 0):  
  print « 1 + 10 PWR  » +str(n)+  » is composed « 
 if (p != 0):  
  print « 1 + 10 PWR  » +str(n)+  » is PRIME  »  
 n = n + 1  

 

Résultats :

A l’exception des nombres 11 et 101, tous les nombres de la forme 10 puissance n + 1 sont composés, pour tout n compris entre 3 et 63. Pour n supérieur à 63, mystère…

Néanmoins, le calcul a été très rapide jusqu’à n=63. Mais l’exécution du programme s’est brutalement ralentie à partir de n=64. Est-ce que 10 puissance 64 + 1 est premier ? C’est une hypothèse… Finalement, non, 10^64 + 1 n’est pas premier, le programme a continué de travailler, maintenant il est clair que jusqu’à 10^100 + 1, les entiers de cette forme sont composés.

J’ai ensuite modifié la valeur limite de n car le programme devait cesser avec n=100. Alors j’ai fixé comme limite, n=1000. Le programme a calculé rapidement, puis il a planté lorsqu’il a atteint n=308, avec ce message d’erreur : OverflowError: long int too large to convert to float.

Résultat : pour n supérieur à 2 et inférieur ou égal à 308, tout entier de la forme 10^n + 1 n’est pas premier.

J’ai remplacé l’instruction r=int(q ** 0.5) par r=q-1. L’overflow est ainsi évité.

Résultat actuel : pour n supérieur à 2 et inférieur ou égal à 1000, tout entier de la forme 10^n + 1 n’est pas premier.

Copyright 2015 John Philip C. Manson

Advertisements