# Solution to puzzle 47: 1000 divisors

Find the smallest natural number greater than 1 billion (109) that has exactly 1000 positive divisors.  (The term divisor includes 1 and the number itself.  So, for example, 9 has three positive divisors.)

The number of divisors of a natural number may be determined by writing down its prime factorization.  The Fundamental Theorem of Arithmetic guarantees that the prime factorization is unique.

Let n = p1a1 · ... · prar , where p1 ... pr are prime numbers, and a1 ... ar are positive integers.
Now, each divisor of n is composed of the same prime factors, where the ith exponent can range from 0 to ai.
Hence there are a1 + 1 choices for the first exponent, a2 + 1 choices for the second, and so on.
Therefore the number of positive divisors of n is (a1 + 1)(a2 + 1) ... (ar + 1).

The unique prime factorization of 1000 is 23 · 53, which contains six prime factors.
So if n has exactly 1000 positive divisors, each ai + 1 is a divisor of 1000, where i may take any value between 1 and 6.
At one extreme, when i = 1, a1 + 1 = 1000, so a1 = 999, and the smallest integer of this form is 2999, a number with 301 decimal digits.
At the other extreme, when i = 6, a1 = a2 = a3 = 1, and a4 = a5 = a6 = 4.
In this latter case, the smallest integer of this form is clearly 24 · 34 · 54 · 7 · 11 · 13 = 810,810,000.

In fact, of all the natural numbers with exactly 1000 divisors, 810,810,000 is the smallest.  A demonstration by enumeration follows.  Having established this result, it will be a simple matter to find the smallest integer greater than 1 billion that has 1000 divisors.

Let n = 24 · 34 · 54 · 7 · 11 · 13.
The smallest integer that can be obtained by combining the six prime factors in various ways is:

• 5 · 5 · 5 · 4 · 2, yielding 24 · 34 · 54 · 73 · 11 = (72/13)n > 3n
• 10 · 5 · 5 · 2 · 2, yielding 29 · 34 · 54 · 7 · 11 = (25/13)n > 2n
• 25 · 5 · 2 · 2 · 2, yielding 224 · 34 · 5 · 7 · 11 = (220/53 · 13)n > 500n
• 8 · 5 · 5 · 5, yielding 27 · 34 · 54 · 74 = (23 · 73/11 · 13)n > 10n
• 10 · 5 · 5 · 4, yielding 29 · 34 · 54 · 73 = (25 · 72/11 · 13)n > 10n
• 10 · 10 · 5 · 2, yielding 29 · 39 · 54 · 7 = (25 · 34/11 · 13)n > 15n
• 20 · 5 · 5 · 2, yielding 219 · 34 · 54 · 7 = (215/11 · 13)n > 200n
• 25 · 5 · 4 · 2, yielding 224 · 34 · 53 · 7 = (220/5 · 11 · 13)n > 1000n

Any other combination of the prime factors would contain a power of 2 greater than 30, which, on its own, would yield an integer greater than 1 billion.
Therefore, the smallest natural number with exactly 1000 divisors is 810,810,000.

To find the smallest number greater than 1 billion with exactly 1000 divisors, we must substitute larger prime(s) in the factorization of 810,810,000.
Logically, the smallest such substitution must be either: replace 54 · 7 with 5 · 74, or replace 13 with 17.
Arithmetically, we find that 24 · 34 · 5 · 74 · 11 · 13 = 2,224,862,640, while 24 · 34 · 54 · 7 · 11 · 17 = 1,060,290,000.

Therefore the smallest natural number greater than 1 billion that has exactly 1000 positive divisors is 1,060,290,000.