Python, suites de Syracuse et de Fibonacci

8.1 La suite de Syracuse

On choisit un entier $a > 0$, et on pose $u_0 = a$. Pour tout entier naturel $n$ :

• si $u_n$ est pair, $u_{n+1} = \dfrac{u_n}{2}$ ;
• si $u_n$ est impair, $u_{n+1} = 3u_n + 1$.

Cette suite est définie par un algorithme, avec un test sur la parité. En partant de $6$, on obtient $6, 3, 10, 5, 16, 8, 4, 2, 1$. Arrivée à $1$, la suite tourne en rond : $4, 2, 1, 4, 2, 1\ldots$

En Python, on découpe le travail en deux fonctions : c'est la programmation modulaire. La fonction suivant calcule le terme d'après, et la fonction syracuse construit la liste. Les symboles // donnent le quotient entier.

def suivant(u):
    if u % 2 == 0:
        return u // 2
    return 3 * u + 1

def syracuse(a, n):
    L = [a]
    for k in range(n):
        L.append(suivant(L[k]))
    return L

>>> syracuse(6, 8)
[6, 3, 10, 5, 16, 8, 4, 2, 1]

8.2 Une conjecture ouverte

Pour tous les nombres testés, la suite finit par arriver à $1$. Mais personne n'a su le démontrer : cet énoncé reste une conjecture. Vérifier de très nombreux cas ne fait pas une démonstration.

8.3 La suite de Fibonacci

Elle vient d'un problème de comptage de lapins. Un jeune couple devient adulte en un mois, et chaque mois, tout couple adulte donne naissance à un nouveau couple. On part d'un jeune couple.

Les couples d'un mois sont ceux du mois précédent, plus les nouveau-nés. Il y a autant de nouveau-nés que de couples adultes, c'est-à-dire que de couples présents deux mois plus tôt. Chaque nombre est donc la somme des deux précédents : $F_0 = 1, \quad F_1 = 1 \quad \text{et, pour tout entier naturel } n, \quad F_{n+2} = F_{n+1} + F_n.$

Il faut cette fois deux termes pour calculer le suivant, donc deux premiers termes pour démarrer.

def fibonacci(n):
    L = [1, 1]
    for k in range(n - 2):
        L.append(L[k] + L[k + 1])
    return L

>>> fibonacci(10)
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Une liste garde tous les termes, ce qui permet de les comparer. On peut ainsi écrire max(syracuse(7, 16)), qui renvoie $52$, et len(fibonacci(10)), qui renvoie $10$.