Aller au contenu

Nombres qui serpentent⚓︎

On dira d'un entier qu'il serpente si ses chiffres alternent entre croissants et décroissants quand on les lit. Par exemple :

  • \(8\), \(90\), \(243\,516\) et \(31\,524\) sont des nombres serpent ;
  • \(44\), \(123\) et \(4235\) ne sont pas des nombres serpent.

Objectif : Compter les nombres serpent qui ont \(n\) chiffres, pour \(n\) inférieur à 100. Les zéros de tête sont interdits (sauf pour zéro lui-même) pour les nombres, ainsi \(08\) ne compte pas comme un nombre serpent. Calculer un tableau d'entiers serpent de longueur au moins 100 tel que serpent[n] donne l'effectif des nombres serpent à n chiffres.

Exemples
  • Les nombres serpent à 0 chiffre n'existent pas. Il n'y en a aucun ; 0.
  • Les nombres serpent à 1 chiffre sont \(0\), \(1\), \(2\), \(\cdots\), \(8\), et \(9\). Il y en a 10.
  • Parmi les nombres serpent à 2 chiffres, il y a \(10\), \(12\), \(13\), ..., \(20\), \(21\), \(23\), ..., \(98\). Il y en a 81 : de \(10\) inclus à \(100\) exclu, il y en a 90, auquel on enlève les 9 nombres \(11\), \(22\), ..., \(99\) qui ne sont pas serpent.
  • Parmi les nombres serpent à 3 chiffres, il y a \(101\), \(121\), \(120\), ..., \(205\), \(218\), \(230\), ..., \(989\). Il y en a 525.
🐍 Console Python
>>> serpent[0]
0
>>> serpent[1]
10
>>> serpent[2]
81
>>> serpent[3]
525
>>> len(serpent) >= 100
True
###
# testsbksl-nlbksl-nlassert serpent[0] == 0bksl-nlassert serpent[1] == 10bksl-nlassert serpent[2] == 81bksl-nlassert serpent[3] == 525bksl-nlassert len(serpent) >= 100bksl-nlbksl-nl# autres testsbksl-nlbksl-nlSERPENT = [0, 10, 81, 525, 3105, 18939, 114381, 693129, 4195557, 25405586, 153820395, 931359050, 5639156409, 34143908573, 206733865761, 1251728824798, 7578945799704, 45888871327435, 277847147039527, 1682304127857000, 10185986079451152, 61673933253012813, 373422269794761171, 2260990733622821388, 13689807788336374413, 82888812632681299575, 501873756436963255725, 3038736584593404112888, 18398889984004648394684, 111401282480312690455535, 674510568248786542723384, 4084014982140900066996999, 24727823639079446292398973, 149721601071325722314771768, 906531773865227322540527599, 5488852985453577921599786404, 33233812608096915187160862646, 201223516716003090938495558273, 1218364686502763138912251531858, 7376933539095247157524690209596, 44665730255556705813455277892969, 270441294975640547699726057576357, 1637463299259559727190050998356877, 9914484608068134973197170061461591, 60030050803623279460905640700537146, 363468918651916171818101177606787775, 2200725354342352358032848391711429287, 13324914006975819086503546268399064826, 80679460043917672551257824285696701631, 488496606399894533135228090580518726849, 2957740846732444497653596441045121744779, 17908478384122192100208036703515396114945, 108431946763990227509406490644619239949670, 656531885447794265344437789229847771602593, 3975157962881656804262109523464275982054206, 24068718032001765864399208734778590812059100, 145730859783006115692556683131127947572716351, 882368702182510621630923925514359365784813975, 5342550834809792396806303497681900898790602948, 32347984863840919439702872508060799643996329921, 195860022132767463457194622209195721131511619393, 1185889891791338408154534460189644031233260498090, 7180305710879381718473109708289839840279416225259, 43475191464705279658821205861906473192979193394551, 263232841190727052129577046753774486800584662952576, 1593817677320544472069315699698021405961289198127352, 9650219847374200686866980990825185077113651584259915, 58429985077851243131664519519650782811471472008138262, 353780868228289794214717741134865565936022487352042972, 2142066313342370732999494929764219945531265582381574084, 12969746254891643527206138735713153473581856857600095022, 78528996450069182818170035206950924986262776615228842359, 475476016435488792922724897174988743962786201248439181821, 2878904002664891282213725487897616787658753354127999437145, 17431138417229580981375607929954799920484191208458836849334, 105541756946171068442094408895636846737397539224743995138242, 639032413871166799425569675259991298503891964738270377571646, 3869202463497791194390022403538813795184824191022263105120261, 23427180497538227918384894216032536344822982120913486859005897, 141846489358451945872383596558786903972944914449980284295419669, 858849682975367577620868729238136646340508021279438150851189203, 5200148282012719554761322719583518251776093190150646249093143114, 31485768337525729063232789086930259474485679688747287900236134643, 190639488345634999172037991756500352751157724547714851328253128848, 1154280693648192732866441010454314021643048294494184927145989749181, 6988918881870570231769912232187671511248169744379692168541703509970, 42316385785669385595814350388619174876388240296223393673888607531882, 256216524505193716144733781060865175999482846906506651739660845744675, 1551335403784699437467403137673555159940026653854455786424502055338943, 9392998908573720332591434332116379298964835183480715231431284456457957, 56872568163674679661793660628819558901413442844685202596077017341738809, 344351047095241664581365027406377518948639259453576986455463834228076289, 2084970794607558707929544265766774574113298602455891036247922071247187506, 12624045290514652253974190059423751220374380450784779710821698749343369568, 76435852199532490537114357525478173578997382169325263461986888368804125371, 462802482644657363293397846264195190536976947251737947227949204965780224431, 2802168508345203224585165008456703166541527129222571530462213246984687687723, 16966521666631831399368304014981269907585511181598421802474676023379660074148, 102728603439442098192781482549970023263233791039643568211308707933725742061091, 621999380425342872846895049949523920352287482295049627234230430671848280308249]bksl-nlbksl-nlfor n, attendu in enumerate(SERPENT):bksl-nl assert serpent[n] == attendu, f"Erreur pour n = {n}"bksl-nlbksl-nl ∞/∞

serpent = [0, 10]bksl-nl# À compléter avec ou sans fonction...bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert serpent[0] == 0bksl-nlassert serpent[1] == 10bksl-nlassert serpent[2] == 81bksl-nlassert serpent[3] == 525bksl-nlassert len(serpent) >= 100bksl-nlbksl-nlserpent = [0, 10]bksl-nlserpentpy-undcroissant = [0] + [1] py-str 9bksl-nlserpentpy-unddecroissant = [0] + [1] py-str 9bksl-nlbksl-nlfor py-und in range(2, 100):bksl-nl newpy-undcroissant = [0] py-str 10bksl-nl newpy-unddecroissant = [0] py-str 10bksl-nl for i in range(10):bksl-nl newpy-undcroissant[i] = sum(serpentpy-unddecroissant[j] for j in range(0, i))bksl-nl newpy-unddecroissant[i] = sum(serpentpy-undcroissant[j] for j in range(i+1, 10))bksl-nl serpentpy-undcroissant = newpy-undcroissantbksl-nl serpentpy-unddecroissant = newpy-unddecroissantbksl-nl serpent.append(sum(serpentpy-undcroissant) + sum(serpentpy-unddecroissant))bksl-nlbksl-nl# testsbksl-nlbksl-nlassert serpent[0] == 0bksl-nlassert serpent[1] == 10bksl-nlassert serpent[2] == 81bksl-nlassert serpent[3] == 525bksl-nlassert len(serpent) >= 100bksl-nlbksl-nl

A

On peut remplacer les lignes 6 à 10 par des listes en compréhension.

🐍 Script Python
new_croissant = [sum(serpent_decroissant[j] for j in range(0, i)) for i in range(10)]
new_decroissant = [sum(serpent_croissant[j] for j in range(i+1, 10)) for i in range(10)]

À la suite de quoi, il est possible de se passer des tableaux new_* de manières explicites. Ils seront toutefois toujours créés par Python !!! Le code de la boucle devient alors

🐍 Script Python
for _ in range(2, 100):
    serpent_croissant, serpent_decroissant = (
        [sum(serpent_decroissant[j] for j in range(0, i)) for i in range(10)],
        [sum(serpent_croissant[j] for j in range(i+1, 10)) for i in range(10)],
    )
    serpent.append(sum(serpent_croissant) + sum(serpent_decroissant))

On a ici un style plutôt fonctionnel très dense.

Pour aller plus loin⚓︎

Ici, on calcule les termes de serpent de proche en proche.

En utilisant du calcul matriciel, ou mieux polynomial, on pourra calculer des termes éloignés de serpent. Il faudra maitriser l'exponentiation rapide et le calcul modulaire.

Z

Indice 1

Si on sait que :

  • Il y a \(A\) nombres serpent de taille 20 qui finissent par 0 en décroissant.
  • Il y a \(B\) nombres serpent de taille 20 qui finissent par 1 en décroissant.
  • Il y a \(C\) nombres serpent de taille 20 qui finissent par 2 en décroissant.
  • Il y a \(D\) nombres serpent de taille 20 qui finissent par 3 en décroissant.
  • Il y a \(a\) nombres serpent de taille 20 qui finissent par 0 en croissant.
  • Il y a \(b\) nombres serpent de taille 20 qui finissent par 1 en croissant.
  • Il y a \(c\) nombres serpent de taille 20 qui finissent par 2 en croissant.
  • Il y a \(d\) nombres serpent de taille 20 qui finissent par 3 en croissant.

Pouvez-vous déduire la quantité de nombres serpent à 21 chiffres qui finissent par 3 en croissant ?

Solution

Il s'agit de \(A+B+C+D\). En effet, s'il finit par 3 en croissant, c'est qu'avant, c'était 0, 1, 2 ou 3, qu'il était de taille 20 et qu'il finissait en décroissant.

Indice 2

Généraliser une formule qui donne :

  • l'effectif des nombres serpent de taille \(n+1\) qui finissent par i en décroissant ;
  • l'effectif des nombres serpent de taille \(n+1\) qui finissent par i en croissant.

Tout cela en fonction des effectifs pour ceux de taille \(n\).

Indice 3

On utilisera deux tableaux :

  • serpent_croissant de longueur 10, qui indique pour chaque chiffre i de 0 à 9, combien de nombres serpent à \(n\) chiffres se finissent par i en croissant.
  • serpent_decroissant de longueur 10, qui indique pour chaque chiffre i de 0 à 9, combien de nombres serpent à \(n\) chiffres se finissent par i en decroissant.

Écrire les instructions qui permettent :

  • de construire deux nouveaux tableaux serpent_croissant_suivant et serpent_decroissant_suivant qui contiennent les effectifs suivants en fonction des précédents.
  • de remplacer des deux anciens tableaux par les nouveaux.
Indice 4

Écrire l'instruction simple qui calcule et stocke la bonne valeur de serpent[n] en fonction de serpent_croissant et serpent_decroissant.

Indice 5

Initialiser correctement toutes vos variables et mettre en place la boucle qui fait progresser votre problème ; on parle de programmation dynamique.