Énoncé
Prenons un entier n, et écrivons le en base b. On définit l'opération qui consiste à calculer la somme des 2^chiffres dans cette écriture. Par exemple, l'entier 10 s'écrit 101 en base 3, ce qui nous donne 2^1+2^0+2^1 = 5. Ou encore 10 s'écrit 22 en base 4, ce qui donne 2^2+2^2 = 8.
Lorsque l'on itère ce procédé sur un entier (en l'appliquant à nouveau sur le dernier résultat), on peut facilement prouver que l'on va finir par "boucler", c'est-à-dire retomber plusieurs fois sur le même entier. Lorsque cela arrive, on définit la taille de la boucle comme le nombre minimal d'itérations entre deux répétitions d'un même entier.
Par exemple, reprenons le cas de la base b = 4 avec l'entier 10. On a déjà vu que la première étape nous donnera 8. 8 s'écrit 20 en base 4, on obtient donc 2^2 + 2^0 = 5. 5 s'écrit 11 en base 4, et on obtient 2^1 + 2^1 = 4. 4 s'écrit 10 en base 4, ce qui nous donne 2^1+2^0 = 3. Enfin 3 s'écrit 3 en base 4, ce qui donne 2^3 = 8. L'entier 8 a déjà été obtenu en première étape, et la taille de la boucle est donc 3.
L'objectif de cet exercice est de compter combien d'entiers strictement positifs inférieurs ou égaux à n sont tels que ce processus, appliqué en base b, donne des boucles de taille l.
Entrée
L'entrée comporte sur une première ligne la base b utilisée pour le procédé puis sur une seconde ligne le nombre n maximum à tester, lui même suivi d'un retour à la ligne. La base b sera toujours inférieure à 16, et n inférieur à 10000. Enfin, la troisième ligne comporte la longueur des boucles recherchées, l, suivie d'un retour à la ligne.
Sortie
La sortie comportera le nombre d'entiers compris entre 1 et n inclus qui sont tels que leurs boucles sont de taille l lorsque le procédé est itéré en base b.
Exemples
Squelette CamlLight
Squelette OCaml