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 les autres fonctionnelles de listes (cf. le module de liste).

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 maintenus secrets. 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ésolution de l'énigme elle-même.

Question : itérateur de fonctions

Écrire une fonction récursive repeat, telle que

$$ \text{repeat}\;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.

Question : génération d'un intervalle

En déduire la fonction range de type int -> int -> int list, telle que

$$\text{range}\;a\;b = [a;a+1;a+2;\ldots,b-1;b]$$

Attention, cette fois vous n'avez pas le droit d'utiliser une récursion, mais seulement repeat.

Question : crible d'Ératosthène

On souhaite faire la liste de tous les nombres premiers inférieurs à 100 .

• Écrire une fonction is_divisible prenant un entier n et une liste lst d'entiers en argument, et testant si n est divisible par au moins un entier de lst. Son type sera donc:

  1. val is_divisible : int -> int list -> bool
     
• En utilisant List.fold_left, en déduire une fonction sieve, prenant un entier $n$, et retournant la liste de tous les nombres premiers inférieurs à $n$. La fonction passée à List.fold_left s'appelera insert_when_prime : int list -> int -> int list.

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 power : int -> int -> int , pour le calcul de la puissance sur les entiers. (Vous pouvez utiliser une récursion si vous coder la puissance rapide).
• É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$.
• Utiliser valuation pour calculer la factorisation d'un entier $q$. Le résultat devra être une liste de couples de la forme $(p_i,k_i)$ tel que $q = \prod_{i} p_i^{k_i}$. Par exemple:

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

  Ici, primes 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,\ldots,k\}$.
• Transformer la décomposition en facteurs premiers, en une liste de listes des $a^j$ où $a$ est un nombre premier apparaissant dans la décomposition, et $j$ est inférieur ou égal à la valuation de $a$. Pour $136$, vous obtenez :

  1. - : int list list = [[1;2;4;8];[1;17]]
     
• Écrire une fonction qui prend deux listes d'entiers, et calcule la liste des produits $a \times b$, avec $a$ choisi dans la première liste et $b$ choisi dans la seconde liste.
• 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 \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$.

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 \cdot v$ admet au moins deux décompositions.

• pour une valeur de $s$, générer la liste des couples $(u,v)$ possibles,
• et vérifier que pour chaque couple, $u \cdot v$ admet au moins deux décompositions valides.
• Testez toutes les valeurs possibles pour $s$ (de 4 à 198), et gardez celles pour lesquelles la propriété est vrai. Vous devriez obtenir une liste admissible_S 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 une valeur parmi cette dizaine de valeurs. Puisqu'il en déduit $x,y$, toutes les décompositions valides de $p$ autres 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 (dont la somme est admissible), 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 admissible.
• Appeler cette liste de paires possible_solutions.

Question : Trouver $x$ et $y$:

Enfin, Sophie trouve $x$ et $y$. Il doit donc y avoir une paire $x,y$ parmi toutes celles là, dont la somme $x+y$ est unique. C'est donc la solution. Quelle est-elle ?