Suite à 10000$ de Hofstadter-Conway

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.

La suite HC à 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\]

Exercice

Coder une fonction cumul_HC qui prend en paramètre un entier n >= 1 et qui renvoie la liste des n premières valeurs de $S_n$.

$a = (\texttt{None}, 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, \cdots)$ ; suite OEIS A004001 :

$S = (0, 1, 2, 4, 6, 9, 13, 17, \cdots)$

On utilisera None pour le terme d'indice 0 qui n'existe pas.

Contraintes

$1 \leqslant n < 10^6$
Fonction récursive interdite
Modules math et functools interdits
Code source limité à 2000 caractères

Évaluations restantes : ∞/∞

.128013x/.ùr;nbylaeu)dM6z3H^Am(P+02è-],59fq7B}8 N_o={pcwgv41kIéhtsSàLC[ji:050p0m0*0l0=0k0+0P0W0k0l0+0+0T010*0=0V010406050+0n0x0x0l0f0j040,0S0k0n170S0h050c1e1g1i1k1c0V04051A1t1D0c1A1c0p0=0Z0 1113150)0=0Y0)0k1R0)0*1a050`0i0k0m1M1214011Q1S1U1S0*1!1$1Y0*0f1B0*0)1(1O010J0|0m0h0l0x0m010 1n0+0V0l0h150C1Y292b1|1*1 1$22241a0a0P0z0f0S0V0S0+0=1q0h0P0^270f0f0m0W2y1t2g0h1B0c1`2L1@1_1^1Z0p2i151U0h212v1Y1J1L101)2V0=2X0h0S2#1Y0V2E1B2J2L2?1d2a2z2%1}2,0f1h0k1a0P0#2I2`1b2_2h2|1*2~30320C352b372J2U013c0l31040P0t3g2K1c3j3a153m3o0P0!3s3i2`3k3y320H3C3u3E3w3l0S2 3n320r3J382{1N3b3O3d3p0L3T3v3W3x3Y3Q3p0O3$3L3(3N3P3z0I3.393:3G040#0B3^3V2(3;3Z0#341u363K3_413{0#3f463h48402}3*3o0#3r4e3t3U3F4j1a0#3B4n3D494i3=4s3I4v1E2;1t2#2O0p1_2T3M0W2-251B4G1C4E2^4C4M0^2=3/410$1a0^0J3C4p3M0X324(3%4a0J1a0W1f0n0k0R0u0/4-4Y1}19040y4|4x3b1a1s4C4.4~1a0o0?3J0P5e0P4)3`1a0l3C5g581*0S1a0T5l5h414 0:524h1*0$0W1a0Q1r0m5x3k4 0G5s5n150x0=4s5G3M5I5K4}1*5N5P575U154 0F3J065f5m5Z014!040J3O5T533x1a0=5;5y150S4+042*5_3F0i1a0f2b0Y5F5Y5=014 51685`015W044m2^5L6a1a5J4v5*690h555Q3:4 5b5d5)5f5t2}5j6t415p040d6D6B040l0V0V210p6I1*6b6Q5?6K6T6l045w6d3F6C6!5R1a6Z6j5+6r5~603M6F0E6/3:6g456+695#5$6o6A5o1a0A6?4a6$6`6e5v6W6-5^6~6k6;736J5k6%6u6)795@7f70046=7c5+6^6W6|0o5%5)6 150W0#1a030 4?0k0P210P0V110W672?5(6z6k6-7h765H7k7i416g3~7Y59046}2?6p6e6F5r7r697!6x5e7z5,1a5/0f7n6U7b7*7@5|5@567 7S6204640h667u1a6c7V3M7t7$6R6m7|3l6s8h5!5a5c4v7Q6y7+6#6V8n6X6*367@7a8b7(8k6F0A7.846,758A6k788x8C7/7,1a7q8J7:5O3|8D7)478s8u4L7C047E2w0P110P1e2x1%0m0+0*0P1@2t8-1r0Y0n1%0y2u0n0f0P2z020k0*0g3q7w8r7y6k5-0X1Q1$8k0h862l8D8d8M8K8w8e7j049c8V8S04020Y999k8m9t5u1a8q7P8t7?7S8L3h801a6H8P1a2u0V9o9w479e5+5-2E0*9383368%5i9s9*9+417B7D0 008?8^8.8:0*1%0,3T0c4V0m2L2:a24F1K4H2O2R2M0l1#a50c4G1caf0_0{0}372#3k0l0p0x1r2x0=1r2A650m0f1a1zaoaqas2y0E170*1=040q4N7I0b6N0f0*1E371A0%7H0m0b0=8@1%0n2z3n0Y3O2x0)247K0S930 3n4=1$947@1ia+1h9|0b1a090y0,0R0h099X3h8/2b0~0l0Z0S0=940i8?bd2z2B0Wa=4@ay8_a/0~1$0~2:0(0W0(0^0h0*0+0d0P0/9@8@0Pa$aNay0W0=7N5m8`89041@0D0+2IbP0Y3p1J0J1 bL1$0G0P0S0eb)2z1p0|aZ1%2B1h0h0=0D2E8/93a422bz1%1$8_0f0=65c12B0z12bl0k9R1H1C04c894aX0m0x7L0mb(aS1I1Kaoc31`a|aXa 0:b20U3}0vcz0O0N0N0P0T0P0C0H0L090G4c0!cM0I0t0HcM0#0L0rcU0!0#cM0L0t0CcU0Hc(0G0H0!cL0G0B0r0IcM0H0t0OcMc.cT0G0r0Hc`6}agce0.0l0P0x0(1`aMbL0E0^130nba930{8^bg0+bi2Ac0d6d8arbeb;9@0h0ZbeavbI5N0k1U1i2T0p003O1J229|930+b(0_2A00bI9|ck0~bkbm7H2B7Ldg0=0mdM2A0=0s0{2XdV002b0h0(8?bC0w0Z2FbH2z0iava(a*ctcm9?9^0P0K0n120=0P2*8@2b0`d;bC0Mav4Mdi660P9a7N8^ci0fbLbNe40f0(0+ay0Z0(0P0l0n0b0P0U0U8-2*0$0RaX0*0y9@aOaybA00b(000XeW0d290S0;0d4M0x0c880$0+0c4`3}0Be:0c000o0PcEccaT1B0=0x0YeB9815260+er5{1p0V1p0d0V89010ca3e{0,a:8.ej0fbg0P2Ebuexbz0l17d_do9/1}a`ctfscv04b00C0lb30P0Eb4b62Kb(av6N1p270hec9|94dA0S170J0P0J642G3ne50ne92E13cjad0P0-8-d605d60)2E0J1P1:0V0+0?0c0cf!0d0X0=0$180m1J0l0d3O0Y0cg4g60c0/a/fl0m0R0p0n0R1#2b0W0Eb?66az04fkfmgn0P0M110hgsguay1t0l6Gcoce0/dXboa_csa,fAa~fCb1b3b55l2Edx218^f:0+bbbd94caa?bo0kd/dt8/bq0 0_9|2793bge`ah4G.