Aller au contenu

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
###
# testsbksl-nlbksl-nlassert S[1] == 1bksl-nlassert S[2] == 2bksl-nlassert S[3] == 4bksl-nlassert S[4] == 6bksl-nlassert len(S) >= 10000bksl-nlbksl-nl# autres testsbksl-nldebut = [None, 1, 2, 4, 6, 9, 13, 17, 21, 26, 32, 39, 46, 54, 62, 70, 78, 87, 97, 108]bksl-nlfin = [26303585, 26308945, 26314305, 26319665, 26325025, 26330386, 26335748, 26341111, 26346475, 26351840, 26357205, 26362571, 26367938, 26373306, 26378675, 26384044, 26389414, 26394785, 26400157, 26405529]bksl-nlattendu = debutbksl-nlassert S[:20] == attendubksl-nlattendu = finbksl-nlassert S[(10000 - 20):10000] == attendubksl-nlbksl-nlbksl-nl ∞/∞

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.