Programmer fakultet og forklar nuller i 100!

Programmer fakultet og forklar nuller i 100!

n!n! leses som «nn fakultet» og er produktet av de naturlige tallene fra og med 1 til og med nn. Se eksemplene nedenfor.

1!=12!=123!=1234!=12345!=12345\begin{aligned} 1! &= 1 \\ 2! &= 1 \cdot 2 \\ 3! &= 1 \cdot 2 \cdot 3 \\ 4! &= 1 \cdot 2 \cdot 3 \cdot 4 \\ 5! &= 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \\ &\ldots \end{aligned}

Lag et program som kan regne ut n!n! for et gitt naturlig tall nn. Bruk programmet til å regne ut 5!5!, 10!10! og 15!15!.

100!100! er et produkt av 100 faktorer, 1234991001 \cdot 2 \cdot 3 \cdot 4 \cdot \ldots \cdot 99 \cdot 100.

Gjør rede for hvilke faktorer som gjør at det er 24 nuller i slutten av tallet 100!100!.

Fasit

Se program under. 5!=1205! = 120, 10!=362880010! = 3\,628\,800, 15!=130767436800015! = 1\,307\,674\,368\,000.

24\underline{\underline{24}} sluttende nuller i 100!100!

LøsningsforslagKI-generert

Vi lager en funksjon fakultet(n) som starter med f=1f = 1 og multipliserer med hvert tall fra 1 til og med nn i en løkke:

def fakultet(n):
    f = 1
    for i in range(1, n + 1):
        f = f * i
    return f

print(fakultet(5))   # 120
print(fakultet(10))  # 3628800
print(fakultet(15))  # 1307674368000

Programmet gir

5!=120,10!=3628800,15!=1307674368000.5! = \underline{\underline{120}}, \qquad 10! = \underline{\underline{3\,628\,800}}, \qquad 15! = \underline{\underline{1\,307\,674\,368\,000}}.

En sluttende null oppstår fordi 10=2510 = 2 \cdot 5. Antall sluttende nuller i 100!100! er derfor lik antall ganger vi kan skrive 1010 som en faktor i produktet 1231001 \cdot 2 \cdot 3 \cdot \ldots \cdot 100, det vil si min(antall faktorer 2, antall faktorer 5)\min(\text{antall faktorer 2},\ \text{antall faktorer 5}).

Faktorer 2 forekommer langt oftere enn faktorer 5 (hvert partall bidrar med minst én faktor 2), så det avgjørende er antall faktorer 5.

Vi teller faktorer 5 i 100!100! ved å se hvilke tall som bidrar:

  • Multipler av 55 (gir minst én faktor 5 hver): 1005=20\left\lfloor \dfrac{100}{5} \right\rfloor = 20 stykker.
  • Multipler av 25=5225 = 5^2 (gir én ekstra faktor 5 hver): 10025=4\left\lfloor \dfrac{100}{25} \right\rfloor = 4 stykker.
  • Multipler av 125=53125 = 5^3: 100125=0\left\lfloor \dfrac{100}{125} \right\rfloor = 0 stykker.

Totalt antall faktorer 5:

20+4=24.20 + 4 = 24.

Siden det er minst 24 faktorer 2 (faktisk mange flere), kan vi danne nøyaktig 2424 par (25)=10(2 \cdot 5) = 10.

100!100! har derfor 24\underline{\underline{24}} sluttende nuller.

Sensorveiledning

Et delvis riktig program kan gi 1 poeng.

En kandidat som finner noen riktige faktorer og gjør rede for disse, kan få 1 poeng.