Suite de Hofstadter-Conway à 10000$⚓︎

Cette suite $(a_n)_{n\in\mathbb N^*}$ de Hofstadter-Conway est définie par :

\[a_1 = a_2 = 1\]

\[a_n = a_{a_{n-1}} + a_{n-a_{n-1}}\quad \text{pour }n \geqslant 3\]

On définit alors

\[S_n = \sum_{i=1}^{n}a_n\quad \text{pour }n \geqslant 1\]

Objectif : Construire un tableau de valeurs pour $S$ de taille 10000. $S_0$ n'étant pas défini, on le codera par None.

Exemples

🐍 Console Python

>>> S[1]
1
>>> S[2]
2
>>> S[3]
4
>>> S[4]
6
>>> len(S) >= 10000
True

###

∞/∞

a = [None, 1, 1]bksl-nlS = [None, 1, 2]bksl-nl...bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert S[1] == 1bksl-nlassert S[2] == 2bksl-nlassert S[3] == 4bksl-nlassert S[4] == 6bksl-nlassert len(S) >= 10000bksl-nlbksl-nla = [None, 1, 1]bksl-nlS = [None, 1, 2]bksl-nlbksl-nlcumul = 2bksl-nlfor n in range(3, 10000):bksl-nl apy-undn = a[a[n-1]] + a[n - a[n-1]]bksl-nl a.append(apy-undn)bksl-nl cumul += apy-undnbksl-nl S.append(cumul)bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert S[1] == 1bksl-nlassert S[2] == 2bksl-nlassert S[3] == 4bksl-nlassert S[4] == 6bksl-nlassert len(S) >= 10000bksl-nlbksl-nl

A

Pour aller plus loin⚓︎

Il existe un algorithme pour calculer $S_n$ sans avoir besoin de calculer tous les précédents. C'est un exercice très difficile, où on utilise de manière surprenante le triangle de Pascal. Par exemple,

\[S_{10^{18}} = 257\,124\,935\,176\,141\,732\,152\,547\,069\,538\,475\,658\]

La méthode ci-dessus aurait besoin de la mémoire d'environ un milliard d'ordinateurs, et d'un temps de calcul de plusieurs dizaines d'années. Avec un bon algorithme, c'est quasi instantané.

Z

Histoire des $10\,000\,\$$

Le 15 juillet 1988, pendant un colloque au laboratoire Bell, John Conway a affirmé qu'il était capable de prouver que $\lim_{n\to\infty} \frac{a(n)}n \to \frac12$, mais que la preuve était extrêmement difficile.

Il a alors proposer d'offrir $100\,\$$ à quiconque pourrait trouver un $n_0$ tel que pour tout $n\geqslant n_0$, on a $|\frac{a_n}n - \frac12| < 0.05$, et qu'il offrirait $10\,000\,\$$ pour le plus petit $n_0$ satisfaisant. (Il aurait voulu dire $1000\,\$$). Le prix a été gagné par Colin Mallows, qui a accepté de ne pas encaisser le chèque.