Projet Euler en ATS
Le Projet Euler est une collection de petits problèmes mathématiques, dont la résolution nécessite également des compétences informatiques. J’ai commencé à en résoudre les problèmes en ATS, en utilisant bien sûr de la programmation prouvée : tous les algorithmes utilisés seront prouvés corrects (et vérifiés par le compilateur).
Vous trouverez ici les sources ATS des-dits problèmes, ainsi que diverses librairies regroupant les fonctions utiles dans plusieurs problèmes. Un problème ne sera marqué
(Résolu
) que lorsque toutes des preuves nécessaires seront écrites et acceptées par le compilateur. De plus, le calcul de la solution ne doit pas dépasser
une minute.
Vous pouvez compiler ces programmes avec ce Makefile générique
, ou télécharger le tout ici
.
Problèmes
Problème 1 (code source ATS
, problème original) (Résolu)
Si on fait la liste des entiers naturels strictement inférieurs à 10 qui sont multiples de 3 ou de 5, on obtient 3, 5, 6 et 9. La somme de ces multiples vaut 23.
Trouver la somme des multiples de 3 ou de 5 strictement inférieurs à 100.
Problème 2 (code source ATS, problème original) (Résolu)
Chaque terme de la suite de Fibonacci est obtenu en ajoutant les deux termes précédents. En commençant avec 1 et 2 les 10 premiers termes seront :
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Trouver la somme de tous les termes pairs de la suite de Fibonacci qui ne dépassent pas quatre millions.
Problème 3 (code source ATS, problème original) (En cours)
Les facteurs premiers de 13195 sont 5, 7, 13 et 29.
Quel est le plus grand facteur premier du nombre 600851475143 ?
Problème 4 (code source ATS, problème original) (En cours)
Un palindrome est un nombre qui se lit de la même façon dans les deux sens. Le plus grand palindrome qui s’écrit comme produit de deux nombres à deux chiffres est 9009 = 91 × 99.
Trouver le plus grand palindrome qui s’écrit comme produit de deux nombres à trois chiffres.
Problème 5 (code source ATS, problème original) (En cours)
2520 est le plus petit nombre pouvant être divisé par tous les nombres de 1 à 10 sans reste.
Quel est le plus petit entier positif divisible par tous les nombres de 1 à 20 ?
Problème 6 (code source ATS, problème original) (Résolu)
La somme des carrés des dix premiers entiers naturels est :
1² + 2² + … + 10² = 385
Le carré de la somme des dix premiers entiers naturels est :
(1 + 2 + … + 10)² = 55² = 3025
Ainsi, la différence entre la somme des carrés des dix premiers entiers naturels et le carré de la somme est 3025 - 385 = 2640.
Trouver la différence entre la somme des carrés des cent premiers entiers naturels et le carré de la somme.
Problème 7 (code source ATS, problème original) (En cours)
En faisant la liste des six premiers nombres premiers : 2, 3, 5, 7, 11 et 13, on voit que le sixième nombre premier est 13.
Quel est le 10001e nombre premier ?
Librairies
Librairie lib_arith (code source ATS) (En cours)
Fonctions basiques d’arithmétique : croissance de la multiplication, PGCD, PPCM, etc.
Librairie lib_prime (code source ATS) (En cours)
Fonctions concernant les nombres premiers : définition, existence (et calcul) de facteurs premiers, etc.
Librairie lib_decimal (code source ATS) (En cours)
Fonctions concernant la représentation des nombres en base 10, palindromes, etc.