Aller au contenu

2#

15/05/22

Toujours avec le projet Euler on va aujourd'hui s'attaquer au deuxième problème.

Ennoncé

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with \(1\) and \(2\), the first \(10\) terms will be:

\(1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots\)

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Nous devons alors trouver la somme des nombres pairs de la suite de Fibonacci, en nous arrettant dès que le résultat de la suite dépasse \(4000000\).

Avec mes connaissances limitées je n'ai pas pu résoudre ce problème 100% mathématiquement, j'ai du utiliser l'informatique pour calculer la suite de Fibonacci par exemple. Notre problème revient alors à trouver :

\[ S = \sum_{x \in F} \text{si} \ x \equiv 0 \bmod 2 \]

Avec \(F\) l'ensemble des nombres de la suite de Fibonacci dont la somme est strictement inférieure à \(4000000\).

Pour calculer cet ensemble j'ai codé un script en Python :

# La limite pour arrêter la récurrence
limit = 4000000

# Suite de Fibonacci récurrente
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

# Itération jusqu'à la limite
i = 0
while (r := fib(i)) < limit:
    i += 1

# Affichage du nombre d'itérations pour arriver à la limite
# et le ième terme de la suite
print(i - 1, fib(i - 1))

# 33 3524578

Il faut donc \(33\) itérations pour ne pas dépasser la limite. J'ai ensuite modifié ce script pour faire la somme des termes pairs :

# La limite pour arrêter la récurrence
limit = 4000000
+ evens = list()

# Suite de Fibonacci récurrente
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

# Itération jusqu'à la limite
i = 0
while (r := fib(i)) < limit:
+    if r % 2 == 0:
+        evens.append(r)
    i += 1

- # Affichage du nombre d'itérations pour arriver à la limite
- # et le ième terme de la suite
- print(i - 1, fib(i - 1))

+ # Affiche la somme des entiers pairs de la suite de Fibonacci
+ # dans la limite imposée
+ print(sum(evens))
# La limite pour arrêter la récurrence
limit = 4000000
evens = list()

# Suite de Fibonacci récurrente
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

# Itération jusqu'à la limite
i = 0
while (r := fib(i)) < limit:
    if r % 2 == 0:
        evens.append(r)
    i += 1

# Affiche la somme des entiers pairs de la suite de Fibonacci
# dans la limite imposée
print(sum(evens))

# 4613732

On a donc la solution à notre problème : \(S = 4613732\).