Long, long zeroes

Number Theory Level 2

Find the number of trailing zeroes in 78 ! 78! .

Details

  • 78 ! 78! is 78 factorial.


The answer is 18.

Adam Phúc Nguyễn by Adam Phúc Nguyễn , 20, Vietnam

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Vishnu Bhagyanath
Aug 23, 2015

In the factorization of 78 ! 78! there would be 15 15 multiples of 5 5 . Namely 5 , 10 ⋯ 75 5,10 \cdots 75 . But of these, there are 3 3 which have an extra 5 5 in their prime factorization which are 25 , 50 , 75 25,50,75 . And since there are certainly more 2 2 in the prime factorization of 78 ! 78! , each 5 5 multiplied with 2 2 would produce a trailing zero, or a power of 10. Therefore, 78 ! 78! can be written as s o m e t h i n g × 1 0 ( 15 + 3 ) something\times 10^{(15+3)} . So in total, there would be 18 18 trailing zeros.

4 Helpful 0 Interesting 0 Brilliant 0 Confused

Challenge Master Note: This is correct. +1

Pi Han Goh - 5 years, 9 months ago

f ( 78 ) = ⌊ 78 5 ⌋ + ⌊ 78 5 2 ⌋ + … = 15 + 3 = 18 f(78)=\left\lfloor{\frac{78}{5}}\right\rfloor + \left\lfloor{\frac{78}{5^2}}\right\rfloor+\ldots= 15+3=\boxed{18}

2 Helpful 0 Interesting 0 Brilliant 0 Confused

Did the same way.

Niranjan Khanderia - 5 years, 9 months ago

It's better to explain why you stop at 5^2. And why your formula works in the first place.

Pi Han Goh - 5 years, 9 months ago 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 
# Lazy mode
def legendre(n):
    i = 5
    ans = 0
    while i <= n:
        ans += (n/i)
        i *= 5
    return ans

print legendre(78)    # 18

1 Helpful 0 Interesting 0 Brilliant 0 Confused

This is beautiful.

Alan Yan - 5 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...