Find a smallest number which has exactly N divisors

Question

Let's say we have a number of divisors N. And I want to find a minimum number that has N divisors.

My algorithm

• I found prime numbers(pm = [2,3,5,7,..])
• I have found N's prime factors(N=12, p=[2,2,3], reversed p rp = [3, 2, 2])
• number *= pm[i]^(rp[i]-1), i = 1...length of prime factors

For the N=12, answer is 60 = 2^(3-1) * 3^(2-1) * 5^(2-1)

But for the number 243 my algorithm gives wrong answer (5336100 - but it is not minimum number that has 243 divisors). Expected number is 2822400.

Where is my fault? Any literature?

Answer 1

Let's start with the OEIS sequence. Now any number can be expressed as product of prime powers.

How many divisors will it have? You can prove using combinatorics that it will have:

So you have to solve the equation where the expression above is equal to the number of divisions that you have. I will not write a code here, but notice that because you are looking for integer solutions, you can factor out your number of divisors.

When you will find your m_i, you can get your smallest number by sorting m_i and assigning biggest m_i to smallest prime. So if your m1 = 2, m2 = 5, m3 = 2, the number will be 2^5 * 3^2 * 5^2.

Answer 2

Building upon SalvadorDali's answer:

Given that N is the product of (m_i + 1), you have attempted to find m_i by computing the prime factorization of N, and then subtracting 1 from each factor.

That doesn't necessarily give the minimum answer, as shown by your example with N=243. The prime factorization of 243 is

243 = 3*3*3*3*3

so your method suggests that the minimum should be

2^2 * 3^2 * 5^2 * 7^2 * 11^2 = 5336100

However, the alternative composite factorization of 243 is

243 = 9*3*3*3

which suggests that the minimum should be

2^8 * 3^2 * 5^2 * 7^2 = 2822400

The composite factorization works better because 2^6 is less than 11^2. So in general, your method is only a starting point. After computing your answer, you need to fold the largest primes into the smallest primes to improve the answer.