A1976. Un générateur de nombres premiers Imprimer
A. Arithmetique et algèbre - A1. Pot pourri
calculator_edit.png  
On introduit l’entier 2010 dans la mémoire d’un automate. A l’étape n° k de son programme, il calcule le plus grand commun diviseur d de k et de l’entier n qui est dans sa mémoire puis il remplace n par n + d. Démontrer que la valeur 1 mise à part, l’entier d calculé à chaque étape est toujours un nombre premier.
Source: d'après Tournoi des Villes - session du printemps 2009.

 Solution


Jean Moreau de Saint Martin,Jean Drabbe,Claude Felloneau et Maurice Bauval ont résolu le problème. Celui-ci a été posé pour la première fois à la session de printemps 2009 du Tournoi des Villes avec une valeur de départ n0 égale à 6. La séquence des nombres premiers qui en résultait était : 5,3,11,3,etc...alors que celle de notre problème est : 7,5,3,43,etc..
Jean Drabbe a remarqué que ce générateur de nombres premiers n'était autre que le générateur conçu par Eric Rowland qui l'a présenté et en a donné ses principales propriétés dans un article paru en 2008 dans "Journal of Integer Sequences". De son côté Jean Moreau de Saint Martin, après avoir exploré les valeurs de départ n0 comprises entre 2 et 2010, a constaté que pour 122 valeurs  -la plus petite étant 531 et la plus grande 1794 - il y a un incrément d distinct de 1 qui n'est pas premier mais le cas ne se produit qu'une fois par valeur de n0 pour n <10000000. La propriété de d premier n'est pas universellement vraie et dépend donc du point de départ n0.Claude Felloneau a fait la même observation avec n0 = 1000 qui donne pour premier incrément >1 le nombre 21 qui est composé.