Nombre=Somme des chiffres aux puissances successives

Discussion générale entre passionnés et amateurs de mathématiques sur des sujets mathématiques variés
Avatar de l’utilisateur
anthony_unac
Habitué(e)
Messages: 1099
Enregistré le: 30 Juin 2007, 01:31

Nombre=Somme des chiffres aux puissances successives

par anthony_unac » 11 Fév 2017, 20:14

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
Membre Relatif
Messages: 401
Enregistré le: 28 Mai 2016, 19:43
Localisation: Palaiseau

Re: Nombre=Somme des chiffres aux puissances successives

par samoufar » 11 Fév 2017, 23:03

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.

Avatar de l’utilisateur
anthony_unac
Habitué(e)
Messages: 1099
Enregistré le: 30 Juin 2007, 01:31

Re: Nombre=Somme des chiffres aux puissances successives

par anthony_unac » 11 Fév 2017, 23:09

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
Membre Relatif
Messages: 401
Enregistré le: 28 Mai 2016, 19:43
Localisation: Palaiseau

Re: Nombre=Somme des chiffres aux puissances successives

par samoufar » 11 Fév 2017, 23:18

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
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Nombre=Somme des chiffres aux puissances successives

par nodgim » 12 Fév 2017, 10:20

@ 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
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Nombre=Somme des chiffres aux puissances successives

par nodgim » 12 Fév 2017, 11:03

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.

Avatar de l’utilisateur
anthony_unac
Habitué(e)
Messages: 1099
Enregistré le: 30 Juin 2007, 01:31

Re: Nombre=Somme des chiffres aux puissances successives

par anthony_unac » 12 Fév 2017, 11:57

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
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Nombre=Somme des chiffres aux puissances successives

par nodgim » 12 Fév 2017, 12:05

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
Membre Relatif
Messages: 401
Enregistré le: 28 Mai 2016, 19:43
Localisation: Palaiseau

Re: Nombre=Somme des chiffres aux puissances successives

par samoufar » 12 Fév 2017, 15:19

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).

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 20442
Enregistré le: 11 Nov 2009, 23:53

Re: Nombre=Somme des chiffres aux puissances successives

par Ben314 » 12 Fév 2017, 16:17

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)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

 

Retourner vers ⚜ Salon Mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 4 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite