# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1193: 1,000,000!

From New Scientist #2349, 29th June 2002 [link]

George has been explaining to his young son the concept of factorials, which are denoted by an exclamation mark. The factorial of three, denoted 3!, is 1 × 2 × 3 = 6. The factorial of 10 (10!) is 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 = 3,628,800.

“In that case, Dad, the factorial of one million (1,000,000!) must be a very large number.”

“Indeed so — it has more than five million digits, ending with a long string of zeros.”

How many zeros?

This Enigma appeared in the styling that was used for the remainder of Enigma puzzles, up to December 2013.

[enigma1193]

### 4 responses to “Enigma 1193: 1,000,000!”

1. Jim Randell 16 November 2015 at 7:28 am

The number of zeros depends on the number of times 5 appears as a factor (as there are always enough 2 factors to multiply it up to 10).

This Python program counts the number of factors that are various powers of 5.

For 1000000! it calculates the result in 31ms.

```from enigma import printf

import sys
N = (1000000 if len(sys.argv) < 2 else int(sys.argv))

# count the number of factors of f in factorial(N)
def count(N, f):
# consider increasing powers of f
(n, p) = (0, f)
while not(p > N):
t = N // p
n += t
p *= f
return n

n = count(N, 5)
printf("factorial({N}) ends with {n} zeros")
```

Solution: The decimal representation of 1,000,000! ends in 249,998 zeros.

2. Naim Uygun 16 November 2015 at 11:58 am
```p=1 #power of five
n=10**6 #number before  !
a=list()
while(1):
q,r=divmod(n,5**p)
if q<1: break
p += 1 #increase the power of 5
a.append(q)
print("There are ",sum(a)," zeros in ",n,"!")
```
• geoffrounce 18 November 2015 at 12:11 pm

A manual solution:

```Find all divisors of 5 to find number of divisors of 10.
There are 1,000,000 ÷ 5 = 200,000 multiples of 5 between 1 and 1,000,000.
The next power of 5, namely 25, has 1,000,000 ÷ 25 = 40,000 multiples between 1 and 1,000,000 (ie 40,000 extra 5's)

This process continues as shown, until the division by 5 is less than 1:

1,000,000 ÷ 5 = 200,000 so 200,000 factors of 5
1,000,000 ÷ 25 = 40,000, so 40,000 more factors of 5
1,000,000 ÷ 125 = 8,000, so 8,000 more factors of 5
1,000,000 ÷ 625 = 1,600, so 1,600 more factors of 5
1,000,000 ÷ 3125 = 320, so 320 more factors of 5
1,000,000 ÷ 15625 = 64, so 64 more factors of 5
1,000,000 ÷ (15625 * 5) = 12.8, so 12 more factors of 5
1,000,000 ÷ (15625 * 25) = 2.56, so 2 more factors of 5
Next division:
1,000,000 ÷ (15625 * 125) = 0.512, which is less than 1, so no more factors of 5.

Number of trailing zeros in factorial (1,000,000) is :

200,000
40,000
8,000
1,600
320
64
12
2
-------
249,998
-------
```
• geoffrounce 19 November 2015 at 11:25 am

The above analysis leads to a one line Python solution :

```print(sum(list(1000000//5**d for d in range(1,9))))       #  Ans = 249998
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.