Re: 0!=1 ?

Le 15/03/2023 à 04:25, Dominique a écrit :

 Ma question vient d'une petite énigme Python, notamment trouver deux nombres dont la somme de la factorielle de tous ses chiffres était égal à ces nombres.

En fait on peut voir que les *seuls* nombres pour lesquels on a cette propriété sont 1, 2, 145, 40585.
En effet si n est grand, avec m chiffres, la somme des factorielles est au plus m*9! tandis que le nombre est au moins 10^m -1. Donc le nombre
grandit plus vite avec m que la somme des factorielles. Raffinant un peu, le calcul suivant montre que pour pour n > 3 millions on ne peut avoir égalité:
  float((2!+6*9!)/(2*10^6));  --> 1.088641
  float((3!+6*9!)/(3*10^6));  --> 0.725762
Il suffit donc de chercher tous les cas d'égalité entre 1 et  3000000.
Comme c'est assez long, j'ai arrangé un peu le programme maxima pour aller plus vite.
- je remplace la fonction n! par une fonction "memoizing" qui garde la mémoire pour éviter de recalculer sans arrêt de 0! à 9!
Ca fait gagner un peu mais pas beaucoup.
fact[n] := n! $
- je compile la fonction gfact. Pour ce faire je la remplace par:
gfact(n) :=
block([m : n, mm : 0, fsum : 0],
   mode_declare([m,n,mm,fsum],fixnum),
   mm:floor(m/10),
   while(mm > 0) do (fsum:fsum+fact[m-10*mm],
     m:mm,mm:floor(m/10)),
   fsum:fsum+fact[m-10*mm])$
mode_declare([gfact(n),fact(n)],fixnum);
  compile(gfact);
warning: variable mm (declared type fixnum) assigned type any.
warning: variable m (declared type fixnum) assigned type any.                     [gfact]
Comme on peut le voir le compilateur ne tire pas bien parti des déclarations, mais on gagne quand même un facteur 10 sur le temps.
On se retrouve avec à peu prés le même temps que python.
for n from 1 thru 3000000 do if (n=gfact(n)) then print(n) $
1
2
145
40585
(%i32) time(%);
(%o32)                             [44.804]
soit 45s.
Le compilateur maxima convertit une partie des constructions maxima en lisp, ce qui fait qu'on ne passe pas sans arrêt dans l'interprète de maxima. Si les déclarations étaient satisfaisantes pour lisp, le compilateur lisp donnerait du code machine environ 100 fois plus rapide que  du python, mais en partant de maxima ce ne peut être le cas (notamment parce que toutes les variables maxima sont "dynamiques" globales, ce qui empêche les bonnes optimizations par lisp).
--
Michel Talon