Number of factors of a number.

There is another problem that I came across, which is as follows:

There is a number n, find the number of numbers x, such that n is a factor of x, and the number of factors of x, equals n.

Now, if we want to find the number of numbers whose number of factors is n, it is clearly infinity, for any n. For this, we can choose a prime number p (any would do), and simply raise it to power n-1, making p^(n-1). This clearly has n factors. Since there are infinite number of primes, this number would be infinite. The only change in this problem statement is that, n should be a factor of x.

Let's start by proving that, there exists at least one such x, for every n. We will do this by using a construction of such a number.

Let's say,
n = p1^ap1 * p2^ap2 * p3^ap3 * ...... for distinct primes p1, p2, p3 etc...
Let's construct x as follows.
x = p1^(p1^ap1 - 1) * p2^(p2^ap2 - 1) * p3^(p3^ap3 -1) * ....
The number of factors for x, is
(p1^ap1 - 1 + 1) * (p2^ap2 - 1 + 1) * (p3^ap3 - 1 + 1) * ...
= p1^ap1 * p2^ap2 * p3^ap3 * ... = n

Also, since p1^ap1 - 1 >= ap1 etc..., we know that n divides x. So, there is at least one such x.

Let's say, n is of the form p (where p is a prime). Then,
X = 2^a2 * 3^a3 * 5^a5 * ... * p^(ap + 1) * ...
where all ak >= 0 for k >= 2.

Now,
n = (a2 + 1) * (a3 + 1) * (a5 + 1) * ... * (ap + 2) * ... = p

Since, p is a prime, only one of these factors should be p, and rest all should be 1s. Clearly, only ap + 2, can be p, since it can't be 1. So, this has only one solution, that is given by, ap = p - 2.

Let's consider n of the form p1 * p2 (where p1 and p2 are different primes). Then,
X = 2^a2 * 3^a3 * 5^a5 * ... * p1^(ap1 + 1) * ... * p2^(ap2 + 1) * ...

Now,
n = (a2 + 1) * (a3 + 1) * (a5 + 1) * ... * (ap1 + 2) * .. * (ap2 + 2) * .. = p1 * p2

Again, only non-1 terms can be ap1 + 2, and ap2 + 2. So,
(ap1 + 2) * (ap2 + 2) = p1 * p2

Since all primes >= 2, and since p1 and p2 are assumed to be distinct, the solutions are,
ap1 + 2 = p1 and ap2 + 2 = p2, or
ap1 + 2 = p2 and ap2 + 2 = p1.
So, here there are 2 solutions.

Similarly, if n is of the form, p1 * p2 * p3 * .... * pk, for distinct primes p1 .. pk, the number of such x's will be k!.

Now, let's say n has p^2 as a factor, for a prime p. Now, we can prove that, if p > 2, this has infinite solutions. Consider all other prime factors of n, to use the construction given above, to fill their part of factors. Now, just consider the p^2 part of n.

p^2 = (ap + 3) * (Terms due to other prime factors than p1, p2 etc...). Now, it can be that
ap + 3 = p^2 (or)
ap + 3 = p

In the second case, there are infinite solutions, since when ap + 3 = p, other prime factors than p1, p2, p3, ..., can contribute to the other p in p^2. Also, if p > 2, ap + 3 = p is possible.

Let's consider when p^3 is a factor for, p >= 2.
p^3 = (ap + 4) * (Terms due to other prime factors than p1, p2 etc...). Now, it can be that
ap + 4 = p^3
ap + 4 = p^2
ap + 4 = p
However, even the second possibility gives infinite solutions here, which is ap + 4 = p^2. Similarly, infinite solutions would result, whenever, a number n has p^ap as a factor, where ap >= 4.

So, if a number n has p^2 as a factor, for prime p > 2, it has infinite x's having this property, and also when n has p^3 as a factor, there are infinite x's having this property, for any prime p.

Now, only possible n remaining is,
n = 2^2 * p1 * p2 * p3 * p4 * ... * pk.
x = 2^(a2 + 2) * p1^(ap1 + 1) * p2^(ap2 + 1) * .... * pk^(apk + 1).
n = (a2 + 3) * (ap1 + 2) * (ap2 + 2) * (ap3 + 2) * ... * (apk + 2)
= 2^2 * p1 * p2 * p3 * p4 * ... * pk.