MP/MP*: Option Informatique
Devoir surveillé du mercredi 22 mars 2006
Trois exercices



Présentation

La première partie du problème étudie la suite de Stern; cette suite de naturels a été découverte ou redécouverte par de Rahm, Dijkstra et d'autres. Elle possède plusieurs définitions, nous en verrons deux.

La deuxième partie présente un objet mathématique découvert récemment, l'arbre de Calkin-Wilf: les nœuds de cet arbre infini fournissent une énumération exhaustive et sans doublon des rationnels positifs; la suite de Stern apparaît naturellement lorsque l'on observe cet arbre.

Numérotons les nœuds de l'arbre de Calkin-Wilf dans un parcours en largeur. Moshe Newman a établi une formule permettant le calcul du k-ième nœud par itération d'une fonction très simple. La troisième partie prouve cette formule.

Enfin, la quatrième partie montre le lien entre l'arbre de Calkin-Wilf et la version «binaire» de l'algorithme d'Euclide pour le calcul du PGCD.