Qui occupe la milliardième position ?

Considérons une suite dans laquelle 1 apparaît une fois, 2 deux fois, 3 trois fois, et ainsi de suite. Quel nombre se trouve exactement à la milliardième position ? L’intervalle occupé par chaque nombre permet de répondre sans construire un milliard de termes.

Ce document a été préparé à l’origine pour le cours 2011-2012 destiné aux enseignants nouvellement nommés et imprimé le 15 mai 2012.

1. Résumé

Ce document corrige la solution attribuée à Ferdinando Arzarello pour l’UMI : 44722 n’est pas le bon résultat. La réponse exacte est 44721. Le point essentiel est que le nombre n n’occupe pas une seule position, mais tout un intervalle de n positions.

2. Le problème

Considérons la suite de nombres naturels suivante :

1  2 2  3 3 3  4 4 4 4  5 5 5 5 5  6 6 6 6 6 6  ...

On écrit une fois le nombre 1, deux fois le nombre 2, trois fois le nombre 3 et, en général, n fois le nombre n. La question est : quel est le milliardième terme de cette suite ?

3. Une solution par intervalles

Pour trouver la position finale du nombre 4, par exemple, additionnons les quatre premiers nombres :

1 + 2 + 3 + 4 = 10

La formule de Gauss donne la position finale du bloc contenant n :

fin(n) = n(n + 1) / 2 = (n² + n) / 2

Le bloc contient n termes ; sa position initiale est donc sa position finale moins n - 1 :

début(n) = n(n + 1) / 2 - (n - 1)
         = n(n - 1) / 2 + 1
         = (n² - n + 2) / 2

Le nombre n occupe toutes les positions, bornes comprises, de (n² - n + 2)/2 à (n² + n)/2.

4. Vérification avec un tableur

Dans Excel, ou dans tout autre tableur, créons trois colonnes : n, position initiale et position finale. Les premières lignes montrent la croissance des intervalles ; les deux dernières apportent la réponse.

La réponse exacte est le plus petit entier n tel que fin(n) ≥ 1 000 000 000 : cet entier est 44721. La position 1 000 000 000 appartient bien à son intervalle. Le nombre 44722 ne commence qu’à la position 1 000 006 282, au-delà du milliardième terme. Ne pas préciser qu’il existe un intervalle de positions peut facilement prêter à confusion.

5. Modélisation et approximation

Notons I la position initiale et F la position finale du bloc de n :

I = (n² - n + 2) / 2
F = (n² + n) / 2

2I = n² - n + 2
2F = n² + n
2I + 2F = 2n² + 2
I + F = n² + 1
n² = I + F - 1

Si M = (I + F)/2 est la moyenne des positions occupées par le nombre, alors :

n² = 2M - 1

Le carré de n est donc exactement le double de la position moyenne, diminué de 1. Comme les fonctions considérées sont croissantes, remplacer M par un nombre plus petit donne une approximation par défaut ; le remplacer par un nombre plus grand donne une approximation par excès. Sans connaître les positions initiale et finale, on ne peut pas déterminer de quel côté se trouve l’approximation.

Ici, en prenant directement un milliard comme valeur de référence, on obtient :

√(2 · 1 000 000 000)     = 44 721,3595499958
√(2 · 1 000 000 000 - 1) = 44 721,3595388155

Ces deux valeurs sont très proches de la solution entière 44721. Pour n = 44721, la position moyenne est :

M = (999 961 561 + 1 000 006 281) / 2
  = 999 983 921

Puisque 1 000 000 000 est supérieur à cette moyenne, 44 721,3595388155 est une approximation par excès. La vérification par l’intervalle prouve finalement sans ambiguïté que le milliardième terme est 44721.

Préparé par Salvatore Mosaico.