Les Brins d'une Guirlande Éternelle⚓︎

Quelques suites numériques utilisant l'auto-référence.

💥💥💥 Le coin NSI + maths expertes 💥💥💥

Douglas Hofstadter ¹ est l'auteur du livre Gödel, Escher, Bach : Les Brins d'une Guirlande Éternelle ²

On y trouve en particulier certaines suites étonnantes.

1- Hofstadter Q-sequence⚓︎

Cette suite ressemble à celle de Fibonacci ou de Lucas, chaque terme est la somme de deux termes presque précédents.

La suite $a$ est définie par :

$a_1 = a_2 = 1$,
$a_n = a_{n-a_{n-1}} + a_{n-a_{n-2}}$, pour $n \geqslant 3$.

Personne n'a prouvé que cette suite est bien définie pour tout $n\in\mathbb N^*$.

On ne connait pas son taux de croissance.

Question

Donnez un code qui calcule les termes successifs en vérifiant que chacun est bien défini.

$a = (1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, \cdots)$ ; suite OEIS A005185 :

###

def A005185(n):bksl-nl ... # ← À compléter icibksl-nlbksl-nlbksl-nl# Testsbksl-nlfor n, a in enumerate([None, 1, 1, 2, 3, 3, 4,bksl-nl 5, 5, 6, 6, 6, 8, 8, 8, 10, 9]):bksl-nl if n > 0:bksl-nl assert A005185(n) == abksl-nlbksl-nl

Réponse

🐍 Script Python

def A005185(n):
    if 1 <= n <= 2:
        return 1
    else:
        i = n - A005185(n - 1)
        j = n - A005185(n - 2)
        assert (i > 0) and (j > 0), "Erreur de définition"
        return A005185(i) + A005185(j)

2- Hofstadter Figure-Figure sequences⚓︎

Les suites Hofstadter Figure-Figure $R$ et $S$ sont des suites d'entiers 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)$ ; suite OEIS A005228 :
$S = (2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, \cdots)$ ; suite OEIS A030124 :

Question

Donnez un code en Python pour les fonctions R et S.

Suite de Hofstadter Figure-Figure

3- Hofstadter-Conway $10,000 dollars sequence⚓︎

La suite $a$ est définie par :

$a_{1} = a_{2} = 1$,
$a_{n} = a_{a_{n-1}} + a_{n-a_{n-1}}$, pour $n \geqslant 3$.

$a = (1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, \cdots)$ ; suite OEIS A004001 :

Questions

(Facile) Calculer les premiers termes.
(Variable) Calcul dynamique de $S(n) = \sum\limits_{i=1}^n a_i$. 💥💥 Suite de Hofstadter-Conway à 10000$
(Vraiment très difficile) Vérifier si votre code est efficace. 💥💥💥💥💥

Réponse 1

Le code est très accessible, on peut même démontrer que la fonction est bien définie, avec A004001(n) <= n pour n > 0.

🐍 Script Python

def A004001(n):
    if 1 <= n <= 2:
        return 1
    else:
        i = A004001(n - 1)
        j = n - A004001(n - 1)
        assert j > 0, "Erreur de définition"
        return A004001(i) + A004001(j)

Réponse 2

On pourra faire le lien avec la courbe du blanc-manger

Réponse 3

Bon courage ; cet exercice est réservé aux experts.