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

###

Lancer # 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 = [bksl-nl 26303585,bksl-nl 26308945,bksl-nl 26314305,bksl-nl 26319665,bksl-nl 26325025,bksl-nl 26330386,bksl-nl 26335748,bksl-nl 26341111,bksl-nl 26346475,bksl-nl 26351840,bksl-nl 26357205,bksl-nl 26362571,bksl-nl 26367938,bksl-nl 26373306,bksl-nl 26378675,bksl-nl 26384044,bksl-nl 26389414,bksl-nl 26394785,bksl-nl 26400157,bksl-nl 26405529,bksl-nl]bksl-nlattendu = debutbksl-nlassert S[:20] == attendubksl-nlattendu = finbksl-nlassert S[(10000 - 20) : 10000] == attendubksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

a = [None, 1, 1]bksl-nlS = [None, 1, 2]bksl-nl...bksl-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-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.