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

.128013.8212:LpM%(40zed3;N 1Eo5_Aên)Bh]6,qcG[yCuvàHi2+DxmYs7=öÉwlSIatf-9ORrg.é?Pkb8/050m0l0*0)0P0$0W0q0G0$0)0W0W0Y010*0P0e010406050W0L0U0U0)0:0J040%0t0$0L1d0t0y0q020)0U0e0o0q0/0l1n0:0F0L0l0W050|1k1m1o1q1i0e041O1V051Y0|1Y1!1V1i0m0P0M1517191b0B0P0;0B0$1=0B0*1g05100`0$0l1-181a011;1?1^1?0*1~201|0*0`0t0m1q1}0:1W0*0B151t0W0e0)0y1b0Q01221/010+120l0y1B0l1|2q2s2x242A202D0U2F040a0q0^0:0t0e0t0W0P1w1y0~2o0:0:0l0G2!1O2H0y1W0|2m2:0*2k2j2l0m2J1b1^0y2C2X1|1*1,16232}0P2 0y2g1+1|0e2)1W2.2:3h1j2r1y352y3a0:1n0$1g0q0r2-3l1h3k2I3n243p3r3t0Q3w2s3y2.2|013D0)3s040q0n3H2/1i3K3B1b3N3P0q0i3T3J3l3L3Z3t0u3%3V3)3X3M0t3q3O3t0D3.3z3m1.3C3?3E3Q0X3{3W3~3Y403^3Q0{443:463=3@3!0-4c3A4e3+040r0j4j3}364f410r3v1P3x3/4k4s4m0r3G4x3I1X3f1O332?0m2`3L0G2g2P0}1+1W3e0l3g3x3%054P0~4X4A3o1g0/3%0q3|3L0t1g0Y4,4.3;1f040I4Z454s0_0G1g0p1x0l4|4d4s4_0E4?4}2y0U0P1g4w3j5b24585a565c5e043S4F2/4@4e4_0C4q3*1g0%5l4(244:044=5r3Q5t571g4{5H5J2y4 5153555C1b5k5H4-5i1b5d1g4E5h5m5j1g595X5O245#043$5N5Z015W3h5Y5)5!5o3-5?5|5^5+5B4r5n1g3`605U62045w5H4z653C1g0P0v0:644/4;6m3;5:5%3x0q5{6a0G0r1g030q0$00381*0G210m0L0q0~0:0y0P0l0:0q0?0$0?2O0y0*6K214+6e5.3Y1g0:0v1k1+2s0*6p4e5E5G5`6$015:436#5@0_1g0#1;206/4B6i6k722y5E020$0*0o765/5o4o0j7h5T6g5V1g0c3.6u6u6@0y4*7j6n040=7u3;7s040)0e0e2C0m7y5u1g0h7H73046)6+0M6-7L2y4_0z7o7p7r746l5-5@5E0R6=6t6@5:5g4y7p6v7k3M1g3e0t0G0B110y7d1b6;7}7=046!5(6a4_5M847;7A6j7!883L5v807%807A5A697;867S6h048b8o7l6c7W7q6|6i0+8i0`1g2M8s6b7K8l5y1r8E7U8g1g797b807,7h7i8H4^7m8v7/7:3L6}040+3?8i1g1N7#610t0#6i7|8,6a0y8B7N2s0;548U7I048G8d7z6(6*0L6,6W8M040R8Q7f8K638=897?2U7_7{9d040z7n6e8Y9q8Z928J8}4s5E7x9v4)7B7D7F9l904Y5@7A8+918~7V9p7X9H937P7R9f7v7)3I9s4l9h7^7`383{0|4#4W4H9*0|4K1O0*4M9/2^2;2f2h2?0)1 9,4K1U4%7;2)0U0v0+0)0_0l0v0B0n4*1H1o1K1M0q9o3j1#3y1V0w6J0m0?0`1v5,1(4S344e261@1_1{a03L2L2C2E1g2R0%0G0:1e6X0^0J2m1x4Z4Va03i4Y9)aC9t837*7$6o9T8V4`8E5Q04522 9l5,6?5@7,9l6d3h6f8I8ka=8-a%a~855La+50a-5S9z5*04a;a#616ra^9%aX9+2:9~050L0$3y1^040.2#0?6I2Z4-aX0/0I0Q0C0q0Y3R1OaX9ybp1ibp0dag6+0*bM1x6X1j2@1x0;044P1C6T6V100P2)9JbT0ybV0E6K1x0G6B002C1d6Pbw4Q5;bFb_0q1M6X0m2s144!b_6!aX0q0t6Jc34$8kbGblbnbJ0P040(0$0q2 0q7E1vcn180q0x2@6Hc1b^4$c5b|1E20cn9i9#1y0W6P0)cx4W0n0q0R0q0@cQb{4$0q0h2r140rb,6N0q0Q0zb,0mb.0q0)6J0U0t38140DbHchcg040wc:0PcK9uc6cHcnc80:bNc+0M2*c}5=c60 c}5 c60=df1ObI1Obm3y0|di0|dk1)1+3Lay281`2G61aE2N2PaIaKaM2SaP0BaR5NaT3|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_bi4J4T1idp05bpbr6Kbt95bRbx0I0nbBbD6`da6Xafc}68da0Wb cwca4Wccb_c?boch0S210$0Nb,1xcn0lcp382Z6O6Q170q2f0L16212CdEaQ0ye%eveC33ds1_duaB6@dyaG2Q0qaJaL0eaNdFdH3jdJaj3jdN617Aa!d(a$5F808nd+e4a/d+effvbdd*erfEd.ead:bf5Xen246x6z0q0X0q0N0qd66N8cd_dOa}egd}b0f(8eb3fAb5dZa:9b5$f;d 4seif@d|3L5:eqe2b2baf=0468fId@bgex1#4I9-eAav3L0)0mc.6N2!0q388%1g1Ugfgh1xe@1x0,1d0*2c040H0s0A1Xal1WcJ0B2)0+1:2a0e0W0c0|0|0+0:0=0#0P0_1e0l1*0)0=3?0;0|gUgW0|0Sc80;1.0v0O0t0+eWggbO0:1gg,0Lg.crg;g?100mg_1O0)3Qb~b:c,bO0L6Q6I6B1+2)4-gGgIgK0*gMgOgQgSg)gXgZg#0:g%hr0|0H0g0K0n0g0A0D0~0$0E0v0s0W7_6PhI0A0)7_0v0c0vbL0W0v0AaL0yhW0m0g0Q0X0L2 0v0H950:170y0~0vhAhC0{0-g_2 0$gy0H0ZhGb,hKhM0:b,hP7_ah0qhV0qhYc:6K00h*21h-b$h:2$0!h{0lh}8|h60q1Kc|cJ0t0`bO0y6JcC3e0P0T2Sbm2Z0k6P9yau1VeF0J0qbT0Ld6b}1y2r0:1d0GiHb@6GiX7{bMeIag0?0*1x2D6W1MiLgE05cJ3;g.aA2f0T2wc010gv0J7E1b0P1n8{i~0)j0gUh30B1bha4:6Kj90)0,0B0laAje1vjggH0lgJ010H4Q0$0v1Mi40v0`hQ0B0v9{5d0;0:1B0=0eb*j8j00~hL0,2W2Y2!1b2f2a0t0U1|j50;c+7a1b0^1o0q0f0)iFhYc,1y0b0q1`hmgNgP0#j}0=0+1^0G0_gSbX1#dGi-0W0|1n0T0`jJh*0|0n0r0-0D0D0-0-h(0ib,0K0Kic0V0,0%0wc#0=0jb,j_hngPbXgi0WgTgVj5gY0Pg!g$g(0|6E0l0TjL0B0e0@iZaL0m0Y0X0u0n0i0-0X0D6y0q0W0:0G1bjvhGjyhLjl6)jChRjG1=jJ0UjLjN2:h6gD1i1 7^0_1K0tbOgE0w0U0`k 1B2O0q0H0q0sicb,e?1d3Oag2$h i1lnk_b@dbi72n3e0?cH6Wk.hc6Bi^c8d6iXhc6HiBhgcvh!b:btgt2#21ki0X0-0=2Sj,j.j:kef3l61Ol8k2lbldevbk9-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