Voici un résumé de l'énoncé du problème 1 "Multiples of 3 and 5" du Project Euler (traduction complète en français ici) :

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

Compréhension du problème

Reformulons le problème : il nous faut trouver la somme de tous les nombres inférieurs à 1000 divisibles par 3 ou 5.

Comme ce problème est normalement assez simple à résoudre, je ne vais pas m'éterniser sur les explications. Sachez juste que :

• Un programme brute force (programme qui teste toutes les valeurs possibles) fonctionne très bien
• Le problème peut être entièrement résolu en utilisant des mathématiques
• Pour savoir si un nombre a est divisible par un nombre b, il faut que le reste de la division euclidienne de ces deux nombres soit égal à 0. En Python, il faut utiliser le signe % pour obtenir le reste d'une division.

Solution programmation

La solution brute force est :

resultat = 0
for i in range(1, 1000):
    if i%3 == 0 or i%5 == 0:
        resultat += i
print(resultat)

Qui peut être réécrite de manière plus condensée : 

print(sum(i for i in range(1, 1000) if i%3 == 0 or i%5 == 0))

Je ne pense pas avoir besoin de donner des explications particulières pour ces codes, si ce n'est que += est une facilitation de langage en Python pour incrémenter.

Solution mathématique

Trouver la somme de tous les nombres inférieurs à 1000 divisibles par 3 ou 5, revient à faire la somme de tous les multiples de 3 inférieurs à 1000, d'y ajouter la somme de tous les multiples de 5 inférieurs à 1000 et d'y soustraire tous les multiples de 15 inférieurs à 1000.

Si on note \(S\) cette somme, on obtient :

$$\begin{align}
S &= \sum_{k = 1}^{\lfloor \frac{1000 - 1}{3} \rfloor} 3 \cdot k + \sum_{k = 1}^{\lfloor \frac{1000 - 1}{5} \rfloor} 5 \cdot k - \sum_{k = 1}^{\lfloor \frac{1000 - 1}{15} \rfloor} 15 \cdot k \\
&= 3 \cdot \sum_{k = 1}^{333} k + 5 \cdot \sum_{k = 1}^{199} k - 15 \cdot \sum_{k = 1}^{66} k
\end{align}$$

En utilisant la somme des n-premier nombres entiers, on arrive au résultat :

$$S = 3 \cdot \frac{333 \cdot 334}{2}+ 5 \cdot \frac{199 \cdot 200}{2} - 15 \cdot \frac{66 \cdot 67}{2}$$

Une simple calculatrice permet alors de trouver le résultat.

Le résultat

La réponse à ce problème est 233168.