Aller au contenu

Suite H de Hofstadter

Le cadre

La suite \(H\) de Hofstadter est définie par récurrence de la manière suivante :

  • \(H(0) = 0\),
  • \(H(n) = n - H(H(H(n - 1)))\), pour \(n > 0\).

On montre par récurrence que chaque nouveau terme \(H(n)\) est dans l'intervalle \([\![0\;;\;n]\!]\), ainsi la suite est bien définie.

Exercice

Coder une fonction terme_H qui prend en paramètre un entier positif n et qui renvoie le terme \(H(n)\) de la suite de Hofstadter.

On pourra travailler avec une liste H_mem définie en dehors de la fonction. (Oui, c'est une mauvaise pratique ; c'est volontaire ici.)

\(H = (0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, \cdots)\) ; suite OEIS A005374 :

Contraintes
  • \(0 < n < 10^5\)
  • ⚠ Nombreux appels à la fonction terme_H
  • Fonction récursive interdite
  • Modules math et functools interdits
  • Code source limité à 2000 caractères
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞
.128013x/.r;nbOylaeïu)d63Hm(P+02è-U],59fq!78 _o=pcwgv41kRéhtsSC[Di:050q0m0#0l0+0k0$0M0R0k0l0$0$0P010#0+0Q010406050$0o0u0u0l0e0j040%0O0k0o100O0g0M020l0u0Q0f0M0Y0m1a0e0I0o0m0$050c17191b1d150Q04051I1B1L0c1I150q0+0U0^0`0|0~0!0+0T0!0k1Z0!0#13050:0h0k0m1U0{0}011Y1!1$1!0#1,1.1*0#0e1J0#0!1:1W010H0=0m0g1o0m010^1g0$0Q0l0g0~0z1*2g2i241=271.2a0u2c040a0M0w0e0O0Q0O0$0+1j1l0.2e0e0e0m0R2G1B2n0g1J0c222S1 21201+0q2p0~1$0g292D1*1R1T0_1;2$0+2(0g0O2,1*0Q2L1J2Q2S2}162h1l2.252?0e1a0k130M0W2P3114302o331=3537390z3c2i3e2Q2#013j0l38040M0s3n2R153q3h0~3t3v0M0V3z3p313r3F390F3J3B3L3D3s0O363u390r3Q3f321V3i3V3k3w0K3!3C3%3E3)3X3w0L3-3S3/3U3W3G0G3^3g3`3N040W0y3 3$2/3{3*0W3b1C3d1M2{1B2,2V0q212!3T0R2@2v0-1S1J2`0m2|4e4d3o054o0.4w40480g130t0N2u0u3J0M3#3r0O130P4M4O3T12040)3J4U3`0u0+13454y2R4!484W0D3Q3R4E250X130.0H4Z3.480S394{3_4F0H130#0m360m0N0t504=1=4W0v5b4734130g5g3r4W0p0,463r4~3w0M5u5l3T0$0q13015B5q5x5z5t5u0(0O1p0k0A550E0M2E0M0h1z0O2;5O0`0M1$0$550M4I4K5D3`5y395u1s290U5U1/1.0M55575$4J1u0)0g4/4*3K5c0~5+5G0M5B013Q5-4N4|4?130H3V4T6c3i130X6h51250O5s2;6m623s0h130e2i0T0m5w3`5e6B4F6v042s6E256D604,5i045%1u6J5d130p0E6s5h6j045k606b6n1=4Q040x6X3r4$134c2 6i0~5n5p60066a6a6N6Z4I6l6$6~0~6*4S726?3s6k6-3T6*0B7b414H5{4L6M784W4Y7k6(3E7h5(7o6t7m6S7q6P7i7w017v7t6Y7x712}6%6t7d7f486/437A4.0D5 2}6{6|5v784G7y7s6=7p016*0d7A7Y0l0Q0Q290q7P135f7D3M7h7G4e7l6U695-73014@042L0#0o0e6#7H807Y6Q7j7#7u137n8e7E796!7;047S3d150c4B4v4f8t0c4i1B0#4k8y2Y2T0l1-8v4i1H4D8j2L0u0N0H0l0X580!0s131t1v1x1z0M6_2 1O3e2,3r0l0q0u1k2F0+1k0M0q6y56131H8)8+8-2G0B100#1}040w0{8;000m0H0H0/0@2I0h3V7:8$8I0i1l6x7-0m0k5?8X0^965!0M0o2(0M1a0o0U0;0$1/2`0l109p2I1 0l9z0=1.0e0M9J2M9t9v5Z5#0q0Z270g0+1/298;0m0!3V9b5=0l0M6f0g2N8/0g0d9?0M0*1/2?0u0h2L0o0b0M2`0O1-0A2u0@9#0U1y0M0Jac1M3e1I0w0O860M0T1b0.9N9u1/1i0=0+0$9E9;5P0+5K1/2I5X9.9:8:4A4p045^2u591B8s045Oap5P1gar8:0Z0k0Zal0g5#1z0#95ar5Z569R1/3h9!1l0w0i0i7)9g4r2-3`1@1#1%1)8J3r2r292b132x0%0R0e11a$0w0j221k4Z4u8J2~4eaN80823h7A5s4N7@3T9/4H0O0H5!8*5^5abr6C138!8p6}78824_bo4 bB480H0u130N0N2;2FbR8m7?8i3r0h4W9B0k4`bM6K6UbE3o7U7V800R0W13035P0o7-3Va$2I0u0Z8,0nau2G0M0v9T1/ai8;0+aE0g2a0+2L0p7~b/78b!13b$b(bY7c13a?co7g7Z6R777$757Lb*4X7A7N4)cs4-138ob-b.7I8jbI97bK3w7AbObQ0N0R3u0kbVb)6T04bX7{7$ck04cm8m6Wcw6t7Y88c%8f045och6|bl6e6gc.8j7Y7`3ocL4P6qc;d28a6G6x0g6zbW7*6G6IcZ6@7=7Ac)c+dh7%cq7*7rcvcFcA6Vcz6Zd62Rd3cp6+dw0~7N6;c=8j6^c_7V7W7$8b0Nd1dz80cyc~7^04dQcQ787KdU3Tdl9mcndH4PdpdndO7!d*4V8gdkb#d(7A7(dqcu8dd:bCcBdnd%b%d_d,dt6 7zdn7Ce67FdDdo047ed#4#4%7Oe9cH7RdKdL80e2d)4zdZe5d~4Fdrd}etcxeveAc/137,7.0g9feb7Bdjd-7_8mcg6`cKbG7$828486dydYc(d@e3dnd`eNd|8m8hew6OeY804.4:8a5456aKbA89eu0476e{dNbubw0:0qbzbWeQ7T064;8jb;b?0M0C105Zavbe6`c{041;560#ed7YaJ58e`e-c!c$eD8jdFcEfvdic@ed75e~3ddAei133,fk8raH8u2S8H4h4s8q0.0:0=0$04.