Réponse au défi numéro 14 de Performance Calcul

Vincent Lefèvre

24, rue Louis Blanc 31400 Toulouse

                    e-mail: Vincent.Lefevre@ens-lyon.fr
                 WWW: http://www.ens-lyon.fr/~vlefevre/

Numéro Performance Calcul: 300136

27 avril 1996

Pour n ⩾ 1, soit G(n) le ne terme de la suite de Golomb. On va considérer les valeurs de n pour lesquelles G(n + 1) ≠ G(n) ; elles sont intéressantes car elles déterminent des intervalles dans lesquels G est constante, et il suffit de savoir dans quel intervalle le nombre n donné est situé. Pour k ⩾ 0, on définit l’entier

S(k) = ∑_{i=1}^{k} G(i).

D’après la définition de la suite, on a : G(n) = k ⟺ S(k − 1) < n ⩽ S(k).

Cherchons maintenant à calculer S(k) rapidement, k étant très grand. Dans la somme, on regroupe les G(i) qui sont égaux à un même nombre j. On pose k = S(ℓ − 1) + p, où ℓ = G(k). On a alors :

S(k) = ∑_{j=1}^{ℓ−1} G(j).j + pk.

On va donc calculer les G(ℓ) et les S(S(ℓ)), en commençant par ℓ = 1, et en incrémentant ℓ successivement, jusqu’à ce que S(S(ℓ)) ⩾ n. On peut alors calculer :

G(n) = k = S(ℓ) − ⌊(S(S(ℓ)) − n)/ℓ⌋,

où S(ℓ) se calcule directement à partir de la définition, ℓ étant suffisamment petit par rapport à n.

En fait, on ne calculera par S(S(ℓ)), mais on considèrera d’abord S(S(1)) − n, puis on ajoutera G(ℓ).ℓ à chaque itération pour avoir S(S(ℓ)) − n. Cela a 2 avantages : d’une part, c’est un peu plus rapide et cela prend un peu moins de mémoire ; d’autre part, cela évite les erreurs d’arrondi éventuelles de S(S(ℓ)) quand n est proche de 10^{12}.

Programme pour HP48S/SX :

<< { 1 } 1 ROT -
  WHILE DUP 0 <
  REPEAT SWAP DUP DUP SIZE 3 DUPN GET GET - 1 + GET 1 +
         + LASTARG SWAP SIZE 1 + * ROT +
  END OVER SIZE / FLOOR SWAP LIST-> ->ARRY CNRM SWAP -
>>

127,5 octets – CRC : #948Eh

Au niveau du WHILE, le niveau 1 de la pile contient le nombre S(S(ℓ)) − n, et le niveau 2 de la pile contient la liste des G(j), pour j allant de 1 à ℓ. Le WHILE teste si n > S(S(ℓ)). G(ℓ + 1) est calculé à partir de la formule

G(ℓ + 1) = G(ℓ − G(G(ℓ)) + 1) + 1,

en utilisant la liste des G(j) déjà calculés. (ℓ est suffisamment petit pour qu’on puisse utiliser cette formule sans perdre trop de temps.)

G(140) est renvoyé au bout d’une seconde environ. G(10 000) est renvoyé au bout de 7, 3 secondes environ.