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 = [None, 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236]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 = [50672311, 50682424, 50692538, 50702653, 50712769, 50722886, 50733004, 50743123, 50753243, 50763364, 50773486, 50783609, 50793733, 50803858, 50813984, 50824111, 50834239, 50844368, 50854498, 50864629]bksl-nlfinpy-undS = [10113, 10114, 10115, 10116, 10117, 10118, 10119, 10120, 10121, 10122, 10123, 10124, 10125, 10126, 10127, 10128, 10129, 10130, 10131, 10132]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-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-nlbksl-nl# testsbksl-nlbksl-nlassert R[3] == 7bksl-nlassert S[3] == 5bksl-nlassert (len(R) >= 10000) and (len(S) >= 10000)bksl-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