Aller au contenu

Suite Q de Hofstadter

Le cadre

La suite Q de Hofstadter ressemble à celle de Fibonacci ou de Lucas, chaque terme est la somme de deux termes presque précédents.

La suite \((a)\) est définie par :

  • \(a_1 = a_2 = 1\),
  • \(a_n = a_{n-a_{n-1}} + a_{n-a_{n-2}}\), pour \(n \geqslant 3\).

Personne n'a prouvé que cette suite est bien définie pour tout \(n\in\mathbb N^*\).

On ne connait pas son taux de croissance.

Exercice

Coder une fonction suite_Q qui prend en paramètre un entier n >= 2 et qui renvoie une liste de longueur n des termes de la suite Q de Hofstadter.

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

  • ⚠ Si un terme d'indice k s'avère ne pas être défini, la fonction provoquera une erreur avec le code suivant à utiliser :
    • `#!py raise IndexError(f"Le terme d'indice {k} n'est pas défini !")

👍 On utilisera None pour le terme d'indice 0 qui n'existe pas, mais qui compte pour la longueur de la liste.

Contraintes
  • \(2 \leqslant n < 1024\)
  • 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)d63Am(P+2-],59fq!7}8 N_o={pcwgQv41kIéhtsSL[ji:E050p0m0#0l0+0k0$0J0Q0k0l0$0$0N010#0+0P010406050$0n0t0t0l0e0j040%0M0k0n110M0g050c181a1c1e160P04051u1n1x0c1u160p0+0U0_0{0}0 0!0+0S0!0k1L0!0#14050;0h0k0m1G0|0~011K1M1O1M0#1U1W1S0#0e1v0#0!1Y1I010D0?0m0g0l0t0m010_1h0$0P0l0g0 0x1S23251?1!1_1W1|1~140a0J0v0e0M0P0M0$0+1k0g0J0/210e0e0m0Q2s1n2a0g1v0c1;2F1.1:1/1T0p2c0 1O0g1{2p1S1D1F0`1Z2P0+2R0g0M2V1S0P2y1v2D2F2-17242t2X1@2$0e1b0k140W2C2;152:2b2?1!2^2`140x2~25302D2O01350l2{040r392E163c330 3f3h0V3k3b2;3d3q140B3t3m3v3o3e0M2_3g140q3A312=1H343F36040G3K3n3N3p3P3H040I3T3C3V3E3G3h0C3t1y2+1n2V2I0p1:2N3D0Q2%1 1v3:1w3.2/1o2 053_0/2,3$2Y010X140/0D3,3U480R140J4e472@0D14182r0m0L0T4k323%13040u4u3M480g141m413a3L3d4x0o0,3A0J4O4j4f2@144t4G2E4Q4l1!0M140N3t4X4v484x0)4A3d0X0Q140K1l0m4-3D4x0A4%4I3D0t0+2|4^4w144{4V044(4B1@4 51564}53040z4%583d0Q0W14030J2!2r0+3g0+0$0l2B56064P5j3D4a040D3F4|4R34140X5H4Y0 0M4h042!5M4)2@0h140e250S4@5d5I0 4x4z5$5N015b3i524*545T595J044F2/5%014K4M5y5A5A5e4C140+5?3d4!044$565B3%4D045L6c631@690y673D6f4U5{5,4+5:4S6g6n3%6l6x485.2}5+5U1!4x5h60614O6j5^0*6A6k4#6P5^6h2-6d486z6i5|6p6u6G144,6E5@3p5K6S5O146m6Z5,5.386*4J146I2-5z6K6W1@5D0+4d6=6F5(145*6r763e656.0169020k0#0f7e6C6$77040o7e5P145G756+5}787n7c046O7v68147h7j7l50046D7a7w5~4N6 625|5D5Y5u5#6V6M3p3{0Y0g0/0b0-2x7u7M6`4y7z5v14747,3D0$2804010(1X0#0m2_1X0p002!1D0Q1X7/7J0O7z6f6U425|2q140H7/7_0J0g000m0$0#0J240^0p0Z1_0g0+0J0F017z4K7P6K7Y7A6q8e5,690d8b140l0P0P1{0p8C7y6_6o4T8U046)7?6e7d8W5f6|2 704Z140w7e6#8)5;8!8N7B8Z0z7q6J6L7S5X0:0n0e5`8,8G8=6}1n440m2F2*9c3/1E3;2I2L2G0l1V9f0c3:169p0:0=0@302V3d0l0p0t1l5r1l5p0g5F141t9y9A9C2s0y110#1,040s0U2z0J0n2R0J0Z0Q0!0m0k1W0J0k0M0S1c2r0!4 0E0n1X180e9*8o2u0m0n0b0J0l0b8o1y301u0i2t0M0h0$7 9U0J9=000l1j0M932u0n8r0:2r0_0!0l2p0A5p0k0J0ja09W9Y7~7$25868l0:7~8M1Aa51v0+0t0Sa07i0 200$0e0Q0 ab0E0y0T0d0P0g0S010c9d309p9h.