La spirale de Ulam

 

On raconte que Ulam, s'ennuyant fort lors d'une conférence, prit son crayon et écrivit les entiers naturels en colimaçon en utilisant les carreaux de sa page. Puis il noircit les cases occupées par les nombres premiers. La spirale qui porte son nom était née. Elle survécut car on s'apperçut que d'étranges alignements apparaissaient qu'il fallait expliquer. De plus, il est amusant de programmer cet enroulement de nombres premiers. On peut utiliser un ordinateur mais une calculatrice à écran graphique suffit.

Le principe du programme
Le programme sur une casio Graph 35
Le programme en Visual Basic sous Excel
Utiliser le programme
Les alignements d'entiers premiers dans la spirale de Ulam
Le polynome particulier P(n)=n²-n+41
Conclusion

Le principe du programme

On voit ci-contre les entiers écrit en spirale dans le sens trigonométrique.

On décide de la position du centre de la spirale, là ou se trouve le '1'. On choisit logiquement un point proche du centre de l'écran.

Pour calculer la position d'un entier q quelconque sur le quadrillage, on peut appliquer la méthode suivante :

1) Trouver sur quelle couronne se trouve q. Par exemple les entiers 1,2,3,4 se trouvent sur la couronne 1,en jaune sur le dessin. Les entiers entre 5 et 16 se trouvent sur la couronne 2, en vert sur le dessin. Les entiers entre 17 et 36 se trouvent sur la couronne 3, en bleu sur le dessin. Plus généralement les entiers entre (2n)²+1 et (2(n+1))² se trouvent sur la couronne (n+1).

2) Une fois déterminée le numéro de la couronne à laquelle appartient q, il faut déterminer sur lequel des 4 cotés de la couronne se situe q. Pour celà il faut comparer la différence de q avec le plus petit entier situé sur la même couronne que lui , avec le nombre d'entiers sur cette couronne. Celà permet, en utilisant une division par 4 et son quotient, de savoir si q appartient au premier, au deuxième , au troisième, ou au quatrième côté de sa couronne.

3) Ensuite il reste à déterminer la position de q sur le côté, et pour celà on utilise le reste de la division par 4, faite à l'étape précédente.

4) Avec les 3 informations, on peut déterminer les formules permettant de positionner exactement le nombre q, en fonction de la position du nombre 1.

Pour déterminer si q est premier ou non :

On peut appliquer la méthode classique, diviser q par les entiers k dont le carré est inférieur ou égal à q. Si une division tombe juste, q n'est pas premier, dans le cas contraire q est premier. On s'applique à ne tester que les nombres q impairs et donc à ne tester que les diviseurs impairs.

Remarque : Si on ne colorie que les cases contenant les nombres premiers, il est alors inutile de calculer la position sur l'écran des nombres composés.

 

Le programme sur une Casio graph 35

On utilise la méthode développée ci-dessus. A chaque nombre entier correspond un pixel sur l'écran. On ne cherche la position de ce pixel que si l'entier correspondant est premier. L'éxécution du programme est un peu long, 1 heure environ pour déterminer les entiers premiers jusqu'à 4000, et les placer.

Attention : dans le programme ci-dessous, le caractère"?" remplace le caractère "flèche" de la casio( au dessus de on/off). En effet je n'ai pas réussi à écrire cette flèche avec dreamweaver.

ViewWindow 1,127,1,1,63,1
AxesOff
PlotOn 63,32
For 4001?N To 3 Step 2
3?D
While D²=N
If Frac (N÷D)=0:Then Goto 1:Else D+2?D:IfEnd
WhileEnd
-1?P
While (2P+2)²<N
P+1?P
WhileEnd
2P+1?L
63-P?A
32-P?B
N-1-(2P)² ?K
Int (K÷L) ?Q
K-LQ?R
If Q=0:Then A+R?S:B?T:IfEnd
If Q=1:Then A+2P?S:B+R+1?T:IfEnd
If Q=2:Then A+L-2-R?S:B+L?T:IfEnd
If Q=3:Then A-1?S:B+L-1-R?T:IfEnd
PlotOn S,T
Text 10,110,N
Lbl 1
Next


Commentaires

 

 

Cette première ligne met la calculatrice en mode graphique. Supprime les axes.Un pixel noirci au centre de l'écran, pour l'entier 2, seul premier pair.

On teste les entiers N entre 3 et 4001, seul les impairs. On teste D=3 comme premier diviseur de N. Tant que le carré de D est plus petit que N+1, on incrémente D, sauf s'il divise N, auquel cas on va en 1, ce qui conduit à incrémenter N.

Si N est déclaré premier, les lignes suivantes servent à déterminer la position du pixel à noircir, suivant la méthode exposée plus haut.

La première boucle while détermine le numéro de la couronne à laquelle appartient le pixel à noircir.

Les autres lignes servent à déterminer le côté de la couronne qui contient le pixel, ensuite la détermination du quotient Q et du reste R, permet de déterminer exactement la position (S,T) du pixel à noircir.

La ligne de Texte affiche l'entier N premier qui vient d'être matérialisé par un pixel sur l'écran, ce qui permet de savoir la progression du programme.

Next renvoie au début de la boucle, ce qui incrémente N de deux unités.

 

 

 

Le programme en visual basic sous Excel et résultats

La spirale de Ulam pour les entiers jusqu'à environ 7500 La spirale de Ulam pour les entiers jusqu'à environ 400

 

Dim prem As Boolean

Dim n, m, c1, c2, a, b, max, i, j, p, q, attente As Single

Sub initialiser()
c1 = 130
c2 = 130
For i=c1-n-1 To c1+n+1
for j=c2-n-1 To c2+n+1
Cells(i,j).Interior.ColorIndex=0
Next
Next
max = 25
attente = 1000000
End Sub

Sub premier()
prem = True
m = 2: a = 1
While ((m * m <= q) And (a <> 0))
a = q Mod m
m = m + 1
Wend
If ((a <> 0) And (q > 1)) Then prem = True Else prem = False
End Sub


Sub colorier()
If prem = True Then
Cells(i, j).Interior.ColorIndex = 1
Else
Cells(i, j).Interior.ColorIndex = 6
End If
End Sub

Sub placer()
d = q - 2 * p * 2 * p - 1
e = Int(d / (1 + 2 * p))
If e = 0 Then
i = c1 + 4 * p * p + p - q + 1
j = c2 - p
End If
If e = 1 Then
i = c1 - p
j = c2 - 4 * p * p - 3 * p - 1 + q
End If
If e = 2 Then
i = c1 - 4 * p * p - 5 * p - 2 + q
j = c2 + p + 1
End If
If e = 3 Then
i = c1 + p + 1
j = c2 + 4 * p * p + 7 * p + 4 - q
End If
End Sub

 

Static Sub programmeprincipal()
initialiser
For p = 0 To max
For q = 4 * p * p + 1 To (2 * p + 2) * (2 * p + 2)
For t = 1 To attente: Next
premier
placer
colorier
Next
Next
Cells(c1, c2).Interior.ColorIndex = 3
Feuil2.Cells(1, 1).Value = q
n= max
End Sub

Les 2 premières lignes du programme déclarent les variables, toutes entières dans ce programme sauf prem qui est une variable Booléenne et qui prend que deux valeurs, TRUE ou FALSE.

Le sous programme initialiser permet de donner des valeurs à certains paramètres. C1 et C2 sont les références de la case correspondant à l'entier 1. max est le nombres de couronnes, qui composent le carré final. attente est un paramètre qui entre dans une boucle vide et permet de ralentir le déroulement du programme afin d'en observer la progression.
La double boucle efface les couleurs obtenues à la dernière éxécution du programme.

 

Le sous programme premier permet de tester si le nombre q est premier ou non. A la fin du test la variable prem est TRUE ou FALSE suivant que q est premier ou non.

La boucle WHILE est le coeur du test, a=q Mod m signifie que a est le reste de q dans la division euclidienne par m.

On pourrait initialiser m à 3, et dans la boucle While remplacer m=m+1 par m=m+2 afin de tester que les diviseurs impairs. Cela oblige alors à traiter le cas q=2 à part. Le programme se déroulerait plus vite, mais comme par ailleurs on essaye de le ralentir...

 

 

Le programme colorier sert déterminer les couleurs des cases, en fonction du statut des entiers auxquelles elles sont associées. Une couleur si l'entier est premier, une autre s'il ne l'est pas. 1 est l'index de la couleur noire, 6 celle du jaune, 3 celle du rouge utilisée plus loin pour colorier la case origine associée à 1.

 

 

Le sous programme placer est le plus délicat.
En réalité pour bien le comprendre il vaut mieux chercher les formules soi même, en utilisant le principe énoncé plus haut.

d est la distance entre le nombre q et le plus petit nombre de la couronne p.

e+1 est le numéro du coté de la couronne ou se trouve q.

Il y a donc 4 possibilités pour e et à chacune d'elle correspond une formule pour i et une pour j.

 

 

 

Le programme principal est appellé et éxécuté en premier et celui ci a pour rôle de répartir les taches entre les différents sous programmes.

p désigne le numéro de la couronne qui contient le nombre q.

le sous programme premier est appelé pour tester si q est premier. Ensuite le sous programme placer détermine la position de q sur le quadrillage. Ensuite le sous programme colorier est appellé pour colorier la case.

Le programme principal est lu autant de fois qu'il y a de nombre à tester.

La case centrale associée à 1, est coloriée en rouge. Sur la feuille 2, sur la première cellule on affiche la dernière valeur de q, donc le plus grand entier testé.

La valeur du plus grand entier testé est affiché sur la feuille2.
n prend la valeur de max, ceci pour effacer les couleurs au prochain lancement du programme.

 

Utiliser le programme "spirale_ulam"

télécharger "spirale_ulam" . Ensuite ouvrir avec Excel. Aller dans outils-macro-macro-programme principal et cliquer sur éxécuter. La spirale s'affiche lentement sur votre écran car le paramètre attente est réglé sur 1000000. Pour un affichage plus rapide ou instantané, on peut diminuer la valeur du paramètre attente, directement dans le programme. Pour celà, faire apparaitre le programme en faisant Outils-Macro-Visual Basic editor (ou Alt F11) ou encore Outils-Macro-Macro-modifier. Choisir par exemple 1000 ou 1. Vous pouvez aussi changer la valeur du paramètre max pour augmenter le nombre de couronnes affichées donc le nombre d'entiers affichés. Il faudra alors agir sur la fonction zoom de Excel pour voir la spirale dans sa totalité. Pour max = 120(ne pas dépasser cette valeur)il faut choisir un zoom de 20% ou 10%.Quand vous êtes sur la feuille de programme, pour revenir sur la feuille de calcul faire Alt F11.

 

Les alignements d'entiers premiers dans la spirale de Ulam

Dans la spirale de Ulam, apparaissent des alignements diagonaux de points carrés noirs, suggérant que certaines diagonales contiennent un nombre important d'entiers premiers. Il est donc intéressant d'en savoir un peu plus sur ces alignements. Considérons la spirale ci dessous, à droite. 2 couronnes voisines se distinguent par des couleurs différentes, les entiers premiers sont en jaune et chaque case est numérotée.

Les alignements diagonaux sont des suites d'entiers dont les différences successives forment une suite arithmétique de raison 8( au fait, pourquoi 8 ?) , à condition que deux entiers de la suite n'appartiennent pas à la même couronne.

Ces suites peuvent s'écrire : pour tout entier n, w(n)=w(n-1)+ 8(n-1)+b

En fonction de n, on trouve facilement : pour tout entier n , w(n)=4n²+n(b-4)+w(0)

On obtient ainsi quelques exemples :

3-11-27-51-83-123-171 u(n)= 4n²+4n+3
26-48-78-116-162 u(n)= 4n²+18n+26
43-71-107-151-203-263-331-407 u(n)=4n²+24n+43
7-23-47-79-119-167-223-287-359-439-.. u(n)=4n²+12n+7
1681-1847-2021-2203-2393-2591-2797- u(n)=4n²+162n+1681

Certains de ses polynomes fournissent beaucoup de nombres premiers, sans explications convaincantes à part que certains d'entre eux fournissent toujours des entiers impairs.

 

 

 

 

Le polynome particulier P(n)=n²-n+41

On sait depuis Euler que ce polynome donne des nombres premiers pour les 41 premiers entiers naturels. On s'attend à ce que ces 41 entiers soient alignés sur une diagonale de la spirale de Ulam. Or ce n'est certainement pas le cas, le coefficient de n² n'ètant pas 4(voir § précédent). On s'intéresse alors à la répartition des P(i)sur la spirale des entiers , i étant un entier plus petit que 170.

Voilà ce que l'on obtient, ce qui assez curieux. Une zone de points ou semble régner le désordre, puis 2 segments, puis 2 alignements au sens ou on l'a vu plus haut. Ici, les points bleus représentent les entiers premiers et les points jaunes les entiers composés.

Les 41 premières valeurs prises par le polynome, toute premieres, sont réparties de façon chaotique, puis sur les 2 petits segments.

Il est également surprenant de voir apparaitre ces deux demis droites, puisque l'étude précédente semble prouver que de tels alignements ne peuvent être générés par ce polynome. L'examen précis de ces deux alignements montre que les valeurs de P(n) pour n >40 se répartissent alternativement sur l'une et l'autre branche. La branche du haut contient les valeurs de P(n) pour n impair et celle du bas contient les valeurs de P(n) pour n pair. Remarque: le dernier exemple du paragraphe précédent est la suite de rang impair du polynome P.

P(n) est une suite dont les différences de termes consécutifs forment une suite arithmétique de raison 2, donc la suite P(2n), suite extraite des rangs pairs est une suite dont les différences de termes consécutifs est arithmétique de raison 8( étonnant mais facile à montrer). De même, la suite P(2n+1), suite extraite des rangs impairs est une suite dont les différences de termes consécutifs est arithmétique de raison 8. La contradiction apparente est donc levée.

Le premier entier composé est 1681 pour n=41. Cependant la figure comporte beaucoup de points bleus(premiers) et très peu de points jaunes. Celà signifie que le polynome P semble fournir un nombre anormal d'entiers premiers, ce que l'on vérifie ci dessous, pour n plus petit que 1000.

Pour quelques valeurs de n, le tableau suivant indique le pourcentage d'entiers premiers, parmi les valeurs P(i), i étant un entier naturel plus petit que n. Pour faire une comparaison on calcule aussi le pourcentage d'entiers premiers dans chaque intervalle I par rapport au nombre d'entiers impairs dans I. On s'apperçoit que, même pour de grandes valeurs de n, P(n) est souvent un entier premier.

n les valeurs de P(n) sont dans l'intervalle I nombre d'entiers P(i) premiers

pourcentage/n

nombre d'entiers premiers dans l'intervalle I pourcentage d'entiers premiers parmi les impairs de l'intervalle I
100 [41; 10059]] 86 86% 1214 6,1%
200 [41;39841] 156 78% 4176 5,2%
300 [41;89741] 211 70% 8676 4,8%
500 [41;249541] 326 65% 21998 4,4%
1000 [41;999041] 581 58% 78424 3,9%

 

 

Conclusion

Plein de questions restent en suspend : Pourquoi le polynome P(n) génére-t-il autant d'entiers premiers ? Existe -t-il d'autres polynômes simples ayant la même propriété? Si oui, comment les fabriquer?
Si certains lecteurs ont des réponses ou des contributions à proposer, n'hésitez pas, toutes remarques ou compléments permettant de faire évoluer cette feuille seront les bienvenues.

Pour toutes remarques concernant cette page, écrire à Philippe Bondon.