L'objectif de ce travail est d'apprendre à manipuler les listes à l'aide de fonctionnelles.

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 :

• " Tu ne connais pas les valeurs de $x$ et $y$", proclame Sophie à Philippe.
• "Maintenant, si !" , répond Philippe.
• "Et maintenant, moi aussi" réplique finalement Sophie.

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.

Question : itérateur de fonctions

Écrire une fonction récursive iter, telle que

$$\text{iter}nfv=f(f(f\dots (fv)\dots ))$$

où $f$ est répété $n$ fois dans le membre droit de l'équation.

Question : génération d'un intervalle

En déduire une fonction interval de type int -> int -> int list, telle que

$$\text{interval}ab=[a;a+1;a+2;\dots ,b-1;b]$$

Question : produit de deux listes

É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 :

Question : crible d'Ératosthène

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:

  1. val relative_prime : int -> int list -> bool
     
• En utilisant List.fold_left, en déduire une fonction primes, prenant un entier $n$, et retournant la liste de tous les nombres premiers inférieurs à $n$.

Question : factorisation d'un entier

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).

• Écrire une fonction récursive valuation, qui prend deux entiers $p$ et $n$, et calcule le plus grand $k$ tel que $p^k$ divise $n$.
• Écrire une fonction récursive power, pour le calcul de la puissance sur les entiers.
• 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:

  1. # factorize ps 136;;
     
  2. - : (int * int) list = [(2, 3); (17, 1)]
     

  Ici, ps est la liste des nombres premiers à utiliser pour la factorisation.

Question : facteurs d'un entier

À 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,\dots ,k\}$. En déduire une fonction calculant la liste des facteurs d'un entier.

Question : décomposition valide

Dans le cadre de l'énigme, seules les décompositions d'un entier $p$ en deux facteurs $p=a\cdot b$, avec $2\le a\le b\le 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$.

Question : restreindre le choix de $s$

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\ast 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$.

Question : prendre en compte la remarque de Philippe

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.

Question : Trouver $x$ et $y$:

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 ?