Somme de factorielles

soland
soland
dans Arithmétique
Le calendrier mathématique 2019 édité par PUG(?) demande aujourd'hui de trouver le dernier chiffre de

$1!+2!+3!+ \cdots +99!$

J'aimerais bien connaître les deux premiers.
Évidemment la méthode m'intéresse plus que le résultat.

Réponses

  • Chalk
    Chalk
    A partir de $10!$ les éléments de la sommes sont tous des multiples de $10$, il n'y a plus qu'à regarder les $9$ premiers éléments, ce qui donne $3$ comme dernier chiffre.

    Edit : excusez moi, j'avais mal compris la question ...
  • nicolas.patrois
    nicolas.patrois
    C'est faisable en une ligne de Python (qui va faire hurler les puristes) :
    print(str(sum(map(lambda n:eval("*".join(map(str,range(1,n+1)))),range(1,100))))[:2])

    Le script ici.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • soland
    soland
    Moi aussi, j'ai 94...83426
  • CyD
    CyD
    Bonjour à tous,

    je vous présente mes meilleurs vœux pour cette nouvelle année 2019, je vous souhaite bonheur et la santé.

    Une petite précision sur ce qu'a écrit Skyffer3 : On a même, à partir de $5!$ les éléments de la sommes sont tous des multiples de 10.

    Cordialement,
    CyD
  • Chalk
    Chalk
    Exact, j'ai pas cherché à simplifier plus 8-)
  • GaBuZoMeu
    GaBuZoMeu
    En Sage
    In: 
    def sumfact(n) :
    S=0
    for i in range(n) :
        S=(n-i)*(S+1)
    return S

%time sumfact(99)
    Out: 
    CPU times: user 140 µs, sys: 9 µs, total: 149 µs
Wall time: 124 µs

94278623976582657916059526820683938135475434960105097434
539541040707823024959041445883011744261818073291120352020
8889371641659121356556442336528920420940313

    À comparer avec
    In : 
    %time add(factorial(i) for i in range(1,100))
    Out: 
    CPU times: user 700 µs, sys: 45 µs, total: 745 µs
Wall time: 721 µs

94278623976582657916059526820683938135475434960105097434
539541040707823024959041445883011744261818073291120352020
8889371641659121356556442336528920420940313L
  • JLT
    JLT
    Soit $x=1!+2!+\cdots+99!$. Soit $N=99!+98!$. On a $N=100\times 98!$. D'autre part, $x-N\leqslant 97!+96\times 96!=193\times 96!=\frac{193N}{100\times 98\times 97}\leqslant \frac{N}{5000}$ donc
    $$N\leqslant x\leqslant N+\frac{N}{5000}.$$

    On a par ailleurs $9.426\times 10^{153}<N< 9.427\times 10^{153}$ donc $9.42\times 10^{153}<x<9.43\times 10^{153}$.
  • Poirot
    Poirot
    Joli JLT (tu)
  • babsgueye
    babsgueye
    Salut

    Avec la méthode de @JLT, on est même sûr que le troisième chiffre est $2$ non ?
  • JLT
    JLT
    Oui (à condition bien sûr d'avoir calculé $N$, ou du moins une approximation assez bonne de $N$).
  • GaBuZoMeu
    GaBuZoMeu
    Calculer la somme des factorielles jusqu'à $99!$ ne demande pas plus de multiplications que de calculer $99!$ (à savoir, $98$ multiplications).
    On peut gagner dans le calcul de $99!$ en équilibrant la taille des nombres qu'on multiplie.
  • JLT
    JLT
    D'accord, mais j'imagine qu'avec des formules de type Stirling on peut obtenir de bons encadrements de $N!$ qui sont moins coûteux que le calcul exact.
  • nicolas.patrois
    nicolas.patrois
    Ça dépend, le calcul de l’exponentielle est coûteux comment ?
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • JLT
    JLT
    En gros, on veut trouver 3 chiffres significatifs de $n!$, donc on veut calculer $\ln(n!)$ avec une précision de $10^{-3}$.
    Si on se contente de Stirling, par exemple pour $n=10^6$, il faut calculer $(n+\frac{1}{2})\ln(n)-n+\frac{1}{2}\ln 2\simeq 12815518.3847$ avec
    environ 3 chiffres après la virgule. En revanche, le calcul exact de $n!$ demande un million de multiplications, et la plupart des multiplications utilisent un nombre ayant des millions de chiffres, ça me paraît plus coûteux.
  • babsgueye
    babsgueye
    Oui @JLT, on a $N\leq x\leq N\times 1,0002$. Avec l'encadrement que tu as de $N$, ça marche très bien.
  • soland
    soland
    Ouf ! Enfin une preuve (JLT) suivie d'une discussion.
    Merci à tous.
  • gerard0
    gerard0
    Bonjour Soland.

    Tu n'as pas dit ce que tu voulais. Comme un logiciel de calcul formel donne tous les chiffres en une fraction de seconde (et même la somme jusqu'à 999 en moins d'une seconde sur mon vieux Maple), la méthode "utiliser un programme de calcul exact" est la plus simple. Et pas besoin de "preuve".
    Si c'est calculer à la main, c'est très long ! Et l'utilisation de logs demande une table de logarithmes dont tu n'as rien dit.

    Cordialement.

    NB : je m'étais abstenu de répondre "calcul formel", espérant de ta part une clarification. J'attends toujours.
  • soland
    soland
    A ceux qui combattent l'ambiguïté, dont je suis.

    Un énoncé ne peut être parfait car définir les termes de toutes les définitions conduit à l'absurde.
    Un idéal est inatteignable; il ne faut pas lui tourner le dos pour autant.

    Un bon énoncé de problème est un énoncé ouvert.
    Il fait réfléchir et réagir : les chercheurs, les trouveurs, les prouveurs.

    Un tel énoncé n'a pas de réponse univoque, il est plein de surgeons.
    Comme toujours ce qui est trop contraint meurt.
    Ce qui ne l'est pas assez prolifère en chaos et meurt aussi.
    L'essentiel est que les gens réfléchissent et participent.

    Si vous cherchez que chose vous trouverez peut-être cette chose.
    Si vous cherchez sans but trop précis, vous avez une chance de trouver ce que vous ne cherchez pas.

    P.S.
    "Calcul formel." Vous laisserez-vous limiter par overflow ?
    Qui a programmé les algorithmes ? Qui les a implantés ?
    Y a-t-il des failles dans ma puce ? Que faire pour ne pas croire aveuglément ?
    Puis-je faire mieux que la machine (Mathematica)?

    Fin du prêchi-prêcha.
  • Al-Kashi
    Al-Kashi
    Soland dans tous ses états :-D

    Al-Kashi
  • gerard0
    gerard0
    Soland,

    je ne demandais pas un énoncé parfait, seulement ce qui t'intéresse. Finalement, ce que tu fais est de poser une question floue et d'attendre que d'autres s'investissent. Sans réagir vraiment, comme si ça ne t'intéressait pas, comme si la question ne venait pas de toi. Drôle de conception !! Finalement, les jeux de mots en moins, c'est du Samok.

    Pour ma part, je n'ai pas grand chose à dire de plus que ma confiance dans les algorithmes de calcul formel, bien plus vérifiés que l'explication de JLT (qui ne donne pas le résultat, lui). Et mon refus du snobisme "sans ordinateur c'est mieux".

    Cordialement.
  • JLT
    JLT
    Soit $n=10^9$. En prenant la formule de Stirling pour approximation de $n!$
    n:=10^9;a:=(n+.5)*log(n)-n+.5*log(2*Pi);b:=e^(a-floor(a/log(10))*log(10));

    je trouve $b\simeq 9.904626578$ donc les premiers chiffres de $n^ne^{-n}\sqrt{2\pi n}$ sont $9904$. Les autres termes (l'erreur dans la formule de Stirling ainsi que les termes $1!+2!+\cdots+(n-1)!$) sont de l'ordre de $n!/n$ donc ne perturbent pas ces chiffres. J'en déduis que les deux premiers chiffres de $1!+2!+\cdots+(10^9)!$ sont $99$.

    Si on veut calculer de manière exacte $1!+2!+\cdots+(10^9)!$ avec un logiciel de calcul formel, je crains que ce soit très long avec un ordinateur de bureau.
  • GaBuZoMeu
    GaBuZoMeu
    Entièrement d'accord, JLT.

    Mes remarques concernaient essentiellement l'approche de Soland dans ce message. Il semblait penser faire des économies en ne calculant (exactement) que la somme des plus gros termes $99!+98!+97!+96!$ par rapport au calcul (toujours exact) de la somme complète des factorielles.
  • soland
    soland
    Snobisme, diantre... du Samok, fichtre...

    Un point, quand même :
    > ce que tu fais est de poser une question floue...
    Pour mémoire, la voici :
    > J'aimerais bien connaître les deux premiers [chiffres de la somme $1! + ... +99!$]
    Où est le flou ?

    Quant à la façon de réagir des intervenants, je n'avais aucune attente particulière.
    J'espère que quelques-uns se sont bien amusés, c'est là toute mon ambition.
    Si j'ai choqué quelqu'un, je le prie de m'excuser.
    Depuis que je suis retraité, j'ai perdu mes outils de gravure sur marbre.

    Mon salut à tous (en général) et à Samok (en particulier).
  • gerard0
    gerard0
    JLT,

    d'accord avec ce que tu dis pour la somme des factorielles jusqu'à 109; les logiciels de calcul exact ont des limites. Mais le calcul initial était jusqu'à 99. Et la formule de Stirling est d'autant plus efficace que les factorielles sont grandes.

    Donc d'accord avec ta méthode, pour une très grande somme. Pour la somme jusqu'à 20000, j'obtiens (en calculant seulement le dernier terme et contrôlant que les précédents ne changeront pas les premiers chiffres, donc qu'il n'y a pas une série de 9 vers le cinquième chiffre) 181 pour les 3 premiers chiffres (2 s de calcul sur un ordinateur de bureau, 1 s de vérification visuelle).

    Cordialement.
  • GaBuZoMeu
    GaBuZoMeu
    Bah, le calcul complet de la somme de factorielles jusqu'à 20000!, avec la petite procédure écrite plus haut :

    CPU times: user 127 ms, sys: 8.01 ms, total: 135 ms
    Wall time: 130 ms

    18192972850948273110990300775251908740458036422101351921
    389799688241368571250569358911141504282889209887778838791
    04270242334502510909738056764301501313556457379826900877
    67976737937646614101754617598578548151140579983386064526
    17001572689247637838213811344900313184879806641588029007
    68783640430398315311677691531478149051059733512751806550
    48805489478241031632661910238662299419809587223684709006
    01565973262509688843675795771968972896585551471207000337
    40906465068517655505089690016099025506719001427495575047
    96836513912279802030425175434961729993869090384783904365
    546634954324513470143361915409408539167705091115090342602
    30654849997397003941610685307394880400460654367797296266
    49304567634363955830694120878192163906602134349205474849
    62299746719851069720226353146538171567770157383418256947
    08671275781210271408437961642639222013968053367795023753
    62656635643129455109541519422698274602389107384285150394
    40480505205994620151778618092557154415002104525202745854
    07076984955397815953387123341159059321428690567078164109
    71498366628452574659559231742557678201671516786150529233
    78046534553899532513841679516787666396015109616686369227
    60832848265831867352703961479424351245188423155706732148
    52577566921021731346011228057507363536793718889221793917
    03158900172808892628857559946474744027253906185902937629
    22033754778514050503267204594871443875514248835176164684
    81672383855398340663319799469737944553300553946945473592
    22729960669975712713109153772871279746733170327447651522
    46277543122714167314198595196160172135681940358706279951
    62936537944358322618052274964762295107800404393941393453
    85221026642784740772838075024006779834172279002320078580
    939942199061108157848753466482218527813575211484834706923
    05037304939055533096267872316352759621493008826503564083
    401311137762275117878354109219003916073653986461856856788
    78313119686582941815816863540607267875461059781805799082
    93421694857354708993392687675229235323287641673788016852
    10652288830348979132704654940839178961620127761230084031
    67064103129527391738394214131888698128762845692843555145
    73567455280563460087347139575995240530076107455526388930
    66980918184604824191144798300120752044068752120247731986
    59370280569640374132317539399464960173217692142154179452
    83470604644167381191789994786778501855549052174887897374
    05259822049033035724893516627172130186353855296193919675
    469655239921071116749763999901821634197115465927443200754
    61680535534254271736609837590425058131374645441181373759
    30196477931554758962925394780566753402509200436201286834
    61427835942677355518877927655401407889191848384992154106
    36344720421817353911505964501025259495333261975130243550
    98512043782228081673063085648760319661202795414829956390
    30162505630578944077306995770113568397174264981547199598
    77151133825221624726726900409252451879230783606923630682
    50194654909440804690668002468133383944528154177889924346
    77365353778317934758170573618188430263996326311748000018
    70228709998476882646852888292028506483723062280187686446
    086148397711180311456399567627445252673156986587581857784
    00548502772392835846965450394977534760837054100349892587
    51859575914428379508197741402456382868721491077748360917
    80238890815045114601431779147448814298438010054779050048
    659305899283431966233111656264200305420383952054364767505
    68669052177220486512248168891549589681439281346962401643
    04099147756377856837799888366010159425548574158480619393
    89054888806829810271050495499922728643572118097220281402
    275777057308868645748459115532315153118710405863963190984
    20612900198789473494772998846531870482281181514395659703
    06797448319862769963498884643249883085585404718295342641
    86498487312386664819419776828218222659224311043591950751
    66008438377708649203677646551588786778165146148803287704
    19319246423487116550408922769545338842287908414819959507
    54909759191333863715512592934277705141481270963301199077
    96639130024005665578606711702064383969429928907135537083
    37907013986601572097702605832863443189687467379711332010
    831186501509209343639159127811765177690852370322101419852
    44482653705883704413692129123655389093057872150329857406
    44001460915366083215032942380016464536666505210916908952
    02686329339560753177543584490422651792662764581021008585
    81186226479781798561948817400959986621910357549219217538
    37648463647681073962464391840337910502301020740737567066
    73658425087258058328197995596112558109763453582806908213
    59087398744167133025750794415559463344871574404539013702
    35009148504282520293274843620936283758007702368436183092
    104804760360391097236514115658530066624422626146781103814
    23984281480159126072875706475260413869205082281864167209
    321652318111985580369761761838069133436985317930374390051
    72925027094480962484904944358851464635139976531304330546
    79988380461809336818368008012106890420490771965370757461
    54370460296740637584591583507233721884945658576808742343
    96226084452310410025020715724091122916213091368343467675
    22752891747565418841718880771784231969358770050925017159
    31583507148474084186311535780755916178750556896689591691
    05395558911614584262229219074256097203616127004302849882
    85615787520683152350143967444505048057354268161070229219
    73398531547464596821229605948649794252390825837406745232
    284117358888177453518776601972430344897670086122011207972
    87286531984683916023628667993755406083332435777955602456
    716377476968258744601566543861113755901070408777146872368
    64123727490746411576085093105268518396063980932216049793
    16238890333657126536395018259552645759485199196739300632
    48217982874615501941795700168385387389583199605521147618
    00825247521634642885409170256242341753887865299481722949
    483222200440370732220840732111070148209939376526128394079
    38334799513678079936387667761592981340327443422156422793
    446684827777855217894304511208805588616625601086637765118
    25892213285483385562199278372959077469849640487474568886
    43075571333094367526445915974424426620398632191887053846
    43655240585693320431653794051701378455721034444762907819
    12870318562297222497980289477796104842092404881657687869
    825483915824096736539763769813390962931633894156951110310
    17801756289249942918544592084641100836998124925607919260
    271118767813375592225800269613203134724119822501808725104
    143027136241590268443511391983043881193163766148414445759
    84932100920119225879495840427468660220965536097778197697
    59624825683457469677168156049128065506453391786595417782
    85084959602886289006283630180962903977421505868392118139
    01626895626913786772540555716866655287964465195245303604
    29284623324394057227908253335693289142909694315599225458
    64686593466519006096031158579501266627952240038097285864
    06665307068807881007093351513283298848597494225672929648
    04380389523728434681826349724391337106653098902787091434
    03674720465112928731809389922493327894760734425543304321
    00024258049409786706582563235549650798299927626900375193
    783714413166092409001789171660893040016466768786426286111
    85703418003358499276184523019077204956792429987845915009
    593112219445746708117339456847459687266682264976136844012
    23402369968698410214654645907964518755625489739559240002
    15559724268736625138459090660218758701071237690990886808
    23420759156153744538624945427043742648570363638580584002
    60428856733198693518657335168678974180505950592238821721
    09856937440992526582040304768527775411742269892255494514
    35621105640104275514979736849855492521224499530539043156
    91744854671800979346229807596230713335079271459654978413
    031129329499432607501182576766407452164715385168108764843
    12939726228944597962148032230126954500147397335775894238
    12735477198463301703700223365490858793921962189183875422
    63108373757900739054406531626689015144746238834149267682
    73825788358325587788694382453303172903255800497110097471
    87650371814333259375418503869714449418926762077431602813
    58648533140487683987577206985429961875428546588647287796
    98695162388872210967460688383957450434435162145093280640
    03587670400957201882027984846388767100726232354754517527
    56198018520953071319943065845227808641972336888832869639
    26557827821594954298760631018066588438086030398274260831
    15558463201039452944477938002859828617190539318235292618
    84517733911364032661851498862465735185075698639121344607
    33636953969266278105182012400722930472392517607043658951
    36597049849312798023762582097249679564060226242304778623
    61077033724526484365506677720736441208291248839546650773
    816843819628916681709505813116449404455984529241505286211
    60909675931348616420100245899180156474994223740144357161
    86360601080935690848541739420966390507229622561204367765
    12489522315722710442694025354036370932698108212625739335
    844111648547819436561244904739868824931348697789835997339
    05659503952035554909350085668357320070481160270849596516
    47720519515092543105904408294382394596698450704928734866
    25689807153301533328836679279657334665208388383230790550
    06968264089008646893698924011058383529208692861844126382
    681847810753977261117042653065343647277026850791860921617
    35711246726942254343388790378308543377255843792574256593
    37038237625547808988185780867402986626571202790243328968
    21339549441233159052392443543161711582457615554309180723
    85601643832049935106202776615615062674593380020355775475
    62864467953933091348149749966989370202221214426362592855
    03678530125819763725170853730655520848930263314357708874
    666348626277563117574728907218868911170065177301018550195
    12117057701337764236672871508943286314430256882927949545
    33837687413893242881368052084930318346837371704732756107
    46338780983165432551338932580584046743474249168419178143
    30896540181808508484721626077731066586725341892032245498
    92390444395351074946747063404146133009290453978711288824
    95347528856050980461248609886686587177327969554436753799
    26494395170209371799916706184296814494484016031497076636
    49824512562363057116489318193709156227720347109435878397
    60013970025755691618578378457129579750126259979751394708
    652128450141163400824044291144193854380933584342779021722
    04164133433465567287760555990411768849543142368299430551
    95796680492432956995854483468207440586543500089241081373
    39066443047667503520646118245269714850336249727004360658
    67450586209469312235276264214114922590088142264579475285
    94721068270034103099580187625351826594182761014788276577
    30252778105543399801659082064959817620976426190043264258
    84186135771010221861014786070076102060440867245180112909
    75440349422131356858140730724128752925153075737263185489
    72192207171808067424011528025462070968746491629730051225
    32358042208193988110937676942608128017434494661260133465
    28170309864216300487914227097097607299943421120051771990
    49066788978039922440219444669944237666694260094168401941
    33206486146380674994662376859187323876790582488990408760
    54895082488470283862235533511886837681297974137336660521
    05603042569219677496788595829945335732006112212079922643
    76846144730690262076557084185266169868270833950714003560
    83950047059098085725197049940218288250485394533519950490
    58458575988969129088109985671526749045805833933979671147
    54434179283104457544039841207274916364636901809276402176
    25243908701805569793001426627842137029943446635207695771
    00523208089783969450614850173088322831898088796808171848
    81350009906175818906080435998058974541454586253495490446
    43453463007801192858138236726632315435619341212346616866
    03729696873915206808724139248696209324829762225731255717
    90522352780592496684244716124124361217062781975338719487
    02891176475760761950855277787669218449562929533453590015
    99533202891471019225168768292004263912947162156339591490
    65910145840162535678618512881120579912259534803527718789
    25474617323119739108252903438276342002367949598809879199
    84148779244809178556345628831426798410472748315905715806
    77817769448218077572446108507863872122490352048975720532
    93034509314916400498324211374595021759414461349330013254
    257650640661021124598189161984170699559171172527774578616
    27493680332034889936834572336527803913019279771628415856
    21513664830682899665936962625789569136082968809786607172
    53175100886342834068417179949026567866308431794563047398
    75726792777550905723761411617992235560970744725222813250
    47732005516429752774841884396019449532269407238563928502
    67311562458264797702822488807716015975409592526098788723
    10433554545573229179018960262097239220715623460942999679
    63202620023744843001439248604181650776349479310740040865
    87343521726042464418419424739541997450913398324336693609
    36026152072471378561051273855267715358454867632160986231
    etc.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 28

AmadouBibixCidrolinCongruCyranoabcdeoghanmtho5vlad69 +19 Invités