L'objectif de ce travail est d'apprendre à manipuler les listes à l'aide de fonctionnelles.
Remark 1: Il sera interdit d'écrire des fonctions récursives, sauf si l'énoncé d'une question le permet explicitement.
Vous devez utiliser autant que possible les fonctions List.map, List.filter, List.flatten et autres fonctionnelles de listes.
Deux nombres entiers $x$ et $y$, compris strictement entre $1$ et $100$ sont choisis. On communique à Sophie la somme $s = x+y$, et à Philippe le produit $p = x \cdot y$, mais $x$ et $y$ sont soigneusement maintenu secret. S'en suit une curieuse conversation :
Que valent $x$ et $y$ ?
Le sujet de ce TP est de trouver une réponse à cette énigme. Les premières questions vont nous permettre de définir plusieurs outils mathématiques qui nous seront utiles. Seules les dernières questions sont axées sur la résolutions de l'énigme elle-même.
Écrire une fonction récursive iter, telle que
$$ \text{iter}\;n\;f\;v = f\;(f\;(f\;\ldots(f\;v)\ldots))$$
où $f$ est répété $n$ fois dans le membre droit de l'équation.
En déduire une fonction interval de type int -> int -> int list, telle que
$$\text{interval}\;a\;b = [a;a+1;a+2;\ldots,b-1;b]$$
Écrire une fonction pairs prenant deux listes en arguments, et calculant la liste de toutes les paires obtenus en prenant un élément de chaque liste. Par exemple :
On souhaite faire la liste de tous les nombres premiers inférieurs à 100 .
Écrire une fonction relatively_prime prenant un entier $n$ et une liste $l$ d'entiers en argument, et testant si $n$ est relativement premier avec tous les entiers de $l$. Son type sera donc:
Maintenant que nous avons tous les nombres premiers jusqu'à $n$, nous pouvons trouver l'unique factorisation de n'importe quel entier inférieur à $n$ (et même $n^2$ en fait).
Utiliser valuation pour calculer la factorisation d'un entier $q$. Le résultat devra être une liste de couple $(p_i,k_i)$ tel que $q = \prod_{i} p_i^{k_i}$. Par exemple:
Ici, ps est la liste des nombres premiers à utiliser pour la factorisation.
Remark 2: Il est plus naturel pour les fonctions valuation et power d'utiliser une définition récursive. On pourrait les écrire sans utiliser de récursion, mais le résultat serait moins lisible.
À partir de la décomposition en nombre premier d'un entier, on peut facilement générer une liste de ses facteurs. Donner d'abord une fonction qui, prenant deux entiers $a$ et $k$, calcule la liste des $a^j$ pour $j \in \{0,1,\ldots,k\}$. En déduire une fonction calculant la liste des facteurs d'un entier.
Dans le cadre de l'énigme, seules les décompositions d'un entier $p$ en deux facteurs $p = a \cdot b$, avec $2 \leq a \leq b \leq 99$ nous intéressent. Donner une fonction valid_factorisations calculant toutes les décompositions valides (en ce sens) pour un entier $p$ quelconque. Écrire un fonction calculant le nombre de décomposition valide de $p$.
Dans l'énigme, Sophie peut déduire de $s$ que Philippe ne connait pas la décomposition de $p$ en $x \cdot y$. Donc, pour toute paire $u,v$ avec $u+v = s$, $u*v$ admet au moins deux décompositions. Testez toutes les valeurs possibles pour $s$ (de 4 à 198), et garderez celles pour lesquelles la propriété est vrai. Vous devriez obtenir une liste d'une dizaine de valeurs possibles pour $s$.
En déduire une liste de paires $x,y$ possibles, avec $x < y$.
Philippe en déduit lui aussi que $s$ prend un de cette dizaine de valeurs. Puisqu'il en déduit $x,y$, toutes les décompositions valides de $p$ autre que $x \cdot y$ ont une somme n'appartenant pas à la liste des valeurs encore possible pour $s$.
Pour toutes les paires $x,y$ potentielles, calculer les décompositions valides de $x \cdot y$. Garder seulement les paires qui n'admettent qu'une seule décomposition valide dont la somme est possible.
Enfin, Sophie trouve $x$ et $y$. Il doit donc y avoir une paire possible $x,y$ dont la somme $x+y$ est unique parmi toutes les possibilités restantes, c'est la solution. Quel est cette solution ?
