Discussion :

[Jim69]

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.

[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

[Jim69]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[wiztricks]

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

[Jim69]

pardon mais je ne comprends pas vraiment ce que vous voulez dire.
Quelles sont les factorielles dont j'ai besoin ? Quel est ce dictionnaire ?

[wiztricks]

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