Aller au contenu

Suite G de Hofstadter

Le cadre

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

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

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

Exercice

Coder une fonction suite_G qui prend en paramètre un entier strictement positif n et qui renvoie une liste de longueur n des termes de la suite \(G\) de Hofstadter.

\(G = (0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, \cdots)\) ; suite OEIS A005206 :

Contraintes
  • \(0 < n < 10^5\)
  • 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;nbOylaeu)dM6z3m(P+02-],59fqZ7}8 _o={Gpcwgv4F1kRIéhtsS[i:E050p0m0(0l0,0k0)0L0S0k0l0)0)0O010(0,0R010406050)0n0u0u0l0e0j040*0N0k0n120N0g0L020l0u0R0f0L0!0m1c0e0G0n0m0)050c191b1d1f170R04051K1D1N0c1K170p0,0V0`0|0~100%0,0U0%0k1#0%0(15050=0h0k0m1W0}0 011!1$1(1$0(1.1:1,0(0e1L0(0%1=1Y010F0@0m0g1q0m010`1i0)0R0l0g100z1,2i2k261@291:2c0u2e040a0L0w0e0N0R0N0)0,1l1n0:2g0e0e0m0S2I1D2p0g1L0c242U2123221-0p2r101(0g2b2F1,1T1V0{1?2(0,2*0g0N2.1,0R2N1L2S2U2 182j1n2:272^0e1c0k150L0Y2R3316322q351@37393b0z3e2k3g2S2%013l0l3a040L0t3p2T173s3j103v3x0L0W3B3r333t3H3b0D3L3D3N3F3u0N383w3b0r3S3h341X3k3X3m3y0I3$3E3)3G3+3Z3y0K3/3U3;3W3Y3I0E3`3i3|3P040Y0y3L1O2}1D2.2X0p232$3V0S2_2x0/1U1L2|0m2~3f484i0:4q422;010Z150:0F483:4x0T3b4D3{4x0g0F15192H0m0M0Q4I4w2714040v4T3(4K150g4Z3t4W0o0-414!274G3y0L4=4(3V0)0p15014|4-3t4_3b4=1u2b0V0N0,1;0|0L1(0)0(1;0:1C1E3f3T4U1@504;52521n4o0u570e0_5d381B0L2K594O5d0L4S5h3q5j4.5l4`5n0L4|013S5o3%3O155F2 0L5S3V0N150O3L5X4E4V150+4@3|5s15475G2T5Y3|4W0B5Q525@4x4z040F3X5%5}36150Z635)1@0N4:2?684J360h150e2k0U0m5-4x4W4Y5=4v5J105/456n5*040C6e5k3G4$6x1@4*4,6r065o5R696D040Q0M676r5(6f6a5#6B6t3u666Y3t5!040A6$3V0g5U6F104W5,6r643k6.6?6N016;6/6!046S5W6@106(6*6T73016v3d6`6V6:150B5`6J6L5|6{6-6P6~6(0d6~7m0l0R0R2b0p6~6p7r5U6R7y150o5{4?6{5 2N0(0n0e4%777l6_2 170c4t4p497W0c4c1D0(4e7#2!2V0l1/7Y4c1J6s3t2N0u0M0F0l0Z4Q0%0t151v1x1z5y6I311Q3g2.3t0l0p0u1m2H0,1m5z6k0m0e151J888a8c2I0A120(1 040q4j0L0m0b7v0e0(1O3g1K0#0k8x0b0,5c1;0n1n1(2b8x0g211;0S0;5D610g2P8e1n0;5X0l0L0%2N0F100d0d0c8/8;8:0E0y0A1c240c0W8_0s2O7`0g0p3X0F0c151:0_2N2|0$0)2b0=2I0_2K0H917w951D0l047q85170n0k3g1(040i1n0$0S0e2H6U6C011d2H0%8{8y15090v0g097F6T4i1b1;0)0N9V5z1;2^0u0h2N9i1;0X0,0h1m0l0S0S0,5z8K128Z0(0_8%2^341m0)9B1k0,0F0)7q9u9w0,040.0b1w0R1:0L0-9F6Z9I249L0b9N0v0D0K0L0O0L0D0D0L0x3zat0L0X0M0P0Y0Y0JayaC0M0W9R480c9x7Ta87TaQ059x9z0L7=af9:8U0%0l810L9$9(5e9+9-9/9;9?2j0e0L9X5q0e9B0$0:8S0L0v0)0l0n0Faj889Dam0l5dao049OaD0YaN6r7FaSaVaaacaeagai78al9Kba9Mbd0v0Qaq0K0oaBaDaF0yaIazaD0taB0t0WaJ0zbK0rbh84aU0cbkaPaaaR9v7/aX8b8S2N0Lb30~9?a)brb8btbbapby0g0obR3f8x5c5a8)211m0Sba7Ma-b63Vbsanap090p0F6j0S0P1nazaH0P090V1d0R1!0Jb_3q9r1R4b4m7T0:0=0@0)04.