Histoire

Eurysthée demanda à Hercule pour son 8^e travail de capturer les juments de Diomède, le roi de Thrace. Ces juments, devenues carnivores car le roi ne les nourrissait que de chair humaine, étaient réputées indomptables.

Hercule se rendit donc à la capitale de Thrace. Afin de s'emparer des juments, il fallait tout d'abord les calmer. Pour cela, Hercule eut l'idée de les gaver mais de manière raisonnable.

PS : pour rétablir la vérité "historique", c'est en fait le roi Diomède qu'Hercule jeta dans les mangeoires des juments pour les calmer.

Défi

Hercule estima rapidement que la masse de nourriture à fournir aux juments devait être comprise entre 123456 et 165432 grammes et imagina ironiquement que la quantité devait correspondre à un nombre frugal (voir plus loin). Pour aider Hercule, pouvez-vous déterminer combien de choix il a ?

Un nombre frugal est un entier naturel qui a strictement plus de chiffres dans son écriture que dans sa décomposition en facteurs premiers, exposants différents de 1 inclus :

• 125 = 5³ est frugal (125 : 3 chiffres et sa décomposition 2)
• 25 = 5² n'est pas frugal (25 : 2 chiffres et sa décomposition 2)
• 58 = 2*29 n'est pas frugal (58 : 2 chiffres et sa décomposition 3)
• 126 = 2*3²*7 n'est pas frugal (126 : 3 chiffres et sa décomposition 4)
• 128 = 2⁷ est frugal (128 : 3 chiffres et sa décomposition 2)
• 232 = 2³*29 n'est pas frugal (232 : 3 chiffres et sa décomposition 4)

Pour information les nombres frugaux inférieurs à 1000 sont les suivants : 125, 128, 243, 256, 343, 512, 625, 729.

Testez votre code

Si l'énoncé indique comme entrée (100, 1000), alors vous devez répondre 8.