Suite de Hofstadter Figure-Figure

Les suites Hofstadter Figure-Figure \(R\) et \(S\) sont des suites d'entiers non nuls, complémentaires, définies par :

  • \(R_1 = 1\), \(S_1 = 2\).
  • \(R_n = R_{n - 1} + S_{n-1}\), pour \(n > 1\).
  • avec la suite \((S_{n})\) définie comme strictement croissante contenant tous les entiers absents de \((R_{n})\).

Les premiers termes sont :

  • \(R = (1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260, \cdots)\)
  • \(S = (2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, \cdots)\)

Construire deux tableaux de taille au moins 10000 éléments chacun pour stocker \(R\), et \(S\). On les débutera avec None pour \(R_0\) et \(S_0\) qui ne sont pas définis.

Exemples
🐍 Console Python
>>> R[3]
7
>>> S[3]
5
>>> (len(R) >= 10000) and (len(S) >= 10000)
True

Warning

On n'utilisera pas ni les ensembles, ni les dictionnaires.

On n'utilisera que les deux tableaux à construire comme structure de données.

On n'utilisera pas de boucle pour déterminer l'appartenance à \(R\), ni le test x in R (qui revient à faire une boucle).

On construira plutôt R et S à des vitesses distinctes, chacune avec leur indice. Il n'est pas interdit de modifier un peu l'initialisation de R et S.

###(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 : 10/10
.8212.128013sHY3_8ufvIy 7nGaêS1me(P4C2:twi]D[hE)6Oo;bcdgM?/0làqABÉp.rL-,=+Nzk%9ö5Rxé050S0w0D0r0F0Y0c0n0R0Y0r0c0c0.010D0F0(010406050c0i0v0v0r0*0m040t0O0Y0i1d0O0p0n020r0v0(0P0n0`0w1n0*0!0i0w0c050W1k1m1o1q1i0(041O1V051Y0W1Y1!1V1i0S0F0k1517191b0J0F0T0J0Y1=0J0D1g05100Q0Y0w1-181a011;1?1^1?0D1~201|0D0Q0O0S1q1}0*1W0D0J151t0c0(0r0p1b0B01221/010j120w0p1B0w1|2q2s2x242A202D0v2F040b0n0y0*0O0(0O0c0F1w1y0~2o0*0*0w0R2!1O2H0p1W0W2m2:0D2k2j2l0S2J1b1^0p2C2X1|1*1,16232}0F2 0p2g1+1|0(2)1W2.2:3h1j2r1y352y3a0*1n0Y1g0n0u2-3l1h3k2I3n243p3r3t0B3w2s3y2.2|013D0r3s040n0f3H2/1i3K3B1b3N3P0n0z3T3J3l3L3Z3t0_3%3V3)3X3M0O3q3O3t0M3.3z3m1.3C3?3E3Q0o3{3W3~3Y403^3Q0h443:463=3@3!0@4c3A4e3+040u0X4j3}364f410u3v1P3x3/4k4s4m0u3G4x3I1X3f1O332?0S2`3L0R2g2P0}1+1W3e0w3g3x3%054P0~4X4A3o1g0`3%0n3|3L0O1g0.4,4.3;1f040I4Z454s0=0R1g0:1x0w4|4d4s4_0-4?4}2y0v0F1g4w3j5b24585a565c5e043S4F2/4@4e4_0G4q3*1g0t5l4(244:044=5r3Q5t571g4{5H5J2y4 5153555C1b5k5H4-5i1b5d1g4E5h5m5j1g595X5O245#043$5N5Z015W3h5Y5)5!5o3-5?5|5^5+5B4r5n1g3`605U62045w5H4z653C1g0F0g0*644/4;6m3;5:5%3x0n5{6a0R0u1g030n0Y00381*0R210S0i0n0~0*0p0F0w0*0n0|0Y0|2O0p0D6K214+6e5.3Y1g0*0g1k1+2s0D6p4e5E5G5`6$015:436#5@0=1g0E1;206/4B6i6k722y5E020Y0D0P765/5o4o0X7h5T6g5V1g0C3.6u6u6@0p4*7j6n040)7u3;7s040r0(0(2C0S7y5u1g0x7H73046)6+0k6-7L2y4_0L7o7p7r746l5-5@5E0/6=6t6@5:5g4y7p6v7k3M1g3e0O0R0J110p7d1b6;7}7=046!5(6a4_5M847;7A6j7!883L5v807%807A5A697;867S6h048b8o7l6c7W7q6|6i0j8i0Q1g2M8s6b7K8l5y1r8E7U8g1g797b807,7h7i8H4^7m8v7/7:3L6}040j3?8i1g1N7#610O0E6i7|8,6a0p8B7N2s0T548U7I048G8d7z6(6*0i6,6W8M040/8Q7f8K638=897?2U7_7{9d040L7n6e8Y9q8Z928J8}4s5E7x9v4)7B7D7F9l904Y5@7A8+918~7V9p7X9H937P7R9f7v7)3I9s4l9h7^7`383{0W4#4W4H9*0W4K1O0D4M9/2^2;2f2h2?0r1 9,4K1U4%7;2)0v0g0j0r0=0w0g0J0f4*1H1o1K1M0n9o3j1#3y1V0#6J0S0|0Q1v5,1(4S344e261@1_1{a03L2L2C2E1g2R0t0R0*1e6X0y0m2m1x4Z4Va03i4Y9)aC9t837*7$6o9T8V4`8E5Q04522 9l5,6?5@7,9l6d3h6f8I8ka=8-a%a~855La+50a-5S9z5*04a;a#616ra^9%aX9+2:9~050i0Y3y1^040N2#0|6I2Z4-aX0`0I0B0G0n0.3R1OaX9ybp1ibp0+ag6+0DbM1x6X1j2@1x0T044P1C6T6V100F2)9JbT0pbV0-6K1x0R6B002C1d6Pbw4Q5;bFb_0n1M6X0S2s144!b_6!aX0n0O6Jc34$8kbGblbnbJ0F040l0Y0n2 0n7E1vcn180n0s2@6Hc1b^4$c5b|1E20cn9i9#1y0c6P0rcx4W0f0n0/0n0VcQb{4$0n0x2r140ub,6N0n0B0Lb,0Sb.0n0r6J0v0O38140MbHchcg040#c:0FcK9uc6cHcnc80*bNc+0k2*c}5=c60 c}5 c60)df1ObI1Obm3y0Wdi0Wdk1)1+3Lay281`2G61aE2N2PaIaKaM2SaP0JaR5NaT3|aV4Gbh9P82989V2/9X5Ka*b81ba,a.8|9KdUbb9W7+9cdW6bd%dSd)1g5qd#7T1ga_4y7Y9ub17;7 a(8~879G61dYb7d=b9d-5Ia?5o6s4G5@5_bc6a5:5=e68te8dT66045 ek6bd^3I1i9(b_bi4J4T1idp05bpbr6Kbt95bRbx0I0fbBbD6`da6Xafc}68da0cb cwca4Wccb_c?boch0H210Y0Zb,1xcn0wcp382Z6O6Q170n2f0i16212CdEaQ0pe%eveC33ds1_duaB6@dyaG2Q0naJaL0(aNdFdH3jdJaj3jdN617Aa!d(a$5F808nd+e4a/d+effvbdd*erfEd.ead:bf5Xen246x6z0n0o0n0Z0nd66N8cd_dOa}egd}b0f(8eb3fAb5dZa:9b5$f;d 4seif@d|3L5:eqe2b2baf=0468fId@bgex1#4I9-eAav3L0r0Sc.6N2!0n388%1g1Ugfgh1xe@1x0,1d0D2c040q0K0$1Xal1WcJ0J2)0j1:2a0(0c0C0W0W0j0*0)0E0F0=1e0w1*0r0)3?0T0WgUgW0W0Hc80T1.0g0d0O0jeWggbO0*1gg,0ig.crg;g?100Sg_1O0r3Qb~b:c,bO0i6Q6I6B1+2)4-gGgIgK0DgMgOgQgSg)gXgZg#0*g%hr0W0q0?0A0f0?0$0M0~0Y0-0g0K0c7_6PhI0$0r7_0g0C0gbL0c0g0$aL0phW0S0?0B0o0i2 0g0q950*170p0~0ghAhC0h0@g_2 0Ygy0q0^hGb,hKhM0*b,hP7_ah0nhV0nhYc:6K00h*21h-b$h:2$0%h{0wh}8|h60n1Kc|cJ0O0QbO0p6JcC3e0F0{2Sbm2Z0;6P9yau1VeF0m0nbT0id6b}1y2r0*1d0RiHb@6GiX7{bMeIag0|0D1x2D6W1MiLgE05cJ3;g.aA2f0{2wc010gv0m7E1b0F1n8{i~0rj0gUh30J1bha4:6Kj90r0,0J0waAje1vjggH0wgJ25gLgNgP9)0{0)8%hv0w0)7CgM0)gYe}j90F1xjA0*gQ0F7_e^0c0W2C0g2@0r7Q0i0{0W0Ja41=hc0wjU0{0O0g0`0K0Uhy4Q0Y0g1Mi40g0QhQj%9{5d0T0*1B0)0(b*j8j00~hL0,2W2Y2!1b2f2a0O0v1|j50Tc+7a1b0y1o0n0U0riFhYc,1y0a0n1`hmjwg(0E0EjA1^0R0=gSbX1#dGi-jT1n0{0Qk3h*0W0f0u0@0M0M0@0@h(0zb,0A0Aic0e0,0t0#c#0)0Xb,kChnjxkjgi0cgTgVj5gY0Fg!g$g(0W6E0wjz0(0J0(0ViZaL0S0.0o0_0f0z0@0o0M6y0n0c0*0Rhlk{ew0~jzjB8{jE7Dk jI0RjKjMgRjPjR6PjTjVjXjZj#j%2A0Tj*j,j.j:j=0qj@j_hLjl6)j}hRk01=k30vk5k72:h6gD1i1 7^0=1K0ObOgE0#0v0Ql.1B2O0n0q0n0Kicb,e?1d3Oag2$h i1m9l(b@dbi72n3e0|cH6Wlshc6Bi^c8d6iXj*6KiBhgcvh!b:btgt2#21kZ0o0@0)2SkskukwkVf3l^1Ol`kKl}l evbk9-0 111304.

Indice 0

Ne pas hésiter à regarder l'indice 1 si vous restez bloqué trop longtemps. L'indice 1 ne donne qu'une petite piste, mais qui peut bien être utile.

Indice 1

On pourra commencer avec les valeurs

🐍 Script Python
R = [None, 1, 3]
S = [None, 2, 4, 5, 6]
On cherchera à ajouter une valeur à \(R\), et plusieurs à \(S\).

Indice 2

On pourra ensuite suivre l'idée

🐍 Script Python
i_r = 2  # l'indice du dernier élément de R
r_suivant = 7
while i_r < 10000:
    R.append(r_suivant)
    i_r += 1
    prochain = ...
    ...
    r_suivant = prochain