Path: ...!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!cleanfeed2-b.proxad.net!nnrp4-1.free.fr!not-for-mail
Date: Thu, 16 Mar 2023 17:37:25 +0100
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.8.0
Subject: Re: 0!=1 ?
Newsgroups: fr.sci.maths
References: <turdrh$naru$1@dont-email.me>
Content-Language: fr
From: Michel Talon <talon@niobe.lpthe.jussieu.fr>
In-Reply-To: <turdrh$naru$1@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Lines: 72
Message-ID: <641345c5$0$22266$426a74cc@news.free.fr>
Organization: Guest of ProXad - France
NNTP-Posting-Date: 16 Mar 2023 17:37:25 CET
NNTP-Posting-Host: 88.161.173.7
X-Trace: 1678984645 news-1.free.fr 22266 88.161.173.7:28122
X-Complaints-To: abuse@proxad.net
Bytes: 3376

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