écrire un programme Python qui donne la liste de tous les nombres dit "factorions".
Vous serez plus en confiance si vous savez que vous devez trouver 4 solutions.
Détaillons :
*) factorielle, vous savez ce que c'est ? Je rappelle que par exemple factorielle de 7 et qui se note 7!, c'est le produit 1*2*3*4*5*6*7 lequel vaut d'ailleurs 5040. Donc factorielle n, noté n!, c'est le produit de tous les entiers de 1 à n. On convient que 0!=1.
Voici un programme Python 2.6 qui affiche les 10 premières factorielles :
>>> from math import factorial as f
>>> for k in range(10):print "%s ! = %s" %(k,f(k))
...
0 ! = 1
1 ! = 1
2 ! = 2
3 ! = 6
4 ! = 24
5 ! = 120
6 ! = 720
7 ! = 5040
8 ! = 40320
9 ! = 362880
*) Un factorion, c'est juste un entier positif qui est égal à la somme des factorielles de ses chiffres (en base 10). Par exemple 52 n'est pas un factorion car 5! + 2! = 60 + 2 = 62 != 52. Par contre 145 est un factorion car
1! + 4! + 5! = 1 + 24 + 120 = 145.
*) Pour conclure, vous devez encore savoir qu'on peut démontrer facilement qu'un factorion peut avoir au maximum 7 chiffres.
Voilà, vous avez tout ce qu'il faut pour résoudre le problème, lequel est assez facile. Indiquez le temps de calcul de votre programme.
Un petit test rapide peu être un peu (beaucoup ? ) alourdi par mes habitudes du C
from math import factorial as fact
from time import clock
def decoupe(a):
if a == 0:
return [0]
res = []
while a > 0:
res.append(a%10)
a //= 10
return res
def factorion(a):
res = 0
for i in decoupe(a):
res += fact(i)
return res == a
def trouver_factorion(nb_max):
i = 0
res = []
while nb_max > 0:
if factorion(i):
nb_max -= 1
res.append(i)
i += 1
return res
debut = clock()
print(trouver_factorion(4<secret/>))
fin = clock()
print('Temps :', fin-debut)
Un petit test rapide peu être un peu (beaucoup ? )
Testes-tu la totalité des 7 chiffres possibles ? Je ne crois pas, tu fonctionnes d'après le nombre de résultats trouvés.
Oui c'était mon but, vu que tu avais dis 'on en trouvera 4', mais je vais modifier si ce n'est pas ce que tu attendais
Après modif (y'a eû une 'légère' hausse du temps )
from math import factorial as fact
from time import clock
def decoupe(a):
if a == 0:
return [0]
res = []
while a > 0:
res.append(a%10)
a //= 10
return res
def factorion(a):
res = 0
for i in decoupe(a):
res += fact(i)
return res == a
def trouver_factorion():
i = 0
res = []
for i in range(10**7):
if factorion(i):
res.append(i)
return res
debut = clock()
print(trouver_factorion())
fin = clock()
print('Temps :', fin-debut)
J'ai fait une version qui permet de cherche les Factorions des autres bases (jusqu'à 16)
J'arrive à 31s pour la base 10 et puisque pour la base 16, on peut simplement dire que les factorions sont inférieurs à <math>\(\min(10^{11} - 1, (16 - 1)!\cdot 11) = 99999999999\)</math> (les factorions ont 11 chiffres maximum avec la base 16).
Et donc avec une simple méthode d'itération, j'ai toujours pas obtenu le résultat.
Voici le code :
from math import factorial as fact
from itertools import imap
from itertools import count
from time import clock
import string
import sys
def base(x, b):
if not x:
return '0'
re = ''
chiffre = string.digits + string.letters[0:26]
while x:
x, re = x / b , re + chiffre[x % b]
return re[::-1]
def factorion(b = 10):
ls = []
lsFact = [fact(n) for n in xrange(b)]
lsMaxChiffre = {2: 2, 3: 2, 4: 3, 5: 3, 6: 4, 7: 5, 8: 5, 9: 6, 10: 7, 11: 8, 12: 8, 13: 9, 14: 10, 15: 11, 16: 11}
lim = min(10**lsMaxChiffre[b] - 1, fact(b - 1) * lsMaxChiffre[b])
factorial = lambda n: lsFact[int(n)] if n in string.digits else lsFact[10 + ord(n) - ord('a')]
for n in count():
if n > lim: break
nStr = base(n, b)
if sum(imap(factorial, list(nStr))) == n:
ls += [nStr]
return ls
t = clock()
print factorion(int(sys.argv[1]))
print clock() - t
import time
fact_cache = {}
def fact(x):
if x not in fact_cache:
fact_cache[x] = 1 if x < 2 else x * fact(x - 1)
return fact_cache[x]
def sumFactDigits(n):
if n < 10:
return fact(n)
s = 0
while n:
q, r = divmod(n, 10)
s += sumFactDigits(r)
n = q
return s
def factorions():
n, count, res = 0, 0, []
while len(str(n)) < 8 and count < 4:
if sumFactDigits(n) == n:
res.append(n)
count += 1
n += 1
return res
t = time.clock()
print factorions()
print time.clock() - t
[1, 2, 145, 40585]
0.51060092833
Bon je crois candide sur parole
while len(str(n)) < 8 and count < 4:
Et juste une ébauche d'opti en ne calculant pas les factorielles à chaque fois.
On peut aller plus loin en mémorisant en amont.
La solution très courte et très longue en même temps :
from math import factorial as f
for k in xrange(1, 10**7):
if k== sum( f(int(c)) for c in str(k)):
print k
elle prend environ 85s au lieu de 35s pour la 1ère solution donnée par Eponix.
Autre solution, utilisant le module itertools, mais assez décevante (je n'avais jamais utilisé itertools et donc mon code est sans doute améliorable, la 2ème solution d'EPonix est plus rapide) :
from itertools import product
from math import factorial as f
N=7
it=product(range(10),repeat=N)
nb_ch=1
for i,n in enumerate(it):
if i>=10**nb_ch:
nb_ch+=1
m=n[::-1]
if sum(f(m[k])for k in range(nb_ch))==i:
print i
et qui met environs 45s.
EPonix a élargi la question de façon intéressante en recherchant les factorions en base 16.
Je me suis demandé si les sommes possibles des factorielles des chiffres étaient nombreuses (par rapport aux nombres de nombres examinés) et expérimentalement, j'ai pu me rendre compte que non, par exemple, jusqu'à un million, on en compte seulement 4014 et on en compte 8503 jusqu'à 10**7 (en proportion, c'est peu). D'où une solution par programmation dynamique (si vous ne connaissez pas, lisez le tuto de yoch) :
from math import factorial as f
b=10
N=7
prec=set([f(z) for z in range(b)])
for _ in range(N-1):
cour=set([z+f(i) for z in prec for i in range(1,b)])
prec=prec | cour
for k in prec:
if sum( f(int(c)) for c in str(k))==k:
print k
$ time python dynamique.py
1
2
145
40585
real 0m0.118s
user 0m0.092s
sys 0m0.020s
Par contre, un essai pour les factorions en base 16 ne semble pas passer, il faut peut-être déblayer le terrain mathématiquement.
EDIT
Bon, en fait ça marche sans problème, j'avais juste oublié d'adapter un peu le code à la base 16
from math import factorial as f
b=16
N=11
prec=set([f(z) for z in range(b)])
for _ in range(N-1):
cour=set([z+f(i) for z in prec for i in range(1,b)])
prec=prec | cour
ch_hex="0123456789abcdef"
hexa=dict([(c,f(ch_hex.index(c))) for c in ch_hex])
for k in prec:
if sum( hexa[c] for c in hex(k)[2:] if c != 'L')==k:
print "%x" %k
$ time python dynamique.py
1
2
260f3b66bf9
real 1m26.835s
*) Pour conclure, vous devez encore savoir qu'on peut démontrer facilement qu'un factorion peut avoir au maximum 7 chiffres.
Hum, je n'arrive pas à trouver la preuve mathématique de cela, quelqu'un peut m'expliquer?
Actuellement, j'ai: <math>\(\forall x \in \mathbb{N*}, k \in \mathbb{N} | x = \sum\limits_{k=0}^{\lfloor{log(x)}\rfloor+1} (x/(10k)\bmod(10))!\)</math>
De plus, par tests empiriques, je remarque que lorsque <math>\(\lim_{x\to{10000000^-}} \sum\limits_{k=0}^{\lfloor{log(x)}\rfloor+1} (x/(10k)\bmod(10))!\)</math> adopte un comportement asymptotique (croît de plus en plus lentement). Je suis incapable d'évaluer la limite d'une somme n'ayant pas encore été initié au calcul intégral (je termine un cours de calcul différentiel en ce moment).
Toujours est-il que ça ne me semble pas «facilement démontrable». Quelqu'un connaît-il un autre moyen de faire la preuve mathématique qu'il ne peut exister de factorion >= 10000000?
*) Pour conclure, vous devez encore savoir qu'on peut démontrer facilement qu'un factorion peut avoir au maximum 7 chiffres.
Hum, je n'arrive pas à trouver la preuve mathématique de cela, quelqu'un peut m'expliquer?
Soit x un nombre ayant "vraiment" n chiffres décimaux (ie 0004002 n'a pas 7 chiffres mais 4 vrais chiffres). Alors :
<math>\(x\geq 10^{n-1}.\)</math>
Supposons d'autre part que ce même x soit un factorion. Il est donc la somme des factorielles de ses chiffres et donc <math>\(x\leq 9!n\)</math>. D'où
<math>\(10^{n-1}\leq 9!n.\)</math>
L'exponentielle l'emporte sur la puissance donc cette inégalité se renversera définitivement pour n assez grand. Après tu cherches expérimentalement, moi j'avais calculé ça comme ça :
>>> from math import factorial as f
>>> f9=f(9)
>>> for n in range(20): n, f9*n-10**(n-1)
...
(0, -0.10000000000000001)
(1, 362879)
(2, 725750)
(3, 1088540)
(4, 1450520)
(5, 1804400)
(6, 2077280)
(7, 1540160)
(8, -7096960)
(9, -96734080)
(10, -996371200)
(11, -9996008320L)
(12, -99995645440L)
(13, -999995282560L)
(14, -9999994919680L)
(15, -99999994556800L)
(16, -999999994193920L)
(17, -9999999993831040L)
(18, -99999999993468160L)
(19, -999999999993105280L)
>>>
Tu vois que ça bascule à partir de n=8 donc un factorion a au plus 7 chiffres (si tu as des scrupules, tu passes au log et tu fais une étude de fonction).
et donc un factorion en base 16 a au plus 12 chiffres (Wikipedia et EPonix disaient 11, et c'est ce que j'ai utilisé dans ma recherche dans mon précédent message mais à mon avis, mon code passerait le cap des 12 chiffres).
Soit x un nombre ayant "vraiment" n chiffres décimaux (ie 0004002 n'a pas 7 chiffres mais 4 vrais chiffres). Alors :
<math>\(x\geq 10^{n-1}.\)</math>
Supposons d'autre part que ce même x soit un factorion. Il est donc la somme des factorielles de ses chiffres et donc <math>\(x\leq 9!n\)</math>. D'où
<math>\(10^{n-1}\leq 9!n.\)</math>
L'exponentielle l'emporte sur la puissance donc cette inégalité se renversera définitivement pour n assez grand. Après tu cherches expérimentalement, moi j'avais calculé ça comme ça :
Ah oui, en effet. Je venais de penser à quelque chose de similaire (j'utilisais plutôt <math>\(b^n > x \leq n * (b-1)!\)</math> où b est la base de x (ex. base 10) et n le nombre de chiffres significatifs dans la partie entière (soit le résultat de <math>\(\lfloor{log(x)}\rfloor + 1\)</math>.
Mais je viens de voir que la page Wikipedia en anglais donnait une preuve.
Mon code calcule en 15 secondes les factorions en base 16.
from math import factorial as f
import time
def n_max(base):
n = 1
while f(base-1)*n - base**(n-1) >= 0:
n += 1
return n-1
def factorion_suivant(a, base):
# A
t = time.time()
factorielles = [f(i) for i in range(base)]
# B
sommes = set(factorielles)
N = n_max(base)
produits = factorielles[1:]
for _ in range(N-1):
sommes |= set(s + p for s in sommes for p in produits)
# C
for s in sommes:
if s >= a:
cpy = s
res = 0
while cpy > 0:
res += factorielles[cpy % base]
cpy //= base
if res == s:
return f"dans la base {base}, le plus petit factorion supérieur ou égal à {a} est {s} " \
f"(n_max={N}, size={len(sommes)}, t={round(time.time() - t, 2)})"
return f"dans la base {base}, il n'existe pas de factorion supérieur ou égal à {a}"
Ci-dessous les résultats :
factorion_suivant(3, 14)
> 'dans la base 14, le plus petit factorion supérieur ou égal à 3 est 12973363226 (n_max=10, size=836603, t=1.63)'
factorion_suivant(1000, 16)
> 'dans la base 16, le plus petit factorion supérieur ou égal à 1000 est 2615428934649 (n_max=11, size=5762642, t=13.42)'
Dans le cadre d'un cours de L3 à l'UBS j'avais écrit ça grâce aux messages ci-dessus. Ça fait 2 ans maintenant. Je n'ai pas réussi à l'optimiser depuis. Si quelqu'un a une idée, je serais ravi de l'entendre !
Salut, Je suppose que tu sais déjà que tu as déterré un sujet vieux de 2010 et que les intervenants ne se connectent probablement plus. J'ose espérer que la modération ne m'en tiendra pas rigueur. Je veux bien essayer de t'aider à optimiser ton code. Je vais commencer par les choses simples. Je modifierai ce message jusqu'a ce que tu répondes. + le tableau factorielles: factorielles = [1] f = 1 for i in range(1, base): f *= i factorielles.append(f) Si tu fais plusieurs tests, je ferais le calcul pour la base la plus élevée et je passerais la liste à la fonction. + La fonction n_max: def n_max(base, factorielles): n = 1 f = factorielles[base-1] b = 1 while f*n - b >= 0: b *= base n += 1 return n-1 Ce n'est pas ça qui ralentit ton code, mais je le donne tout de même. Pour l'instant, je vérifie ton set sommes qui semble coûter cher à générer, mais qui sauve du temps ailleurs.
-
J'ai fait un premier test en remplaçant le set par une liste et ça devient affreusement gros et lent. J'ai eu l'idée de remplacer le set par un dictionnaire ayant comme valeurs 0 pour tout le monde. On gagne environ 10% du temps. Voici les corrections:
Re ! Je n'ai pas remarqué que c'était 10% plus rapide avec un dictionnaire... Par contre en ne faisant qu'une fonction du code je gagne 15 - 20% de perfs. Aussi, les listes en compréhension sont plus rapides que les nested loops. Enfin, je ne souhaite pas utiliser de résultats pré-calculés en amont de l'exécution du programme. Voici ma meilleure version actuelle
from math import factorial
import time
def factorion_suivant(a, base):
t = time.time()
factorielles = [factorial(i) for i in range(base)]
sommes = set(factorielles)
n = 0
while factorielles[base-1]*(n+1) - base**(n) >= 0:
n += 1
n_max = n
r = range(1, base)
for _ in range(n_max-1):
nouvelles_sommes = set()
for s in sommes:
for j in r:
nouvelles_sommes.add(s + factorielles[j])
sommes |= nouvelles_sommes
for s in sommes:
if s >= a:
s_sum = 0
temp = s
while temp:
s_sum += factorielles[temp % base]
temp //= base
if s_sum == s:
return f"dans la base {base}, le plus petit factorion supérieur ou égal à {a} est {s} " \
return f"dans la base {base}, il n'existe pas de factorion supérieur ou égal à {a}"
dans la base 10, le plus petit factorion supérieur ou égal à 146 est 40585 (n_max=7, size=8503, t=0.01)
dans la base 16, le plus petit factorion supérieur ou égal à 2615416979456 est 2615428934649 (n_max=11, size=5762642, t=8.09)
dans la base 16, le plus petit factorion supérieur ou égal à 3 est 2615428934649 (n_max=11, size=5762642, t=10.57)
dans la base 16, le plus petit factorion supérieur ou égal à 2615428934649 est 2615428934649 (n_max=11, size=5762642, t=8.02)
dans la base 10, il n'existe pas de factorion supérieur ou égal à 40586 dans la base 14, le plus petit factorion supérieur ou égal à 3 est 12973363226 (n_max=10, size=836603, t=0.86)
Je n'avais pas remarqué que mon code était affreux ...
@dtamien: je suppose que nos processeurs n'ont pas forcéement la même vitesse, mais tu le fais en combien de temps en base 10? Mon code précédent s'exécutait en environ 1.3 secondes. Si ça intéresse quelqu'un, mon nouveau code s'exécute en 9 ms seulement.
Je pourrai poster le code au besoin.
edit: le code suivant est exécuté en 7 ms sur mon ordi:
- Edité par PierrotLeFou 6 avril 2024 à 2:42:59
Le Tout est souvent plus grand que la somme de ses parties.
Je n'ai fait l'exercice que pour la base 10. Elle devrait s'adapter facilement à d'autres bases.
Dans cet exercice, je considère séparément les nombres de 2, 3, ..., 7 chiffres.
Un nombre de 2 chiffres ne peut pas contenir de 5, 6, ..., 9
Un nombre de 3 chiffres ne peut pas contenir de 7, 8, 9
Un nombre de 4 chiffres ne peut pas contenir de 8, 9
etc.
Je considère les suites descendantes et je ne vérifie les permutations possibles que quand la somme des chiffres dans la suite est égale à la somme des chiffres de la somme elle-même.
J'ai donc une suite dont les sommes diminuent continuellement.
Je commence par exemple à 655 pour un nombre de 3 chiffres (somme = 960).
Je m'arrête si la somme est trop petite (par exemple, pour 444, la somme est 72 < 100)
-
from itertools import permutations
from time import perf_counter
begin = perf_counter()
def num(T):
n = 0
for t in T:
n = n * 10 + t
return n
F = [1]
for n in range(1, 9+1):
F.append(F[-1]*n)
R = set()
x = 0
mm = 1
for p in range(2, 7+1):
mm *= 10
mx = mm * 10 - 1
t = 0
while x < 9 and F[x+1] <= mx: x += 1
q = x
N = [0] * p
for i in range(p-1, -1, -1):
while q >= 0 and t + F[q] > mx: q -= 1
if q < 0: break
N[i] = q
t += F[q]
if q < 0: continue
n = sum(F[i] for i in N)
while True:
if n < mm: break
if n == sum(F[i] for i in map(int, str(n))):
# C'est une solution possible.
# Je dois tester toutes les permutations.
# 541 et 540 donnent 145, mais aucune permutations des chiffres de 540 ne donne 145.
7x plus long que le code de PierrotLeFou , j'avais du temps cet après midi ...
f = {10:1,0:0,1:1,2:2,3:6,4:24,5:120,6:720,7:5040,8:40320,9:362880}
for a1 in range(10):
for a2 in range(a1,11):
for a3 in range(a2,11):
for a4 in range(a3,11):
for a5 in range(a4,11):
for a6 in range(a5,11):
for a7 in range(a6,11):
if sorted(str(i%10) for i in (a1,a2,a3,a4,a5,a6,a7) if i) == sorted(str(f[a1]+f[a2]+f[a3]+f[a4]+f[a5]+f[a6]+f[a7])):
print(f[a1]+f[a2]+f[a3]+f[a4]+f[a5]+f[a6]+f[a7])
- Edité par josmiley 7 avril 2024 à 19:47:55
Python c'est bon, mangez-en.
[exercice] "Factorions"
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.