The smallest number with a given number of divisors

Suppose you want to find the smallest number with 5 divisors. After thinking about it a little you might come up with 16, because

16 = 2⁴

and the divisors of 16 are 2^k where k = 0, 1, 2, 3, or 4.

This approach generalizes: For any prime q, the smallest number with q divisors is 2^q-1.

Now suppose you want to find the smallest number with 6 divisors. One candidate would be 32 = 2⁵, but you could do better. Instead of just looking at numbers divisible by the smallest prime, you could consider numbers that are divisible by the two smallest primes. And in fact

12 = 2² 3

is the smallest number with 6 divisors.

This approach also generalizes. If h is the product of 2 primes, say h = pq where p >= q, then the smallest number with h divisors is

2^p-1 3^q-1.

The divisors come from letting the exponent on 2 range from 0 to p-1 and letting the exponent on 3 range from 0 to q-1.

For example, the smallest number with 35 divisors is

5184 = 2^7-1 3^5-1.

Note that we did not require p and q to be different. We said p >= q, and not p > q. And so, for example, the smallest number with 25 divisors is

1296 = 2^5-1 3^5-1.

Now, suppose we want to find the smallest number with 1001 divisors. The number 1001 factors as 7*11*13, which has some interesting consequences. It turns out that the smallest number with 1001 divisors is

2^13-1 3^11-1 5^7-1.

Does this solution generalize? Usually, but not always.

Let h = pqr where p, q, and r are primes with p >= q >= r. Then the smallest number with h divisors is

2^p-1 3^q-1 5^r-1

with one exception. The smallest number with 8 divisors would be 30 = 2*3*5 if the theorem always held, but in fact the smallest number with 8 divisors is 24.

In [1] M. E. Gorst examines the exceptions to the general pattern. We've looked at the smallest number with h divisors when h is the product of 1, or 2, or 3 (not necessarily distinct) primes. Gorst considers values of h equal to the product of up to 6 primes.

We've said that the pattern above holds for all h the product of 1 or 2 primes, and for all but one value of h the product of 3 primes. There are two exceptions for h the product of 4 primes. That is, if h = pqrs where p >= q >= r >= s are primes, then the smallest number with h divisors is

2^p-1 3^q-1 5^r-1 7^s-1

with two exceptions. The smallest number with 2⁴ divisors is 2³ * 3 * 5, and the smallest number with 3 * 2³ divisors is 2³ * 3² * 5.

When h is the product of 5 or 6 primes, there are infinitely many exceptions, but they have a particular form given in [1].

The result discussed here came up recently in something I was working on, but I don't remember now what. If memory serves, which it may not, I wanted to assume something like what is presented here but wasn't sure it was true.

***

[1] M. E. Grost. The Smallest Number with a Given Number of Divisors. The American Mathematical Monthly, September 1968, pp. 725-729.

The post The smallest number with a given number of divisors first appeared on John D. Cook.