Aller au contenu

Liens avec le nombre d'or

Trop long ; pas lu

On fait des expériences mathématiques pour montrer le lien entre le nombre d'or et les représentations de Zeckendorf, en particulier pour les opérations de décalage : incrémentation et décrémentation.

Du code Python illustre les découvertes.

Introduction

Des phrases piégeuses

  • \(\sqrt{a+b} \neq \sqrt a + \sqrt b\), en général, sauf si \(a\) ou \(b\) est nul.
  • \(\frac a b + \frac c d \neq \frac{a+b}{c+d}\)

Trouver l'intruse

Pour simplifier, on considère deux nombres strictement positifs (ou des fonctions très simples).

  • La somme des dixièmes est égale au dixième de la somme.
  • Le produit des puissances est égal à la puissance du produit.
  • La racine d'un quotient est égale au quotient des racines.
  • La somme des dérivées est égale à la dérivée de la somme.
  • La somme des arrondis est égale à l'arrondi de la somme.
Réponse
  • Que pensez-vous de l'arrondi de \(1.618\) ? \(2\)
  • Que pensez-vous de l'arrondi de \(2×1.618=3.236\) ? \(3\)
  • Que pensez-vous de 2 fois l'arrondi de \(1.618=3.236\) ? \(4\)

De manière générale, l'arrondi d'une somme n'est pas égal à la somme des arrondis.

Une suite géométrique

Il n'y a pas que la suite de Fibonacci (\(F_0=0\) et \(F_1=1\)) qui respecte la règle \(u_n = u_{n-1} + u_{n-2}\) pour \(n>1\). Il y a aussi :

  • La suites de Lucas (\(L_0=2\) et \(L_1=1\)).

On peut se poser la question : existe-t-il une suite géométrique \((u)\) qui vérifie également la règle \(u_n = u_{n-1} + u_{n-2}\) pour \(n>1\) ?

Réponse

Déjà, la suite constante nulle vérifie la propriété.

On suppose qu'une autre telle suite géométrique existe, alors \(u_n = u_0×q^n\) (avec \(u_0\neq 0\)), on a :

  • \(u_0 = u_0\)
  • \(u_1 = u_0×q\)
  • \(u_2 = u0×q^2\), mais d'après la règle on déduit
\[u_0×q^2 = u_0×q + u_0\]

Que l'on simplifie par \(u_0\) que l'on a supposé non nul. On déduit que \(q\) est solution de l'équation \(x^2 = x + 1\). Il y a deux solutions. On note \(\varphi\) la solution positive. On a :

\[\begin{align*} \varphi^2 &= \varphi + 1 \\ &\text{ Divisons par } \varphi^2\\ 1 &= \frac1\varphi + \left(\frac 1{\varphi}\right)^2 \\ &\text{ Réarrangeons}\\ \left(\frac {-1}{\varphi}\right)^2 &= \frac{-1}\varphi + 1\\ \end{align*}\]

On déduit que \(\dfrac {-1}{\varphi}\) est l'autre solution de l'équation \(x^2+x+1\).

On peut également vérifier que

\[\begin{align*} \varphi &= \frac{1+\sqrt5}2 \quad \text{ Le nombre d'or}\\ \frac {-1}{\varphi}&= \frac{1-\sqrt5}2\quad \text{ l'autre solution}\\ &\frac1{\varphi}=\varphi -1 \end{align*}\]

Des expériences

Un tour de magie ?

Expérience 1

🐍 Script Python
from math import sqrt

phi = (1 + sqrt(5)) / 2

u = 1
for _ in range(13):
    print(u, end=", ")
    u = round(u * phi)
Sortie : les nombres de Fibonacci
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,

On est tenté de penser que l'arrondi de \(\varphi^n\) est un nombre de Fibonacci...

Expérience 2

🐍 Script Python
from math import sqrt

phi = (1 + sqrt(5)) / 2
a, b = 2,  1  # Les nombres de Lucas
for n in range(80):
    x = phi ** n
    if round(x) != a:
        print(n, end=", ")
    a, b = b, a + b
Liste des erreurs
0, 1, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79,

Alors non, c'était les nombres de Lucas, et avec deux erreurs pour les petits indices (0 et 1). Ensuite, à partir de 69, les erreurs de précisions des flottants sont trop importantes.

\[L_n \approx \varphi^n \quad \text{pour } n > 1\]

Expérience 3

🐍 Script Python
from math import sqrt

phi = (1 + sqrt(5)) / 2
for n in range(68):
    for m in range(n + 1):
        x = phi ** n
        y = phi ** m
        # Test avec les nombres de Lucas
        if round(x) + round(y) != round(x + y):
            print((n, m), end=", ")
Liste des erreurs
(1, 1), (2, 1), (2, 2), (4, 1), (4, 2),

Ici, on constate que, sauf pour les petits indices, l'arrondi d'une somme est égal à la somme de l'arrondi. À partir de 68, on a le problème des flottants...

Et les nombres de Fibonacci ?

Expérience 4

🐍 Script Python
from math import sqrt

phi = (1 + sqrt(5)) / 2
a, b = 0,  1  # Les nombres de Fibonacci
for n in range(80):
    x = phi ** n / sqrt(5)
    if round(x) != a:
        print(n, end=", ")
    a, b = b, a + b
Liste des erreurs
71, 72, 73, 74, 75, 76, 77, 78, 79,

👍 On constate que

\[F_n \approx \frac{\varphi^n}{\sqrt5} \quad \text{Arrondi correct pour } n \in \mathbb N\]

Explication

En réalité, si on note \(\varphi'=\dfrac{-1}{\varphi}\)

\[F_n = \frac{\varphi^n - \varphi'^n}{\sqrt5} \quad \text{Les nombres de Fibonacci}\]

Et comme \(\varphi'\) est entre \(-1\) et \(0\), ses puissances deviennent négligeables. De sorte qu'on peut prendre l'arrondi du premier morceau.

De même

\[L_n = \varphi^n + \varphi'^n \quad \text{Les nombres de Lucas}\]

👍 Mais la chose remarquable... d'après l'expérience 1 :

  • l'arrondi de \(F_n × \varphi\), c'est \(F_{n+1}\), pour \(n>0\)
  • l'arrondi de \(\dfrac{F_{n+1}}{\varphi}\), c'est \(F_{n}\), pour \(n\geqslant 0\)
🐍 Script Python
from math import sqrt

phi = (1 + sqrt(5)) / 2
u = 1
for n in range(13):
    print(u, end=", ")
    v = round(u * phi)
    assert u == round(v / phi)
    u = v

L'autre chose qu'on remarque, en adaptant l'expérience 3 avec les nombres de Fibonacci :

🐍 Script Python
from math import sqrt

phi = (1 + sqrt(5)) / 2
for n in range(68):
    for m in range(n + 1):
        x = phi ** n / sqrt(5)
        y = phi ** m / sqrt(5)
        # Test avec les nombres de Fibonacci
        if round(x) + round(y) != round(x + y):
            print((n, m), end=", ")
Liste des erreurs
(0, 0), (1, 1), (2, 0), (4, 0), (66, 0), (67, 0),

Si on oublie

  • les erreurs avec les flottants à partir de 66
  • l'indice 0 (on le savait déjà \(0\neq 1\))
  • le doublon à l'indice 1 ⚠ (\(2\varphi \approx 3 \neq 2\))

Alors pour deux nombres non nuls de Fibonacci distincts et leur valeur approchée \(\dfrac{\varphi^n}{\sqrt 5}\), on a la chose surprenante : l'arrondi de la somme est égal à la somme de l'arrondi !

Lien avec Zeckendorf

Le lien avec les représentations de Zeckendorf ?

On a constaté que

  • l'arrondi de \(F_n × \varphi\), c'est \(F_{n+1}\)
  • l'arrondi de \(\dfrac{F_{n+1}}{\varphi}\), c'est \(F_{n}\)
  • Avec des nombres de Fibonacci distincts non nuls, on pouvait intervertir arrondi et somme.

Il est naturel de considérer une représentation de Zeckendorf : \(F_{i_1} + F_{i_2} + \cdots + F_{i_k}\) et de s'interroger sur :

  • \(F_{i_1+1} + F_{i_2+1} + \cdots + F_{i_k+1}\) (incrémentation des indices)
  • \(F_{i_1-1} + F_{i_2-1} + \cdots + F_{i_k-1}\) (décrémentation des indices)

On ajoutera la question : que faire pour le bit initial ?

Réponse naturelle :

  • \(F_0=0\) devient \(F_1\) par incrémentation, nous l'ajouterons en tant que nouveau \(F_2\) qui était vide avec le décalage !
  • Par décrémentation, que faire d'un \(F_2\) éventuel ? Il devient un \(F_1\) qui vaut un. Ajoutons-le comme un nouveau \(F_2\), quitte à utiliser la fonction zeckendorf_ajout_un s'il était déjà présent pour éviter un doublon !

On constatera ensuite que ce choix naturel était le bon !

Expérience

On peut facilement coder une fonction zeckendorf_inc qui prend en paramètre une représentation de Zeckendorf sous forme d'un tableau de bits et qui renvoie une représentation incrémentée de 1.

🐍 Script Python
def zeckendorf_inc(bits):
    """
    Renvoie l'incrémentation de la représentation donnée par bits

    /!\ avec ajout de 1 au bit 0, car F_0 devient F_1=F_2 qui vaut 1
    """
    ans = [1]
    for b in bits:
        ans.append(b)
    return ans

De même pour zeckendorf_dec et on rapelle qu'on ne perd pas le bit initial en l'ajoutant à nouveau si besoin, car \(F_2\) devient \(F_1\) qui vaut également 1 !

🐍 Script Python
def zeckendorf_dec(bits):
    """
    Renvoie la décrémentation de la représentation donnée par  bits

    /!\ Sans perdre l'information du bit en 0 !
    """
    ans = []
    for i, b in enumerate(bits):
        if i > 0:
            ans.append(b)
    if bits[0] == 1:
        zeckendorf_ajout_un(ans)  # Modification en place
    return ans

Expérience

C'était un peu long à présenter, mais la question intéressante est la suivante :

Si on prend deux représentations de Zeckendorf d'un entier \(n\), et qu'on leur fait subir une incrémentation (ou une décrémentation), obtiendrons-nous deux évaluations différentes ?

🐍 Script Python
import random

inc = dict()
dec = dict()
for _ in range(10000):
    bits = [random.randrange(2) for _ in range(10)]
    n = zeckendorf_eval(bits)

    if n not in inc:
        inc[n] = dict()
        dec[n] = dict()

    bits_inc = zeckendorf_inc(bits)
    p = zeckendorf_eval(bits_inc)
    if p not in inc[n]:
        inc[n][p] = 0  # compteur d'images
    inc[n][p] += 1

    bits_dec = zeckendorf_dec(bits)
    m = zeckendorf_eval(bits_dec)
    if m not in dec[n]:
        dec[n][m] = 0  # compteur d'images
    dec[n][m] += 1

print("Dictionnaire d'incrémentation", inc)
print()
print("Dictionnaire de décrémentation", dec)

# Vérification de l'unicité des images
for n in inc:
    if len(inc[n]) != 1:
        print(f"Erreur {inc[n]=}")
    if len(dec[n]) != 1:
        print(f"Erreur {dec[n]=}")
📤 Sortie
Dictionnaire d'incrémentation {165: {268: 85}, 118: {192: 103}, 128: {208: 80}, 155: {252: 67}, 103: {168: 80}, 170: {276: 68}, 97: {158: 84}, 111: {181: 59}, 126: {205: 86}, 107: {174: 51}, 53: {87: 36}, 115: {187: 96}, 37: {61: 64}, 213: {346: 30}, 39: {64: 50}, 149: {242: 58}, 150: {244: 43}, 81: {132: 61}, 43: {71: 36}, 24: {40: 34}, 82: {134: 66}, 79: {129: 68}, 80: {131: 35}, 36: {59: 27}, 138: {224: 36}, 113: {184: 103}, 29: {48: 47}, 77: {126: 55}, 117: {190: 33}, 196: {318: 46}, 94: {153: 59}, 148: {241: 33}, 84: {137: 68}, 182: {296: 16}, 55: {90: 56}, 169: {275: 23}, 90: {147: 46}, 131: {213: 79}, 28: {46: 18}, 35: {58: 38}, 127: {207: 53}, 156: {254: 19}, 105: {171: 87}, 215: {349: 41}, 86: {140: 36}, 157: {255: 58}, 19: {32: 36}, 161: {262: 39}, 180: {292: 18}, 119: {194: 50}, 89: {145: 49}, 145: {236: 33}, 106: {173: 53}, 163: {265: 53}, 99: {161: 53}, 69: {113: 69}, 65: {106: 59}, 64: {105: 37}, 147: {239: 63}, 112: {182: 70}, 52: {85: 41}, 71: {116: 72}, 110: {179: 76}, 168: {273: 84}, 42: {69: 52}, 231: {375: 13}, 158: {257: 66}, 60: {98: 50}, 142: {231: 54}, 14: {24: 30}, 11: {19: 25}, 95: {155: 64}, 121: {197: 76}, 183: {297: 43}, 203: {330: 17}, 201: {326: 32}, 129: {210: 92}, 48: {79: 45}, 154: {250: 46}, 212: {344: 35}, 98: {160: 56}, 10: {17: 13}, 56: {92: 43}, 13: {22: 30}, 61: {100: 70}, 73: {119: 70}, 87: {142: 41}, 96: {156: 19}, 124: {202: 75}, 120: {195: 68}, 26: {43: 35}, 23: {38: 30}, 67: {110: 22}, 135: {220: 28}, 144: {234: 43}, 108: {176: 73}, 173: {281: 74}, 47: {77: 61}, 136: {221: 73}, 74: {121: 79}, 192: {312: 45}, 38: {63: 31}, 102: {166: 76}, 171: {278: 51}, 221: {359: 17}, 34: {56: 48}, 123: {200: 73}, 223: {362: 31}, 58: {95: 50}, 179: {291: 41}, 76: {124: 66}, 194: {315: 50}, 205: {333: 28}, 202: {328: 55}, 189: {307: 67}, 27: {45: 32}, 217: {352: 36}, 51: {84: 33}, 132: {215: 48}, 146: {237: 38}, 195: {317: 32}, 200: {325: 28}, 160: {260: 88}, 174: {283: 42}, 137: {223: 79}, 62: {101: 35}, 188: {305: 38}, 207: {336: 57}, 92: {150: 73}, 167: {271: 51}, 7: {12: 7}, 204: {331: 31}, 93: {152: 38}, 181: {294: 60}, 75: {122: 22}, 30: {50: 35}, 230: {373: 15}, 21: {35: 35}, 72: {118: 37}, 159: {258: 42}, 166: {270: 43}, 100: {163: 80}, 209: {339: 33}, 197: {320: 46}, 140: {228: 45}, 40: {66: 48}, 141: {229: 51}, 152: {247: 94}, 175: {284: 41}, 139: {226: 77}, 153: {249: 63}, 116: {189: 72}, 41: {67: 21}, 218: {354: 25}, 18: {30: 31}, 49: {80: 35}, 172: {279: 27}, 178: {289: 48}, 104: {169: 56}, 0: {1: 10}, 85: {139: 46}, 198: {321: 14}, 50: {82: 58}, 17: {29: 24}, 63: {103: 91}, 31: {51: 28}, 184: {299: 53}, 133: {216: 60}, 134: {218: 80}, 83: {135: 33}, 59: {97: 27}, 187: {304: 34}, 88: {144: 8}, 32: {53: 52}, 114: {186: 42}, 228: {370: 16}, 186: {302: 53}, 125: {203: 48}, 91: {148: 46}, 206: {334: 20}, 20: {33: 16}, 109: {177: 23}, 227: {368: 11}, 162: {263: 47}, 199: {323: 43}, 193: {313: 25}, 54: {88: 7}, 210: {341: 49}, 101: {165: 26}, 222: {360: 16}, 176: {286: 44}, 151: {245: 26}, 208: {338: 27}, 22: {37: 26}, 45: {74: 59}, 191: {310: 40}, 78: {127: 56}, 164: {266: 22}, 6: {11: 19}, 5: {9: 15}, 224: {364: 13}, 3: {6: 20}, 211: {343: 10}, 70: {114: 36}, 8: {14: 16}, 44: {72: 43}, 66: {108: 61}, 68: {111: 60}, 220: {357: 14}, 46: {76: 20}, 57: {93: 31}, 25: {42: 21}, 229: {372: 14}, 226: {367: 19}, 12: {21: 11}, 16: {27: 22}, 2: {4: 14}, 1: {3: 15}, 130: {211: 25}, 9: {16: 19}, 216: {351: 18}, 190: {309: 25}, 214: {347: 14}, 4: {8: 11}, 33: {55: 9}, 225: {365: 18}, 219: {355: 5}, 143: {232: 6}, 15: {25: 14}, 122: {199: 20}, 185: {300: 15}, 177: {288: 9}}

Dictionnaire de décrémentation {165: {102: 85}, 118: {73: 103}, 128: {79: 80}, 155: {96: 67}, 103: {64: 80}, 170: {105: 68}, 97: {60: 84}, 111: {69: 59}, 126: {78: 86}, 107: {66: 51}, 53: {33: 36}, 115: {71: 96}, 37: {23: 64}, 213: {132: 30}, 39: {24: 50}, 149: {92: 58}, 150: {93: 43}, 81: {50: 61}, 43: {27: 36}, 24: {15: 34}, 82: {51: 66}, 79: {49: 68}, 80: {50: 35}, 36: {22: 27}, 138: {85: 36}, 113: {70: 103}, 29: {18: 47}, 77: {48: 55}, 117: {72: 33}, 196: {121: 46}, 94: {58: 59}, 148: {92: 33}, 84: {52: 68}, 182: {113: 16}, 55: {34: 56}, 169: {105: 23}, 90: {56: 46}, 131: {81: 79}, 28: {17: 18}, 35: {22: 38}, 127: {79: 53}, 156: {97: 19}, 105: {65: 87}, 215: {133: 41}, 86: {53: 36}, 157: {97: 58}, 19: {12: 36}, 161: {100: 39}, 180: {111: 18}, 119: {74: 50}, 89: {55: 49}, 145: {90: 33}, 106: {66: 53}, 163: {101: 53}, 99: {61: 53}, 69: {43: 69}, 65: {40: 59}, 64: {40: 37}, 147: {91: 63}, 112: {69: 70}, 52: {32: 41}, 71: {44: 72}, 110: {68: 76}, 168: {104: 84}, 42: {26: 52}, 231: {143: 13}, 158: {98: 66}, 60: {37: 50}, 142: {88: 54}, 14: {9: 30}, 11: {7: 25}, 95: {59: 64}, 121: {75: 76}, 183: {113: 43}, 203: {126: 17}, 201: {124: 32}, 129: {80: 92}, 48: {30: 45}, 154: {95: 46}, 212: {131: 35}, 98: {61: 56}, 10: {6: 13}, 56: {35: 43}, 13: {8: 30}, 61: {38: 70}, 73: {45: 70}, 87: {54: 41}, 96: {59: 19}, 124: {77: 75}, 120: {74: 68}, 26: {16: 35}, 23: {14: 30}, 67: {42: 22}, 135: {84: 28}, 144: {89: 43}, 108: {67: 73}, 173: {107: 74}, 47: {29: 61}, 136: {84: 73}, 74: {46: 79}, 192: {119: 45}, 38: {24: 31}, 102: {63: 76}, 171: {106: 51}, 221: {137: 17}, 34: {21: 48}, 123: {76: 73}, 223: {138: 31}, 58: {36: 50}, 179: {111: 41}, 76: {47: 66}, 194: {120: 50}, 205: {127: 28}, 202: {125: 55}, 189: {117: 67}, 27: {17: 32}, 217: {134: 36}, 51: {32: 33}, 132: {82: 48}, 146: {90: 38}, 195: {121: 32}, 200: {124: 28}, 160: {99: 88}, 174: {108: 42}, 137: {85: 79}, 62: {38: 35}, 188: {116: 38}, 207: {128: 57}, 92: {57: 73}, 167: {103: 51}, 7: {4: 7}, 204: {126: 31}, 93: {58: 38}, 181: {112: 60}, 75: {46: 22}, 30: {19: 35}, 230: {142: 15}, 21: {13: 35}, 72: {45: 37}, 159: {98: 42}, 166: {103: 43}, 100: {62: 80}, 209: {129: 33}, 197: {122: 46}, 140: {87: 45}, 40: {25: 48}, 141: {87: 51}, 152: {94: 94}, 175: {108: 41}, 139: {86: 77}, 153: {95: 63}, 116: {72: 72}, 41: {25: 21}, 218: {135: 25}, 18: {11: 31}, 49: {30: 35}, 172: {106: 27}, 178: {110: 48}, 104: {64: 56}, 0: {0: 10}, 85: {53: 46}, 198: {122: 14}, 50: {31: 58}, 17: {11: 24}, 63: {39: 91}, 31: {19: 28}, 184: {114: 53}, 133: {82: 60}, 134: {83: 80}, 83: {51: 33}, 59: {37: 27}, 187: {116: 34}, 88: {55: 8}, 32: {20: 52}, 114: {71: 42}, 228: {141: 16}, 186: {115: 53}, 125: {77: 48}, 91: {56: 46}, 206: {127: 20}, 20: {12: 16}, 109: {67: 23}, 227: {140: 11}, 162: {100: 47}, 199: {123: 43}, 193: {119: 25}, 54: {33: 7}, 210: {130: 49}, 101: {63: 26}, 222: {137: 16}, 176: {109: 44}, 151: {93: 26}, 208: {129: 27}, 22: {14: 26}, 45: {28: 59}, 191: {118: 40}, 78: {48: 56}, 164: {101: 22}, 6: {4: 19}, 5: {3: 15}, 224: {139: 13}, 3: {2: 20}, 211: {131: 10}, 70: {43: 36}, 8: {5: 16}, 44: {27: 43}, 66: {41: 61}, 68: {42: 60}, 220: {136: 14}, 46: {29: 20}, 57: {35: 31}, 25: {16: 21}, 229: {142: 14}, 226: {140: 19}, 12: {8: 11}, 16: {10: 22}, 2: {1: 14}, 1: {1: 15}, 130: {80: 25}, 9: {6: 19}, 216: {134: 18}, 190: {118: 25}, 214: {132: 14}, 4: {3: 11}, 33: {21: 9}, 225: {139: 18}, 219: {135: 5}, 143: {88: 6}, 15: {9: 14}, 122: {76: 20}, 185: {114: 15}, 177: {110: 9}}

Comment lire ce résultat ? Sur 10000 expériences avec des tableaux de 10 bits :

  • Dictionnaire d'incrémentation {165: {268: 85}, 118: {192: 103}, 128: {208: 80}, ...
    • L'antécédent \(n=165\) a donné 85 fois l'image \(268\) par incrémentation. Aucune autre image.
    • L'antécédent \(n=118\) a donné 103 fois l'image \(192\) par incrémentation. Aucune autre image.
    • L'antécédent \(n=128\) a donné 80 fois l'image \(208\) par incrémentation. Aucune autre image.
    • ... Dictionnaire de décrémentation {165: {102: 85}, 118: {73: 103}, 128: {79: 80}, ...`
    • L'antécédent \(n=165\) a donné 85 fois l'image \(102\) par décrémentation. Aucune autre image.
    • L'antécédent \(n=118\) a donné 103 fois l'image \(103\) par décrémentation. Aucune autre image.
    • L'antécédent \(n=128\) a donné 80 fois l'image \(79\) par décrémentation. Aucune autre image.
    • ...

On a même testé l'unicité pour tous avec une clause assert. C'est engageant !

⚠ Ceci n'est qu'une expérience, et non une preuve !

Exercice

Exercice

Démontrer que l'incrémentation (ou la décrémentation) d'une valeur \(n\) ne dépend pas de la représentation choisie.

Indice
  • Commencer à montrer que le résultat ne change pas en utilisant une seule transition \(F_n = F_{n-1} + F_{n-2}\).
  • Évoquer que le graphe des représentations est connexe ! (Présenté en page d'accueil !)

Ces fonctions sont-elles connues ?

Créons la suite des valeurs pour nos fonctions :

🐍 Script Python
# Suite du test
n_max = max(inc)
inc_list = [None for _ in range(n_max + 1)]
dec_list = [None for _ in range(n_max + 1)]
for n in inc:
    for y in inc[n]:  # il n'y aura qu'un seul tour de boucle !
        inc_list[n] = y
    for y in dec[n]:  # il n'y aura qu'un seul tour de boucle !
        dec_list[n] = y

print(inc_list)
print(dec_list)
Sortie
[1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, 30, 32, 33, 35, 37, 38, 40, 42, 43, 45, 46, 48, 50, 51, 53, 55, 56, 58, 59, 61, 63, 64, 66, 67, 69, 71, 72, 74, 76, 77, 79, 80, 82, 84, 85, 87, 88, 90, 92, 93, 95, 97, 98, 100, 101, 103, 105, 106, 108, 110, 111, 113, 114, 116, 118, 119, 121, 122, 124, 126, 127, 129, 131, 132, 134, 135, 137, 139, 140, 142, 144, 145, 147, 148, 150, 152, 153, 155, 156, 158, 160, 161, 163, 165, 166, 168, 169, 171, 173, 174, 176, 177, 179, 181, 182, 184, 186, 187, 189, 190, 192, 194, 195, 197, 199, 200, 202, 203, 205, 207, 208, 210, 211, 213, 215, 216, 218, 220, 221, 223, 224, 226, 228, 229, 231, 232, 234, 236, 237, 239, 241, 242, 244, 245, 247, 249, 250, 252, 254, 255, 257, 258, 260, 262, 263, 265, 266, 268, 270, 271, 273, 275, 276, 278, 279, 281, 283, 284, 286, 288, 289, 291, 292, 294, 296, 297, 299, 300, 302, 304, 305, 307, 309, 310, 312, 313, 315, 317, 318, 320, 321, 323, 325, 326, 328, 330, 331, 333, 334, 336, 338, 339, 341, 343, 344, 346, 347, 349, 351, 352, 354, 355, 357, 359, 360, 362, 364, 365, 367, 368, 370, 372, 373, 375]
[0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 33, 34, 35, 35, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47, 48, 48, 49, 50, 50, 51, 51, 52, 53, 53, 54, 55, 55, 56, 56, 57, 58, 58, 59, 59, 60, 61, 61, 62, 63, 63, 64, 64, 65, 66, 66, 67, 67, 68, 69, 69, 70, 71, 71, 72, 72, 73, 74, 74, 75, 76, 76, 77, 77, 78, 79, 79, 80, 80, 81, 82, 82, 83, 84, 84, 85, 85, 86, 87, 87, 88, 88, 89, 90, 90, 91, 92, 92, 93, 93, 94, 95, 95, 96, 97, 97, 98, 98, 99, 100, 100, 101, 101, 102, 103, 103, 104, 105, 105, 106, 106, 107, 108, 108, 109, 110, 110, 111, 111, 112, 113, 113, 114, 114, 115, 116, 116, 117, 118, 118, 119, 119, 120, 121, 121, 122, 122, 123, 124, 124, 125, 126, 126, 127, 127, 128, 129, 129, 130, 131, 131, 132, 132, 133, 134, 134, 135, 135, 136, 137, 137, 138, 139, 139, 140, 140, 141, 142, 142, 143]

A-t-on une chance de trouver une formule directe ? (Sans tricher avec OEIS)

Indice

Dans le cas particulier d'une somme à un seul terme \(F_n\), combien vaut son incrémentation ? Sa décrémentation ? Cela se généralise-t-il ?

Le premier réflexe est de tracer une courbe représentative pour chacune.

xychart-beta
    title "Courbes"
    line [1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, 30, 32, 33, 35, 37, 38, 40, 42, 43, 45, 46, 48, 50, 51, 53, 55, 56, 58, 59, 61, 63, 64, 66, 67, 69, 71, 72, 74, 76, 77, 79, 80, 82, 84, 85, 87, 88, 90, 92, 93, 95, 97, 98, 100, 101, 103, 105, 106, 108, 110, 111, 113, 114, 116, 118, 119, 121, 122, 124, 126, 127, 129, 131, 132, 134, 135, 137, 139, 140, 142, 144, 145, 147, 148, 150, 152, 153, 155, 156, 158, 160, 161, 163, 165, 166, 168, 169, 171, 173, 174, 176, 177, 179, 181, 182, 184, 186, 187, 189, 190, 192, 194, 195, 197, 199, 200, 202, 203, 205, 207, 208, 210, 211, 213, 215, 216, 218, 220, 221, 223, 224, 226, 228, 229, 231, 232, 234, 236, 237, 239, 241, 242, 244, 245, 247, 249, 250, 252, 254, 255, 257, 258, 260, 262, 263, 265, 266, 268, 270, 271, 273, 275, 276, 278, 279, 281, 283, 284, 286, 288, 289, 291, 292, 294, 296, 297, 299, 300, 302, 304, 305, 307, 309, 310, 312, 313, 315, 317, 318, 320, 321, 323, 325, 326, 328, 330, 331, 333, 334, 336, 338, 339, 341, 343, 344, 346, 347, 349, 351, 352, 354, 355, 357, 359, 360, 362, 364, 365, 367, 368, 370, 372, 373, 375]
    line [0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 33, 34, 35, 35, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47, 48, 48, 49, 50, 50, 51, 51, 52, 53, 53, 54, 55, 55, 56, 56, 57, 58, 58, 59, 59, 60, 61, 61, 62, 63, 63, 64, 64, 65, 66, 66, 67, 67, 68, 69, 69, 70, 71, 71, 72, 72, 73, 74, 74, 75, 76, 76, 77, 77, 78, 79, 79, 80, 80, 81, 82, 82, 83, 84, 84, 85, 85, 86, 87, 87, 88, 88, 89, 90, 90, 91, 92, 92, 93, 93, 94, 95, 95, 96, 97, 97, 98, 98, 99, 100, 100, 101, 101, 102, 103, 103, 104, 105, 105, 106, 106, 107, 108, 108, 109, 110, 110, 111, 111, 112, 113, 113, 114, 114, 115, 116, 116, 117, 118, 118, 119, 119, 120, 121, 121, 122, 122, 123, 124, 124, 125, 126, 126, 127, 127, 128, 129, 129, 130, 131, 131, 132, 132, 133, 134, 134, 135, 135, 136, 137, 137, 138, 139, 139, 140, 140, 141, 142, 142, 143]

Incroyable, deux fonctions qui semblent linéaires ! Mais le coefficient directeur n'est pas entier et il faudra surement faire intervenir un arrondi ou une troncature.

Pour trouver le coefficient, rappelons qu'un cas particulier est \(\text{INC}(F_n) = F_{n+1} \approx \varphi F_n\), ainsi le coefficient \(\varphi\) est tout indiqué ! Et son inverse pour \(\text{DEC}\).

Formules

📋 Texte
On finit par exhiber deux formules qui sont correctes :

- $\text{INC}(n)$, c'est `#!py int((n + 1) * phi)`
- $\text{DEC}(n)$, c'est `#!py int((n + 1) / phi)`

Lien avec le mot de Fibonacci

🐍 Script Python
# Les indices du mot infini de Fibonacci commencent à 1, d'où le # initial

MOT_FIB = "#01101001011000100110101000010001100101010010101100000100001..."
A000201 = [None, 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, 30, 32, 33, 35, 37, 38, 40, 42, 43, 45, 46, 48, 50, 51, 53, 55, 56, 58, 59, 61, 63, 64, 66, 67, 69, 71, 72, 74, 76, 77, 79, 80, 82, 84, 85, 87, 88, 90, 92, 93, 95, 97, 98, 100, 101, 103, 105, 106, 108, 110, 111, 113, 114, 116, 118, 119, 121, 122, 124, 126, 127, 129, 131, 132, 134, 135, 137, 139, 140, 142, 144, 145, 147, 148, 150, 152, 153, 155, 156, 158, 160, 161, 163, 165, 166, 168, 169, 171, 173, 174, 176, 177, 179, 181, 182, 184, 186, 187, 189, 190, 192, 194, 195, 197, 199, 200, 202, 203, 205, 207, 208, 210, 211, 213, 215, 216, 218, 220, 221, 223, 224, 226, 228, 229, 231, 232, 234, 236, 237, 239, 241, 242, 244, 245, 247, 249, 250, 252, 254, 255, 257, 258, 260, 262, 263, 265, 266, 268, 270, 271, 273, 275, 276, 278, 279, 281, 283, 284, 286, 288, 289, 291, 292, 294, 296, 297, 299, 300, 302, 304, 305, 307, 309, 310, 312, 313, 315, 317, 318, 320, 321, 323, 325, 326, 328, 330, 331, 333, 334, 336, 338, 339, 341, 343, 344, 346, 347, 349, 351, 352, 354, 355, 357, 359, 360, 362, 364, 365, 367, 368, 370, 372, 373, 375]
A01950 = [None, 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, 49, 52, 54, 57, 60, 62, 65, 68, 70, 73, 75, 78, 81, 83, 86, 89, 91, 94, 96, 99, 102, 104, 107, 109, 112, 115, 117, 120, 123, 125, 128, 130, 133, 136, 138, 141, 143, 146, 149, 151, 154, 157]

Ces deux suites de nombres sont célèbres :

Et si vous avez résolus les problèmes précédents, vous les avez déjà rencontrées !

On remarquera que la suite haute de Wythoff, celle qui donne l'indice du n-ème 1 (départ à 1) dans le mot de Fibonacci est A001950

En résumé

  • A000201[n] == INC(n - 1) == int(n * phi) ; indices des 0
  • A01950[n] == n + INC(n - 1) == int(n * phi**2) ; indices des 1
  • A05206[n] == DEC(n) == int((n + 1) / phi) ; suite G de Hofstadter

Lien avec la fractale présentée

Si on note les représentations minimales de manière condensée en binaire, le tableau de bits devient, avec les bits de poids faibles à droite, cette fois.

\(n\) z_min
$0 $ 0
$1 $ 1
$2 $ 10
$3 $ 100
$4 $ 101
$5 $ 1000
$6 $ 1001
$7 $ 1010
$8 $ 10000
$9 $ 10001
$10 $ 10010
$11 $ 10100
$12 $ 10101
$13 $ 100000
$14 $ 100001
\(\cdots\) ...

Si on fait la concaténation de ces chaines de caractères, on obtient...

01101001011000100110101000010001100101010010101100000100001...

Il s'agit encore du mot infini de Fibonacci !

Ce tableau est également totalement équivalent à la fractale présentée plus tôt.