0
$\begingroup$

For given positive integer $n$ find the first number $x$ with exactly $n$ divisors. For simplicity of the problem we can assume that $x$ will always fit in integer size and $n \leq 1000$.

Example

If $n=4, x = 6, \text{ divisors of 6 are } \{1, 2, 3, 6\}\\n=6, x=12, \text{divisors of 12 are } \{1,2,3,4,6,12\}$

I was thinking because the number should have at most 1000 divisors we should brute force them in some way, but I cannot think how it could be done.

$\endgroup$
  • $\begingroup$ If $n$ is always less than $1000$ you could consider precomputing first number $x$ with exactly $n$ divisors for each $n<1000$, and later retrieving $x$ in $O(1)$. $\endgroup$ – fade2black Dec 9 '17 at 15:34
  • $\begingroup$ I got it, but how can we find the first number with $n$ divisors $\endgroup$ – someone12321 Dec 9 '17 at 15:36
  • $\begingroup$ Are you aware of the formula for the number of divisors of an integer? $\endgroup$ – Yuval Filmus Dec 9 '17 at 16:41
2
$\begingroup$

Some observations: If p is a prime, then $p^{n-1}$ has exactly n divisors. And if for example p, q, r are different primes, then $p^{n-1} q^{m-1} r^{j-1}$ has exactly n * m * j divisors.

And that's the only way we can find numbers with exactly n divisors: We write n as a product n = n1 * n2 * n3 ..., then find primes p1, p2, p3 and so on, and the product $p1^{n1-1} p2^{n2-1} p3^{n3-1} ...$ has exactly n divisors.

If we sort so that n1 ≥ n2 ≥ n3, then a product that is not in the form $2^{n1-1} 3^{n2-1} 5^{n3-1} ... $ can be made smaller while having the same number of divisors by using the primes 2, 3, 5 in that order. For example, if we start with $2^3 5^2$ then $2^3 3^2$ has the same number of divisors, but is smaller. Likewise, $3^3 2^2$ can be replaced with $2^3 3^2$ with the same number of divisors, bit smaller.

So the smallest number with n divisors has the form $2^{n1-1} 3^{n2-1} 5^{n3-1} ... $ with n1 ≥ n2 ≥ n3 ... and n = n1 * n2 * n3 ...

Now a number like n = 1000, or n = $10^{1000}$, can be written as a product in many ways, so you need to reduce the number of possibilities. You can use an algorithm where you try all possible exponents for 2 that could lead to the smallest number with n divisors, then all possible exponents for 3, and so on.

Let n = p1 * p2 * p3 ... * pk, with primes p1 ≥ p2 ≥ p3 ≥ ... ≥ pk. Whenever we choose an exponent, that exponent is either p - 1 where p is the largest prime not used so far, or it is of the form ab - 1 where b is the smallest prime factor of ab, and ab is greater than that largest prime. (That's quite obvious, right? It's a prime or composite minus 1, and since the exponents are in descending order, its the largest prime minus 1, or greater than that).

n was the product of k primes. Let P be the k-th prime. If an exponent is of the form ab-1, then P is not a factor of the number. And if we have a factor $p^{ab-1}$, then replacing this with $p^{a-1} P^{b-1}$ gives a number with the same number of factors, but smaller unless $p^a < P$.

This hugely reduces the number of choices. Take n = $2^{1000}$ which is the product of 2,000 primes. The k-th prime is very roughly P ≈ 20,000.

We saw that the smallest number with n divisors can only have a factor $p^{ab-1}$ if $p^a < P$. We have $2^{15}≥P ≈ 20,000$, $3^{10} ≥ P$, $5^7≥P$, $7^6≥P$, $11^5≥$, and $13^4≥P$, so a ≤ 14 when p = 2, a ≤ 9 when p = 3, a ≤ 6 when P = 5, a ≤ 5 when P = 7, a ≤ 4 when P = 11, and a ≤ 3 when p ≥ 13. And we must have ab ≥ 5, b is the smallest prime factor of ab, and ab must only have prime factors 2 and 5.

As a result, the only composite exponents minus 1 that are possible in the smallest number with $10^{1000}$ divisors are: $2^{4*2-1}$, $2^{5*2 - 1}$, $2^{5*5 - 1}$, $2^{8*2-1}$, $2^{10*2 - 1}$, $3^{4*2-1}$, $3^{5*2 - 1}$, $3^{5*5 - 1}$, $3^{8*2-1}$, $5^{4*2-1}$, $5^{5*2-1}$, $5^{5*5-1}$, $7^{4*2-1}$, $7^{5*2-1}$, $7^{5*5-1}$, and $11^{4*2-1}$. This is followed by a huge number of factors $p^{5-1}$, finishing with a huge number of factors $p^{2-1}$.

Since the exponents have to be in non-decreasing order, there is only a small number of cases to try, even for a huge number like $n = 10^{1000}$.

PS. In your trivial examples, n = 4 = 2 * 2, the solution was $2^{2-1} 3^{2-1} = 6$, and with n = 6 = 3 * 2, the solution was $2^{3-1} 3^{2-1} = 12$.

PS. Assume you have a more moderately sized n, let's say an n that is the product of 10 primes, making P = 10th prime = 29. We have $2^5<29$, $3^3<29$, $5^2<29$, but $7^2 > 29$. Therefore the only possible factors with an exponent that is not a prime -1 are: $2^{4-1}$, $2^{9-1}$, $2^{6-1}$, $2^{8-1}$, $2^{10-1}$, $2^{25-1}$, $3^{4-1}$, $3^{9-1}$, $3^{6-1}$, and $5^{4-1}$.

$\endgroup$
0
$\begingroup$

This is how you can precompute $A[n]$s for each $n<1000$.

precompute()
  set A[1..1000] = 0 
  count = 1
  x=1 
  while(count <= 1000)
   m = count_divisors_of(x)
   if (A[m] == 0)
     A[m] = x
     count = count + 1
   end
   x = x + 1
  end
end

This procedure must terminate since for any $n$, $2^{n-1}$ has exactly $n$ divisors: $1, 2, 4,\dots 2^{n-1}$. However, I do not know how long time it may take to compute all $A[i]$s. You can optimize the procedure count_divisors_of. Also, the tables in this article list all of the divisors of the numbers $1$ to $1000$.

$\endgroup$
  • $\begingroup$ Well, if n is a large prime, then the only numbers with exactly n divisors are of the form p^(n-1) for primes p, so this will not finish in a lifetime :-) $\endgroup$ – gnasher729 Dec 9 '17 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.