Suites d' Ulam

La définition de la suite d'Ulam (ou des nombres de Los Alamos) se trouve dans un livre de récréations mathématiqes de Clifford A. Pickover : Oh, encore des Nombres !, sous-titré : 54 autres histoires et problèmes « numériques » (chez Dunod).
Stanislaw Ulam, a une époque où il était à Los Alamos, inventa ces suites.

Ce sont les suites définies par la donnée des deux premiers termes u₀ = a, u₁ = b et par la récurrence suivante pour n supérieur ou égal à 2 :

u_n est le plus petit entier somme de deux termes distincts précédents de la suite, et d'une seule manière.

Los Alamos

Deux germes     Nombre de termes



Termes de la suite

En prenant la suite 1 2 3 4 6 8 11 13 16 18 26 28 ... définie par ses deux premiers termes 1 et 2 on peut calculer les différences entre les termes successifs 2-1=1, 3-2=1, ... 6-4=2, ... 11-8=3, ... et on obtient la nouvelle suite

               1, 2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 15, 17 ...  

On remarque qu'il manque un certain nombre d'entiers non nuls

               6, 11, 14, 16, 18, 21, 23, 26, 28, 31, 32, 33, 35, 36, 37 ...

En calculant à nouveau les différences entre les termes successifs on obtient

               1, 2, 3, 5

qui ont la surprenante particularité d'être des nombres de Fibonacci (suite 0, 1, 1, 2, 3, 5, 8, 13, 21, ...)
Pickover et Ken Shirrif a trouvé ces écarts en étudiant les 100001 premiers termes de la suite d'Ulam_1,2.
[initial]
Il faut noter que d'autres suites d'Ulam_a,b avec d'autres germes a, b peuvent donner des résultats différents. Les résultats partiels obtenus en n'étudiant que les premiers éléments de la suite sont susceptibles d'étre invalidés ensuite, ainsi [1er exemple] et [2ème exemple] où les premiers résultats 1 2 3 4 sont corrigés ensuite en 1 2 3 5 lorsque plus de termes de la suite sont connus, (la différence 13 n'avait pas été vue dans le premier exemple et se retrouvait faussement placée dans la liste des différences manquantes). Les résultats partiels obtenus par l'application ci-dessus ne doivent donc pas être considérés comme définitifs. Dans [certains cas] on peut facilement montrer que les écarts sont 1 et 2 (et pas plus). Idem pour [3 6].


Effectifs des différences des termes de U_1,2
J'ai calculé un peu plus de 37 10⁴ termes à l'aide d'un programme C rudimentaire et n'ai toujours trouvé rien d'autre que "1, 2, 3, 5".
Vous pouvez remarquer que lorsque le nombre d'éléments augmente, c'est la 3-ième fenêtre ci-dessus qui se modifie le moins, il n'y a probablement pas eu de différence notable entre l'étude de 100000 ou de 370000 éléments, dans les deux cas la plus grande différence observée est 587, la plus grande valeur manquante est 586.
source :     los.c   
compilation :     gcc -O2 -o los los.c    
utilisation pour u_n<10⁶ :     los 5000000 1 2 > l5E6.g
figure : echo 'set grid;set term png size 600,300;set output "l5E6.png"; set logscale y 10;plot "l5E6.g" w impulses;'|gnuplot

Liens