Nombre=Somme des chiffres aux puissances successives

[anthony_unac]

Bonjour,

Dans les nombreux divertissements mathématiques, on retrouve un jeu aussi amusant qu'agaçant qui consiste à trouver les chiffres qui composent un nombre entier tels que la somme de ces chiffres élevés aux puissances successives est égale .
Formellement, si on écrit , on cherche
Par exemple, convient car
Mais on peut aller plus loin, comme on peut le voir sur la séquence A032799 de l'OEIS : https://oeis.org/A032799
Mais pas trop loin non plus d'après cette démo :

"The sequence is finite with all terms in the sequence having at most 22 digits. Proof: Let n be an m-digit natural number in the sequence for some m. Then 10^(m-1)<=n and n<=9+9^2+...9^m = 9(9^m-1)/8<(9^(m+1))/8. Thus 10^(m-1)<(9^(m+1))/8. Taking logarithms of both sides and solving yields m<22.97 QED. Note proof is identical to that for A208130. [Francis J. McDonnell, Apr 14 2012]"

Faut il en déduire que l'entier est le dernier du genre ou ai je mal compris ?

[samoufar]

Bonsoir,

Je traduis le texte, je pense que ça éclaircit le tout


Proposition

La suite est finie et tous ses termes ont au plus 22 chiffres.

Preuve

Soit un entier à chiffres de la suite, pour un certain .
Alors
. Ainsi, .
En passant au logarithme des deux côtés et en résolvant l'inéquation on obtient CQFD.

[anthony_unac]

Bonsoir,
C'est bien ce qu'il me semblait, il n'existe pas d'entier comportant plus de 22 chiffres solution mais cela ne nous dit toujours pas si est le plus grand dans le genre ? Bon j'imagine que oui vu les acharnés du code qui traînent sur l'OEIS mais ce n'est pas mathématiquement un argument

[samoufar]

Après il suffit de tester tous les nombres en partant de 999...999 et en descendant jusqu'à en trouver un. Ça sera alors le plus grand (mais ça sera long sans une implémentation efficace, ce qui a dû être fait par certains sans doute ).

[nodgim]

@ anthony_unac : as tu essayé déjà à la main pour les nombres à quelques chiffres ?
1 chiffre : 0 à 9
2 chiffres : 89
3 chiffres : 175 et 518
4 chiffres : on doit encore pouvoir y arriver.
5 chiffres : là ça commence à devenir plus compliqué....
....

[nodgim]

J'ai trouvé à la main 3 nombres de 4 chiffres : 1306, 1676 et 2427.
Pour 5 chiffres à la main, il y a vraiment trop de cas possibles ! C'est pour les amateurs de programme.

[anthony_unac]

Bonjour,
Non, je n'ai pas joué le jeu au sens ou je n'ai pas essayé de les trouver à la main.
Bravo à toi Nodgim pour tes résultats car ils sont justes effectivement.
Concernant le nombre suivant (un entier de sept chiffres) , ça risque d'être plus compliqué et c'est là que la machine à due prendre le relais.

[nodgim]

Tiens ! J'aurais pensé qu'il y aurait eu au moins plus d'une solution pour un nombre de chiffres donné. Donc pas de solution pour 5 et 6 chiffres, alors que le nombre de variables grandit. Étonnant. Cela dit, chaque variable manipule des nombres de plus en plus grands quand le nombre a de plus en plus de chiffres, ce qui compense.

[samoufar]

Bonjour,

Le plus grand terme à 7 chiffres de la suite est 2646798.

Après ça devient beaucoup plus compliqué de calculer de manière naïve (càd commencer à 999...999 et descendre jusqu'à trouver) :

Si on veut le faire à partir de 999...999 qui comporte chiffres, on teste dans le pire des cas de l'ordre de nombres. Donc l'algorithme naïf est de complexité temporelle exponentielle !

J'ai fait le test, l'opération de calcul de s'effectue en environ . Ce qui fait pour de l'ordre de... 16 milliards d'années


Par contre on peut optimiser énormément le calcul.
Par exemple en remarquant que comporte seulement 8 chiffres, on sait qu'il n'y a pas besoin de tester les nombres à plus de 8 chiffres qui se terminent par 0, 1, 2, 3, 4, 5, 6 ou 7 (ce qui divise environ par 5 le temps de calcul et bien plus si on optimise encore).

[Ben314]

Salut,
A mon avis, si on veut programmer un truc, il faut évidement utiliser "l'antisymétrique" de l'énoncé si on veut avoir un algo. en temps raisonnable :
Si on cherche tels que alors le "terme le plus important" à gauche est alors qu'à droite, c'est plutôt .
Donc il faut commencer par majorer pour en déduire que doit être au moins égal à ??? pour que la somme des deux dépasse ce qui, si est "un peu grand" ne va laisser que peu de possibilité pour (il devra être au moins égal à???)
Puis il faut ensuite raisonner "dans l'autre sens" : un fois fixé, il y a de forte chance que, vu le majorant qu'on a de , on connaissent précisément les premiers chiffres de (ou bien qu'il n'y ait que 2 possibilités pour ces premiers chiffres) ce qui signifie en fait qu'on connait "direct" les premiers et ça permet d'encadrer bien plus finement

Bref, la connaissance des "de la fin" donne de l'information sur ceux "du début" et... vice versa... et c'est ça qu'il faut programmer (l'info. que ça donne n'est pas obligatoirement une égalité, mais sans doute un encadrement donc il y a une boucle à faire pour tester les différentes valeurs)