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 et , compris strictement entre et sont choisis. On communique à Sophie la somme , et à Philippe le produit , mais et sont soigneusement maintenus secrets. S'en suit une curieuse conversation :
" Tu ne connais pas les valeurs de et ", proclame Sophie à Philippe.
"Maintenant, si !" , répond Philippe.
"Et maintenant, moi aussi" réplique finalement Sophie.
Que valent et ?
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
où est répété 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
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:
val is_divisible : int -> int list -> bool
En utilisant List.fold_left, en déduire une fonction sieve, prenant un entier , et retournant la liste de tous les nombres premiers inférieurs à . 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'à , nous pouvons trouver l'unique factorisation de n'importe quel entier inférieur à (et même 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 et , et calcule le plus grand tel que divise .
Utiliser valuation pour calculer la factorisation d'un entier . Le résultat devra être une liste de couples de la forme tel que . Par exemple:
# factorize primes 136;;
- : (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 et , calcule la liste des pour .
Transformer la décomposition en facteurs premiers, en une liste de listes des où est un nombre premier apparaissant dans la décomposition, et est inférieur ou égal à la valuation de . Pour , vous obtenez :
- : int list list = [[1;2;4;8];[1;17]]
Écrire une fonction qui prend deux listes d'entiers, et calcule la liste des produits , avec choisi dans la première liste et 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 en deux facteurs , avec nous intéressent.
Question : restreindre le choix de
Dans l'énigme, Sophie peut déduire de que Philippe ne connait pas la décomposition de en . Donc, pour toute paire avec , admet au moins deux décompositions.
pour une valeur de , générer la liste des couples possibles,
et vérifier que pour chaque couple, admet au moins deux décompositions valides.
Testez toutes les valeurs possibles pour (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 .
En déduire une liste de paires possibles, avec .
Question : prendre en compte la remarque de Philippe
Philippe en déduit lui aussi que prend une valeur parmi cette dizaine de valeurs. Puisqu'il en déduit , toutes les décompositions valides de autres que ont une somme n'appartenant pas à la liste des valeurs encore possible pour .
Pour toutes les paires potentielles (dont la somme est admissible), calculer les décompositions valides de .
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 et :
Enfin, Sophie trouve et . Il doit donc y avoir une paire parmi toutes celles là, dont la somme est unique. C'est donc la solution. Quelle est-elle ?