Aller au contenu

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.

###
# testsbksl-nlbksl-nlassert R[3] == 7bksl-nlassert S[3] == 5bksl-nlassert (len(R) >= 10000) and (len(S) >= 10000)bksl-nlbksl-nl# autres testsbksl-nlbksl-nldebutpy-undR = [bksl-nl None,bksl-nl 1,bksl-nl 3,bksl-nl 7,bksl-nl 12,bksl-nl 18,bksl-nl 26,bksl-nl 35,bksl-nl 45,bksl-nl 56,bksl-nl 69,bksl-nl 83,bksl-nl 98,bksl-nl 114,bksl-nl 131,bksl-nl 150,bksl-nl 170,bksl-nl 191,bksl-nl 213,bksl-nl 236,bksl-nl]bksl-nldebutpy-undS = [None, 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24]bksl-nlfinpy-undR = [bksl-nl 50672311,bksl-nl 50682424,bksl-nl 50692538,bksl-nl 50702653,bksl-nl 50712769,bksl-nl 50722886,bksl-nl 50733004,bksl-nl 50743123,bksl-nl 50753243,bksl-nl 50763364,bksl-nl 50773486,bksl-nl 50783609,bksl-nl 50793733,bksl-nl 50803858,bksl-nl 50813984,bksl-nl 50824111,bksl-nl 50834239,bksl-nl 50844368,bksl-nl 50854498,bksl-nl 50864629,bksl-nl]bksl-nlfinpy-undS = [bksl-nl 10113,bksl-nl 10114,bksl-nl 10115,bksl-nl 10116,bksl-nl 10117,bksl-nl 10118,bksl-nl 10119,bksl-nl 10120,bksl-nl 10121,bksl-nl 10122,bksl-nl 10123,bksl-nl 10124,bksl-nl 10125,bksl-nl 10126,bksl-nl 10127,bksl-nl 10128,bksl-nl 10129,bksl-nl 10130,bksl-nl 10131,bksl-nl 10132,bksl-nl]bksl-nlbksl-nlattendu = debutpy-undRbksl-nlassert R[:20] == attendubksl-nlattendu = debutpy-undSbksl-nlassert S[:20] == attendubksl-nlbksl-nlattendu = finpy-undRbksl-nlassert R[10000 - 20 : 10000] == attendubksl-nlattendu = finpy-undSbksl-nlassert S[10000 - 20 : 10000] == attendubksl-nlbksl-nl ∞/∞

R = [None, 1]bksl-nlS = [None, 2]bksl-nl...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert R[3] == 7bksl-nlassert S[3] == 5bksl-nlassert (len(R) >= 10000) and (len(S) >= 10000)bksl-nlbksl-nlR = [None, 1, 3]bksl-nlS = [None, 2, 4, 5, 6]bksl-nlipy-undr = 2 # l'indice du dernier élément de Rbksl-nlrpy-undsuivant = 7bksl-nlwhile ipy-undr < 10000:bksl-nl R.append(rpy-undsuivant)bksl-nl ipy-undr += 1bksl-nl prochain = R[ipy-undr] + S[ipy-undr]bksl-nl if len(S) < 10000:bksl-nl for s in range(rpy-undsuivant + 1, prochain):bksl-nl S.append(s)bksl-nl rpy-undsuivant = prochainbksl-nlbksl-nl

A

Au début,

🐍 Script Python
R = [None, 1]
S = [None, 2]
  • On déduit R[2] = 3.
  • Les suites sont complémentaires, donc l'entier 4 est dans R ou S.
    • Il ne peut pas être dans R ; le prochain sera 3 + ??? (pas 1, ni 2), donc au moins 6.
    • Ainsi S se poursuit avec 4 et 5 ...
🐍 Script Python
R = [None, 1, 3]
S = [None, 2, 4, 5]
  • On déduit R[3] = 7 et que 6 est dans S.
  • De là, on peut initier la boucle en Python.
🐍 Script Python
R = [None, 1, 3]  # 7 à venir
S = [None, 2, 4, 5, 6]

GEB

Douglas Hofstadter est l'auteur du livre Gödel, Escher, Bach : Les Brins d'une Guirlande Éternelle qui a obtenu le prix Pulitzer.

On y trouve en particulier certaines suites étonnantes.

Par Max Braun — https://www.flickr.com/photos/maxbraun/3196699274, CC BY-SA 2.0, https://commons.wikimedia.org/w/index.php?curid=75349761

Ambigramme G E B, initiales de Gödel, Escher et Bach présent sur la couverture du livre dans l'édition de 1979. Par Max Braun.

Z

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