Aller au contenu

Suites Female Male de Hofstadter

Le cadre

Les suites \(F\) et \(M\) de Hofstadter sont définies par récurrence (directe et mutuelle) de la manière suivante :

  • \(F(0) = 1\) et \(M(0) = 0\),
  • \(F(n) = n - M(F(n - 1))\), pour \(n > 0\).
  • \(M(n) = n - F(M(n - 1))\), pour \(n > 0\).

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

Exercice

Coder deux fonctions terme_F et terme_M qui prennent en paramètre un entier positif n et qui renvoient le terme d'indice nde la suite de Hofstadter \(F\) (ou \(M\) selon le nom).

On pourra travailler avec deux listes F_mem et M_mem définies en dehors des fonctions. (Oui, c'est une mauvaise pratique ; c'est volontaire ici.)

\(F = (1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, \cdots)\) ; suite OEIS A005378 :

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

Contraintes
  • \(0 < n < 10^5\)
  • ⚠ Nombreux appels aux fonctions terme_F et 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)dVM63Hm(P+02è-U],59fq!78 _o=Gpcwgv4F1kRIéhtsSLC[i:050r0m0+0l0;0k0,0P0V0k0l0,0,0S010+0;0U010406050,0p0x0x0l0e0j040-0R0k0p160R0g0P020l0x0U0f0P0%0m1g0e0L0p0m0,050c1d1f1h1j1b0U04051O1H1R0c1O1b0r0;0Y0~1012140*0;0X0*0k1)0*0+19050_0h0k0m1!1113011(1*1,1*0+1=1@1:0+0e1P0+0*1_1$010K0{0m0g1u0m010~1m0,0U0l0g140C1:2m2o2a1{2d1@2g0x2i040a0P0z0e0R0U0R0,0;1p1r0@2k0e0e0m0V2M1H2t0g1P0c282Y2527261;0r2v141,0g2f2J1:1X1Z0 1`2,0;2.0g0R2=1:0U2R1P2W2Y331c2n1r2@2b2|0e1g0k190P0#2V371a362u391{3b3d3f0C3i2o3k2W2+013p0l3e040P0v3t2X1b3w3n143z3B0P0Z3F3v373x3L3f0I3P3H3R3J3y0R3c3A3f0u3W3l381#3o3#3q3C0N3*3I3-3K3/3%3C0O3?3Y3^3!3$3M0J3~3m403T040#0B453,2^413:0#3h1I3j3X464e480#3s4j3u4l4d3a3`3B0#3E4r3G3+3S4w190#3O4A3Q4m4v424F3V4I4t4D4M493)4P4C3Z4o3=4V3@4n4E493}4!3 4$4S0#444*4K3.4S0C4b4:4u4=3:0C4i334Q4X4%0C4q4 4W47524z554#4L4|4H5a4+5c3{0C4O5f4;3_4?4U5l4`5n4|4Z5q4R4|4)5v514?4/5z574S0v4^5D4,3:0v4~4k565J3{0v543j1S311H2=2#0r272*3Z0V2}2B0?1Y1P300m325T4I055%0@5/5m3y190!0Q2A0x3P0P5O2b0R190S60621{18040:3P68140x0;4F6d5b69190G3W50400$190@0K6j5g1{0W3f6v5_0g0K190+0m3c0m0Q0!6A5r016a0y6L3S190g6Q3Z6a0q0=4c3x6y3C0P6%6U400,0r19016.6Z3Z6+3f6%0P0/0R1v0k0D6F0H0P2K0P0h1F0R2`6 1@0}1,0,6F0}5|5~0P0^0P0t5}1A6:6*6,6$6%0i1r0X1h2o160+0P1D1^7e1A7g7x7j7f0,6G1q7x2O0x0n2A0P0k1q0X1E0p0e0P0M7m4e6=7p1y2f0Y751^1@0P6F6H0P7B0x0:0g6n4_3x7!6@0P6.013W7{6e016r041`6G0+676k3K0h192y6)4e6O8e3a5{7k5 5;896N190q886w1464040S664I618n0g8b048d8m8s8o046P8F6B197F7l8K6M6W0H8r5_0,2r04010(1v2J2K1?1^0M7~4P808n830K3#8T6M0g190$8;3x0R6#2`8_4X8C0e2o0X0m8h6l8I958a8c2f988H8J358A8j5~9c8R8~476S9l4e8u0A9o2b6g6i8P3x6W6Y8+7{6@818?047j8^8y818u8x338z8G9E9H9M9J190E9s3o9h8O9f8G6a6c9w4X8M8k9j199$9Z8L049Q3j9N5_8u9U9I8n9u499+040G7@4 9B9C9g9F9*9%408u0d9c9E0l0U0U2f0r9~9e5Ta59G9~8q9Aa39D8j9;3u9?6M9K9V3K8@az019^aC9E8N8l9.8Q9,ac9XaIal9!aLa84naB9`8GaEaV5_9|5M3u816aa07 a3aw6R047:9caaaM84afahaja=5|au2Xa%8pa*6(8-192R0+7U6TaY8=aN9~9-aP9/b7aJ9x6m6o6paTa69ib88`65aC9#9c9|5HbdaK9 6o81836t9c6#61aS3a6D047-2A0Q0ta_bG9W04bfbwbh046X7Y2bbE9CbP147!7}bX1{7`6@6_6{6}0m6 71730,750g771F7P0;7bb{7:7D7ia75I2bb+7q7s7u0g7w7y1E7/8kc1aH707Ica0P7L7N7*7R7T7V7X7^6;7o7{1z0g7(0;7*1^bK1^aH7=a15N8nc67|6/aqa,3Z83850e87bo8 9abSa$8n8gb#5`a.c3bT6Va cUa9659L9=9D8C8Ebgc*97c#aGc(cYaQbV8Sc,7Z8W8Y8!120;8%7W8*a2a48G8.8:d18i9:aC8{198}dg3o909294c#c!c@47c=9bds19akc}9/aHaod09Ra5cX2XcOc-049rdn6f6h9}dybV9zdbaram0Qa|3C9S8vaFaUdGaW9Td%c%bndu8faRd/dhdDdSbcdBb9didOaDd+d}a!9~a)cN8,9O9)d.c)dLabc`19aeag0gaidSdAa}dXdZa~bVb09Basc%dZdK9pbqd}9Pdjd d)dCc|ekc~d_eE9/a/d^a=etd#9_eB6Me1dSe3dVeqa5eJd=1{a;eca?efeheY14dte9bla{aoepbAb30^b6d,d@e)8HeG5^d{dIe}bUcH4s1H5?5.5Uf60c5X1H0+5Zfb2(2Z0l8%2Y5X1Nf03Z2R0x0Q0K0l0$6I0*0v191z1B7z0}dU5:1V5*2?400l0r0x1q2L0;1qcldq0e191N3xfIfK0gfM1q0E7w23040s6G2KfO0,2o0}0m0K0K0^0}2O0h3#ehfE1O7r0~0e0)1^0;0V0;0P0p2.2vb:0P1gb}clb{0x0)285(0}2I7U0~0*0l7z700p2L0mebf{040(0k0P0j0P0lgd0p0bgagg0*giccg42ncS0l93ck78gDgF7M2A0}2R120R7U0V1F0d060z117Pb{0l1ogXgu3k1O0F1r1o0{b}0l6Fgl0m0b0+0)0ecAglg7ag1o0P2n0}0VcR7PgC7Q0X0;7zg:fl0.b{f/f;0+f?1^f^0e0r0}b@ck5%0g0,0Vh2hpfPhzhdg80d6^001F7x0l0Vg#0U22gt1S3k2=3x1}1+1-1/fm402x2f2h192D0-hB177x0z0jghe 1Q5V355;f5h#4e833nbD6zc`0V190w0R0K7bfI7-9~fC4se55_bBf/i0d!c#0K0x190Q0Q2`2LiobOe`0h6a7H0k6udSbWe4dc5_0V0#1903gqaf3#hD7L0)fK0of,2M0P0y7a6F0PgZclg22M2g0;2RapeUie6Miv19ixize`e!e`9E0TeDd!8nayd}bsc#bue26oa+eu2bi-04i/a:19ebi?i4i_j4eZewePbUe|81j0eSj2a+81j6j8c#i=e,dheXc:i{jhjyeFbtdQa#eHbxf23Gj3jqiw0miyj904jbjvbQe_jB9@jAavenjk9{dQbvd`f1job1dd6sihc#bEacbI0TitjS14jrjNi:j^8HdFjVe~aoicjJjpb2048/0ed,eMi{8|e jf9904910g93j@j(cV8Ddxe`e+km40j`jOjtjaa=i^e8ksd:c d,ked#dNji3ZeRkq8pk31aj3i+a-i^kbd*d$exd(k0bp04eOkY3Zkuj|kB63kxe#kz9Yj}i~iujMkvi;k,jc04k.aOk*96j!e6d|kIdLk#jYj#9vkL9 jIkOkPj+5_k(jPjRk~aAk{i_d#lijGa-eea^eikydYe/iCle6M83b4e@d}lgkwjQlukAlpc^l0bej14P06kQcPj-k)lJ40j:c`bI0wkllU4elEl9j l6l1h?cZkMeplQ6q19k8kadjkdaFdpkjdrl9ejh|3adwl,c~l jLi.j{lha=0wlml-kDkWbRezdMaCkKk:l.lxeVl1mbkTjWkVl3blmraxeAk$ktk?lTm0jglGe#mblImDe*d;j}l%j}juljc$mHk/mQk;mMmBm9mGmcjCe#mwkZl5dJjljEe2eT4kldly3xmNmQmPl#dhmSk}m_mElomJc$lregl!n09Emqlwi*iDlze=b50ekF8nm?m}8tk_j}n6m!5_mVmQ9Em3nobilOl:h}lSiibFi?bI6Kltc#nhn06al)m*dHk2l/na3xdek9mfm%3Zdk04dmmum1b3dqn4c;cWn$ngmXlFm erjxmU8pnJi`l+mhkHmz4emkn:dTnNdWl1and}i|nYbQnTl4aCnGlna`nnbxlLi,n+k^mFk`jUn}ofa-o7evk!mjm,eSlblPm:m6j7m8n,a=olnid~ojnleda@n3nEoklviAn moeIoNo5njmtn`dhopk+orlDohmOnknqe7mToEnpoEoajzoGo)d-o+nHmLo=oYmEm)n?aZotl9m.idoxn*m7k@o%o;oE9En/oEm^n5oIe%n)l1e.oOmne;khe?neo9o$m@o(pabaeKe#nsjHj*kf82nyj/i1nB8Mpilfpso,19n=pCnrnMpmk6l?nSl^dlnf9Ol{kkoLnlm2pJogp6mCobe#oDo^meoTc$pYmsn_l*o l8mln~mnnwd?oSoWmEc/p`d{o{oUo}pCo/kUn-eWodjj9cqcmsqeo1qglKeLmhqam+p|n}p2k4ldoyjsoiqleCmIp-k`n2e(p}m5eln8m/p4pjq2q6kZq5nKl1q8oFqrp5ozp7ptp9pfbmo@jZqipLn0pen.qn40o-q%qVaXp=n|pMlaoPq01{qjmxq$q/qDo:qBd{qGp)a-pkl9i)qMo0ifnclCp=r0kZr6a-p/q*pylN4 06rtergIi70_0riao3jXqT9/i5rxi96Gajrd4sru8niFiH0P0F167ag{fNe bk2bcQ1286d,rwi8rzrIoBk-r9kJjEj%q{rKrDr18wos195pcIj,84r!cSr$i6r(rAqAmar-40a!r:p:r=o~r@qSsd3x9|5ur|rgr~7Hs0mfr%rys4p8rm9(a.s7n{r/qLqQnUc.r_04r{f3k6cRcTp=9EsqrHnRs5p.sx9tszplp=9KsfpC9|sG3GrX1{rZsnsKq3mK6ba=sNr)sPstkysSbQpzbUscpCnQkEpWnWp@8=p!l}qIjD194}aolbpCsXbro_qwsZj$9~pOqsdRl(sEjFp:tkl7045Sn}tr8G9|59p}twp{04tztvsE5etAtGtjsE5ktIe0dQs#tqsEtQentBeQdQsjtFtO195ytNq_dQt$tZt(195Ct%s,019|t.t+t:s9tKt!49tptUtot}mdtVshjEtuq{u2r.4Fu5tRctq;nuc4s(edr s+sBuds.e#s:ssq#su9m04lZp$o=s`c^s|pnpUsL9no3l_ext4s^dPt8u0c~0qtbd#r^i}tflcm;u804sat~t{uLnt04u7s8p0t/uksyt8t`t,tDu.t^dQtHt@u+sT19u@u6tLu;u_1{9|tMu^r?u3r`u v5uVtYu}t{vbubu/t*vcu/t?viu=4FuXu1tovoc~u%u,t|v8sguV4pvwth4FtEvlv0uJ49vDvfvm49u|vJsHc~ovpnsJteumk`uor*sQk`nDl~a=uxuluzpTdfuCmguEpXl`n!l|uIt;dQt9iAuOo:uQp=q=owuUu(qtvEv9w2tmu*w5vuuauYu/wbvpt{vIwcvKwhwfu/vMwivFv@19v3w4vxw6wsvNw9u`sFvAtltTwlvKvewowyv1t)wBtsvhwxwuvuvkwOvB04wRwHwPwz4awLtxjEu!bxvtwYw%bUw)wJu9w!tC4yvws%s-vQsIuivTonsvvWs=uqoCv?pQsVt:s~mft28`uFsLuHuvoE9|v_rcv{kUv}t:v q~vGvru#w-xpw:tWw3wStlwevssExzxrsEwkxAt{wnwEwp9|xIxGu/wwwWwTwDxNvKxSxDvdxuv604wGxJwIvGwNxQtlwVx$wXw.wUxYvyxqw(t x;w64hx_vuvzdSxswq49xCx@uckCvQ0ch{f7fj5+1bf9yc5W0^0`0|04.