Benadering aantal nullen in faculteit

Hoi iedereen,

Er is mij laatst iets opgevallen
Als a! (a faculteit) uitgeschreven wordt dan blijkt dat voor a waarden groter dan 4 het getal een aantal nullen op het einde heeft.

Ik heb opgemerkt dat als men (voor grote a's) a deelt door 4, men een vrij goede benadering krijgt van het aantal nullen op het einde van het getal.

Iemand een idee hoe dit komt?

Kevin
Beantwoorder - dinsdag 4 maart 2008

Antwoord

Hey Kevin,
Goeie observatie, ze blijkt inderdaad te kloppen.

Een nul achteraan wijst natuurlijk op deelbaarheid door 10, dit wil zeggen deelbaarheid door zowel 2 als 5. De factor die het minst vaak voorkomt van die twee, bepaalt het aantal nullen: een getal dat 7 keer de factor 2 en 3 keer de factor 5 bevat, zal slechts deelbaar zijn door 10³, dus eindigen op drie nullen.

Voor a! moet je dus gaan tellen hoe vaak de factoren 2 en 5 voorkomen. Aangezien 25, zal de factor 2 veel vaker voorkomen. We moeten dus enkel nog tellen hoe vaak de factor 5 voorkomt.

Als a5 heb je geen enkele factor 5. Dan, bij a=5, pik je één factor 5 op. Die hou je tot a=9. Bij a=10 komt er weer een factor 5 bij, enzovoort. Je merkt dat je telkens floor(a/5) factoren 5 krijgt. Die floor betekent: naar beneden afronden. Ga maar na! Bij a=0 tot 4 krijg je geen factoren 5; bij a=5 tot 9 juist 1; bij a=10 tot 14 juist 2, enzovoort.

Hier zit wel nog een fout in: namelijk de getallen die hogere machten van 5 bevatten. Bijvoorbeeld, bij a=24 heb je 4 factoren 5 in 4! zitten, als je naar a=25 gaat, komen er ineens twee bij, terwijl je er volgens de formule maar één telt! Hetzelfde bij 50, 75,...

Vandaar nog een extra term floor(a/25). En dan vergeten we de derdemachten, op dezelfde manier geven die aanleiding tot een extra term floor(a/125), en dat gaat zo maar door.

Conclusie:
a! eindigt op floor(a/5)+floor(a/25)+floor(a/125)+floor(a/625)+... nullen. Dit resultaat is exact. Er staat wel een oneindige som op die puntjes, maar je krijgt maar een eindig aantal niet-nul termen: bijvoorbeeld als a=10000 krijg je
floor(a/5)+floor(a/25)+floor(a/125)+floor(a/625)+floor(a/3125) want de volgende termen, te starten bij floor(a/15625), zijn allemaal nul.

Wat geeft dat voor grote a? We nemen dan de limiet voor a naar oneindig. In de limiet zal dat floor-gedoe niet veel uitmaken, ons aantal nullen wordt dan
a/5+a/25+a/125+...
=a/5*(1+1/5+1/25+1/125+1/625+...)
=(a/5)/(1-1/5) wegens de somformule van een meetkundige reeks
=a/4.

Dus inderdaad, je getal a gedeeld door het aantal nullen waarop a! eindigt, gaat voor grote a naar de waarde a/(a/4) = 4.

In het algemeen zal voor elk priemgetal p iets gelijkaardigs gelden als wat hier gebeurt voor p=5: het getal a gedeeld door het aantal factoren p in het getal a!, zal voor grote a gaan naar de waarde p-1.

Toffe vraag!

Christophe
dinsdag 4 maart 2008

©2001-2024 WisFaq