LES SUITES DE CONWAY

D'après Bruno Salvy

Cet exercice sur la récursivité est difficile. Je vous demande d' essayer de le faire et de me l'envoyer à l'adresse beal@monge.univ-mlv.fr avant dimanche.

Une solution de cet exercice apparaîtra ici lundi matin.

Partant de 1, on écrit une suite de mots obtenus en comptant les chiffres successifs du mot précédent. Le deuxième mot est 11 parce qu'il y a un 1 dans ``1''. Ensuite il y a deux 1, donc le troisième mot est 21, etc. Les premiers mots sont

1, 11, 21, 1211, 111221, 312211, 13112221,... On considère ensuite la suite des longueurs de ces mots : 1, 2, 2, 4, 6, 6, 8,... Un joli théorème dû à Conway montre que cette suite des longueurs vérifie une récurrence linéaire à coefficients constants d'ordre 72.

L'objectif de l'exercice est d'écrire un programme qui calcule les N premiers éléments de la suite des longueurs (par exemple pour N=40), mais sans utiliser de tableau pour contenir les mots (ce qui nécessite rapidement trop de mémoire). Pour cela on construit simultanément tous les mots du premier au Nième, mais en n'en conservant qu'une information partielle : la valeur du dernier chiffre construit dans chaque mot (il s'agit nécessairement d'un 1, d'un 2 ou d'un 3), et le nombre de fois qu'il est répété. On utilise trois tableaux :

le tableau des longueurs, dont l'élément d'incide i indique la longueur déjà construite du ième mot ;
un tableau dont l'élément d'incide i indique le dernier chiffre ajouté au ième mot ;
un tableau dont l'élément d'incide i indique le nombre d'occurrences du dernier chiffre ajouté au ième mot.

Au début tout est initialisé à zéro, sauf le premier mot. Le coeur du programme est une procédure qui prend en argument un chiffre et un indice, et va ajouter ce chiffre au mot d'indice donné, et propager les modifications nécessaires.

Une bonne programmation de cet exercice doit être limitée par le temps d'exécution et non par la mémoire.