#1

01/05/22

Aujourd'hui on va revoir un peu nos bases de lycée avec le projet Euler, un site qui met à disposition des problèmes simples et de plus en plus difficiles. Je n'en ai jamais résolu donc c'est le moment de nous y mettre. On y va avec le premier problème du site. Je vais dans un premier temps faire une résolution strictement mathématique et ensuite proposer une seconde manière avec l'informatique.

Ennoncé

If we list all the natural numbers below \(10\) that are multiples of \(3\) or \(5\), we get \(3, 5, 6, 9\). The sum of these multiples is \(23\).

Find the sum of all the multiples of \(3\) or \(5\) below \(1000\).

Désolé pour les non anglophones, mais ce problème nous demande donc de trouver la somme des entiers naturels, multiples de \(3\) ou \(5\), stricement inférieurs à \(1000\).

Résolution mathématique

Pour ce problème, ce qui m'est venu à l'esprit était d'abord de décomposer cette somme. En effet puisque nous cherchons la somme des multiples de \(3\) ou \(5\), on peut utiliser deux ensembles pour ensuite les additionner. Prennons \(A\), l'ensemble des multiples de \(3\) strictement inférieurs à \(1000\), et \(B\), l'ensemble des multiples de \(5\) strictement inférieurs à \(1000\). Il nous sera plus simple de calculer l'un puis l'autre et les "additionner" pour trouver \(C\), l'ensemble des multiples de \(3\) ou \(5\) strictement inférieurs à \(1000\).

\[ A = \sum_{n = 0}^{333} 3n, \quad B = \sum_{n = 0}^{199} 5n \]

Bien, nous avons alors nos deux ensembles de multiples, respectivement de \(3\) et de \(5\), strictements inférieurs à \(1000\). Mais on ne peut pas en l'état simplement additionner ces deux ensembles pour avoir la solution à notre problème de base. En effet, il existe dans ces deux ensembles, des multiples de \(3\) et de \(5\), ce qui rendrait notre somme totale plus importante que la solution, car nous aurions compté certains multiples plusieurs fois.

Pour ce faire nous allons utiliser la théorie des ensembles, et plus particulièrement l'algèbre des parties d'un ensemble pour calculer la somme des multiples sans doublons.

\[ C = \left( A \cup B \right) \]

\(C\) est donc l'ensemble des multiples sans doublon de \(3\) ou \(5\) strictement inférieurs a \(1000\). Calculons a présent la somme des élements qui le composent :

\[ S = \sum_{x \in C} x = 233168 \]

Résolution informatique

Je vais utiliser Python pour ce problème :

# Liste des multiples de 3 ou 5
multiples = list()

# Pour tout entier naturel x strictement inférieur à 1000
for x in range(1000):
    # Si x est un multiple de 3 ou 5 (sans doublon)
    if x % 3 == 0 or x % 5 == 0:
        # On l'ajoute à la liste des multiples
        multiples.append(x)

# Affichage de la somme des éléments de la liste
print(sum(multiples))

# 233168