Calcul d'une somme de factorielles

Version imprimable

11/02/2017, 14h05
Jim69

Calcul d'une somme de factorielles

Bonjour à tous,

J'ai besoin de votre aide pour résoudre un exercice de programmation Python.

L'énoncé est :
Trouver la somme de tous les entiers qui sont la somme des factorielles de leurs chiffres, en écriture décimale.

De tels nombres sont les factorions. Il n'y en a que 4 en base 10 : 1 ; 2 ; 145 ; 40 585.
La somme est donc évidente.

Mais comment programmer le calcul de tels nombres ? Et par suite, leur somme ?

Merci de votre aide.
11/02/2017, 15h01
wiztricks

Salut,

Vous savez écrire une fonction est_factorion(n) qui retourne Vrai si n est un factorion.
Vous savez qu'en représentation décimale les factorions ont une borne supérieure qu'on notera bs.
Donc vous savez construire la liste des factorions en testant tous les entiers de 1 à bs.

- W

Merci

Merci pour votre réponse.

C'est en effet le programme que j'ai écrit. Mais il est très lent (environ 5 mins). N'avez-vous pas quelques astuces pour le rendre plus efficace ?

Voici ce que j'ai programmé :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def factorielle(n):
    """Calcule la factorielle de n"""
    x=1
    for i in range(1,n+1):
        x = x*i
    return x
 
def est_factorion(p):
    L = list(str(p))
    s = 0
    b = False
    for i in L:
        s = s + factorielle(int(i))
    if s== p:
        b = True
    return b
 
def sommetotale():
    somme = 0
    maxi = 10**7
    for p in range(1,maxi+1):
        if est_factorion(p)==True:
            somme = somme + p
    return somme

11/02/2017, 15h25
wiztricks

Citation:

Envoyé par Jim69

C'est en effet le programme que j'ai écrit. Mais il est très lent (environ 5 mins). N'avez-vous pas quelques astuces pour le rendre plus efficace ?

Puisque vous savez que vous allez faire la somme de factorielles de nombres inférieurs à 9, inutile de les recalculer à chaque fois. Vous fabriquez, au début, un dictionnaire "factorielles" avec la valeur des factorielles n qui vous intéressent.

Ceci dit, ca serait bien de mieux calculer votre borne supérieure car elle ne devrait pas dépasser 2*10**6 ce qui est ~ 10 fois moins grand que 10**7.

- W
12/02/2017, 13h36
Jim69

Précisions

pardon mais je ne comprends pas vraiment ce que vous voulez dire.
Quelles sont les factorielles dont j'ai besoin ? Quel est ce dictionnaire ?
12/02/2017, 13h50
wiztricks

Citation:

Envoyé par Jim69

Quelles sont les factorielles dont j'ai besoin ? Quel est ce dictionnaire ?

Est ce que vous avez besoin des factorielles de nombres autres que de 0 à 9?
Un dictionnaire est une structure de base de Python, l'objet "dict".
Mais si vous voulez que çà aille plus vite encore, revisitez le calcul de la borne supérieure: 10**7, c'est 5 à 8 fois trop grand.

- W