Solution : somme des chiffres

Combien existe-t-il de nombres entiers dont l'écriture décimale satisfait aux deux conditions : elle ne contient pas de 0 et la somme de ses chiffres vaut 69 ?

Récurrence

Soit S_n le nombre d'entiers dont l'écriture décimale satisfait aux deux conditions : elle ne contient pas de 0, et la somme de ses chiffres vaut n.

On pose S₀ = 1, et on a évidemment S₁ = 1. Ensuite, on raisonne par récurrence.

Par exemple pour trouver S₄ :

• ou le nombre commence par 1 et la somme des chiffres suivants est 3 : donc il y en a S₃

• ou le nombre commence par 2 et la somme des chiffres suivants est 2 : donc il y en a S₂
• ou le nombre commence par 3 et la somme des chiffres suivants est 1 : donc il y en a S₁
• ou le nombre commence par 4 et il n'y a pas d'autres chiffres : donc il y en a 1 = S₀

soit S₄ = S₃ + S₂ +S₁ + S₀ = 4 + 2 + 1 + 1 = 8, les huit entiers sont : 1111, 112, 121, 13, 211, 22, 31, 4

Jusqu'à S₉ chaque S_n est la somme des précédents, ensuite, il faut se limiter aux 9 précédents.

Ce qui donne la formule : S_n = Sigma(i=1 to min(9,n), S_n-i )

Pour obtenir une relation uniforme (éviter le min), on peut définir S_n = 0 si n < 0.

Si on veut la réponse effective pour S_{69 :}

• on peut programmer la formule avec un logiciel de calcul formel comme Maple :

somme := proc(n)

option remember;

if n = 0 then 1

elif n < 0 then 0

else somme( n - 1 ) + somme( n - 2 ) + somme( n - 3 ) + somme( n - 4 )

+ somme( n - 5 ) + somme( n - 6 ) + somme( n - 7 ) + somme( n - 8 )

+ somme( n - 9 )

end if

end proc

> seq(somme(i),i=1..69);

1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, 32512, 64960,

129792, 259328, 518145, 1035269, 2068498, 4132920, 8257696, 16499120,

32965728, 65866496, 131603200, 262947072, 525375999, 1049716729,

2097364960, 4190597000, 8372936304, 16729373488, 33425781248,

66785696000, 133439788800, 266616630528, 532707885057, 1064366053385,

2126634741810, 4249078886620, 8489784836936, 16962840300384,

33892254819520, 67717723943040, 135302008097280, 270337399564032,

540142091243007, 1079219816432629, 2156312998123448, 4308376917360276,

8608264049883616, 17199565259466848, 34365238264114176,

68662758804285312, 137190215600473344, 274110093801382656,

547680045511522305, 1094280871206611981, 2186405429415100514,

4368502481912840752, 8728396699775797888, 17439593834292128928,

34844822430320143680, 69620982101836002048, 139104773988071530752,

277935437882341678848

• ou aller sur le site http://www.research.att.com/~njas/sequences/A104144

  où on apprend que cette suite est connue et que

  S₆₉ = a(77) = 277935437882341678848