Skip to main content.

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:

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.


Further reading

  1. Online Encyclopedia of Integer Sequences: A000005
  2. The Prime Pages
  3. Prime Numbers
  4. How to discover a proof of the fundamental theorem of arithmetic

Source: Original

Back to top