Enigmatic Code

Programming Enigma Puzzles

Enigma 1226: Megafactors

From New Scientist #2382, 15th February 2003 [link]

George’s son has listed all the factors of the first few dozen numbers.

“Dad – the number 48 has exactly ten factors, 1, 2, 3, 4, 6, 8, 12, 16, 24 and 48. I reckon it is the smallest number with exactly ten factors.”

“Quite right, son. Now can you find the smallest number which has exactly one thousand factors, including itself and 1?”

“Er, yes, I think so. It is …”

“I won’t ask you to calculate the smallest number with exactly one million factors, but can you tell me how many different prime factors it has?”

“Hmm…”

Can you answer both of George’s questions?

[enigma1226]

Advertisements

3 responses to “Enigma 1226: Megafactors

  1. Jim Randell 12 June 2015 at 8:11 am

    Instead of a brute force approach (which will take a long time to reach the large numbers required in the solutions), we do a bit of analysis which gives some straightforward code, that can be used to find the smallest number with any specified number of divisors. This Python program runs in 134ms.

    # if we consider a number by its prime factorisation:
    #
    # n = p1^n1 x p2^n2 x p3^n3 x ...
    #
    # then the number of different divisors can be calculated by selecting
    # some subset of the factors, so: 0 to n1 times p1, 0 to n2 times p2, etc.
    # giving a total number of divisors of:
    #
    # N = divisors(n) = (n1 + 1)(n2 + 1)(n3 + 1)...
    #
    # so given a factorisation of N we can determine a family of numbers with
    # exactly N divisors.
    #
    # e.g.:
    #
    # N = 10 = 2 x 5 = (n1 + 1) x (n2 + 1)
    #
    # n1 = 1, n2 = 4
    #
    # so any number n = p1^1 x p2^4 will have exactly 10 divisors.
    #
    # and the smallest such number is 2^4 x 3^1 = 48.
    #
    # but we must consider the different factorisations for N in order to
    # find the smallest n, for example:
    #
    # N = 24 = 2 x 2 x 2 x 3
    # => n = 420
    #
    # N = 24 = 2 x 3 x 4
    # => n = 360
    
    from enigma import factor, is_prime, divisors, printf
    
    # we're not dealing with very large primes, so we can just use
    # is_prime() and cache the results
    
    class Primes(object):
    
      cache = [2, 3]
    
      def generate(self):
        # generate cached primes
        for p in Primes.cache:
          yield p
        # and then add to the cache
        while True:
          p += 2
          if is_prime(p):
            Primes.cache.append(p)
            yield p
    
    
    # factorisations of n
    def factorisations(n, m=2):
      if n == 1:
        yield []
      elif n < 4 and not(n < m):
        yield [n]
      else:
        for a in divisors(n):
          if a < m: continue
          for fs in factorisations(n // a, a):
            yield [a] + fs
    
    
    def solve(N):
      m = None
      # factorisations of N
      for fs in factorisations(N):
        # compute minimal n
        n = 1
        primes = Primes().generate()
        for f in fs[::-1]:
          p = next(primes)
          n *= p ** (f - 1)
        # number of prime factors
        if m is None or n < m[0]: m = (n, len(fs))
      printf("n={m[0]} has {N} divisors, {m[1]} prime factors")
    
    import sys
    Ns = ([10, 1000, 1000000] if len(sys.argv) < 2 else map(int, sys.argv[1:]))
    for N in Ns:
      solve(N)
    

    Solution: The smallest number with one thousand divisors is 810,810,000. The smallest number with one million divisors has 11 different prime factors.

    The smallest number with one million divisors is:

    173,804,636,288,811,640,432,320,000 = (2^9)(3^4)(5^4)(7^4)(11^4)(13^4)(17)(19)(23)(29)(31).

    Using int2words() from the enigma.py library gives (using short scale notation):

    one hundred and seventy three septillion, eight hundred and four sextillion, six hundred and thirty six quintillion, two hundred and eighty eight quadrillion, eight hundred and eleven trillion, six hundred and forty billion, four hundred and thirty two million, three hundred and twenty thousand

    See OEIS A005179.

    Without considering multiple factorisations of 1,000,000 we would arrive at a larger number with one million divisors, that has 12 prime factors:

    200,961,610,708,938,459,249,870,000 = (2^4)(3^4)(5^4)(7^4)(11^4)(13^4)(17)(19)(23)(29)(31)(37).

    • geoffrounce 12 June 2015 at 12:14 pm

      Hi Jim

      I get the same answer as you, using Mathematica 10 ;

      1) FactorInteger [810810000] = {{2, 4}, {3, 4}, {5, 4}, {7, 1}, {11, 1}, {13, 1}}
      This number has 6 different prime factors ie 2,3,5,7,11 and 13

      Number of divisors (from exponents) = 5 * 5 * 5 * 2 * 2 * 2 = 1000 No.

      But, are we correct on this part of the question – as the question says:
      “Quite right, son. Now can you find the smallest number which has exactly one thousand factors, including itself and 1?” Should we be looking for 998 factors?

      2) FactorInteger [173804636288811640432320000] = {{2, 9}, {3, 4}, {5, 4}, {7, 4},
      {11, 4}, {13, 4}, {17, 1}, {19, 1}, {23, 1}, {29, 1}, {31, 1}}

      – which shows this number has 11 different prime number factors, ie:
      2,3,5,7,11,13,17,19,23,29 and 31
      Number of divisors (from exponents) = 10 * 5^5 * 2^5 = 1000000 No.
      PS
      A minor point – a small typo in line 79 (ie divsors) gives 3 errors in the output

      • Jim Randell 13 June 2015 at 12:17 pm

        Counting the number of divisors by multiplying the successors of the exponents of the primes in the prime factorisation will include both 1 and the number itself. (1 when the exponents are all zero, and the number itself when all the exponents are at their maximum value).

        If the question had asked for 1000 divisors excluding 1 and the number itself then we would be looking for a number with 1002 divisors (using my algorithm). The smallest such number is:

        4209124715513000404426612318222895096609085723770880 = (2^166)(3^2)(5)

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: