Find the smallest natural number greater than 1 billion (10^{9}) 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 = p_{1}^{a1} · ... · p_{r}^{ar} , where p_{1} ... p_{r} are prime numbers, and a_{1} ... a_{r} are positive integers.

Now, each divisor of n is composed of the same prime factors, where the *i*th exponent can range from 0 to a_{i}.

Hence there are a_{1} + 1 choices for the first exponent, a_{2} + 1 choices for the second, and so on.

Therefore the number of positive divisors of n is (a_{1} + 1)(a_{2} + 1) ... (a_{r} + 1).

The unique prime factorization of 1000 is 2^{3} · 5^{3}, which contains six prime factors.

So if n has exactly 1000 positive divisors, each a_{i} + 1 is a divisor of 1000, where i may take any value between 1 and 6.

At one extreme, when i = 1, a_{1} + 1 = 1000, so a_{1} = 999, and the smallest integer of this form is 2^{999}, a number with 301 decimal digits.

At the other extreme, when i = 6, a_{1} = a_{2} = a_{3} = 1, and a_{4} = a_{5} = a_{6} = 4.

In this latter case, the smallest integer of this form is clearly 2^{4} · 3^{4} · 5^{4} · 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 = 2^{4} · 3^{4} · 5^{4} · 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 2
^{4}· 3^{4}· 5^{4}· 7^{3}· 11 = (7^{2}/13)n > 3n - 10 · 5 · 5 · 2 · 2, yielding 2
^{9}· 3^{4}· 5^{4}· 7 · 11 = (2^{5}/13)n > 2n - 25 · 5 · 2 · 2 · 2, yielding 2
^{24}· 3^{4}· 5 · 7 · 11 = (2^{20}/5^{3}· 13)n > 500n - 8 · 5 · 5 · 5, yielding 2
^{7}· 3^{4}· 5^{4}· 7^{4}= (2^{3}· 7^{3}/11 · 13)n > 10n - 10 · 5 · 5 · 4, yielding 2
^{9}· 3^{4}· 5^{4}· 7^{3}= (2^{5}· 7^{2}/11 · 13)n > 10n - 10 · 10 · 5 · 2, yielding 2
^{9}· 3^{9}· 5^{4}· 7 = (2^{5}· 3^{4}/11 · 13)n > 15n - 20 · 5 · 5 · 2, yielding 2
^{19}· 3^{4}· 5^{4}· 7 = (2^{15}/11 · 13)n > 200n - 25 · 5 · 4 · 2, yielding 2
^{24}· 3^{4}· 5^{3}· 7 = (2^{20}/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 5^{4} · 7 with 5 · 7^{4}, or replace 13 with 17.

Arithmetically, we find that 2^{4} · 3^{4} · 5 · 7^{4} · 11 · 13 = 2,224,862,640, while 2^{4} · 3^{4} · 5^{4} · 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.

- Online Encyclopedia of Integer Sequences: A000005
- The Prime Pages
- Prime Numbers
- How to discover a proof of the fundamental theorem of arithmetic

Source: Original