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]

Advertisements

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[1]))
    
    # 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
        

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: