While practicing for a Mathematics competition in the future, I was going through past problems which were used. One of the problems in the category of Arithmetic/Number Theory went as follows:
Consider all positive integers having exactly 12 positive integral factors. Determine the sum of all of the three smallest of these integers.
The solution was $216$.
Initially, I brute-forced the problem, guessing numbers I thought would have 12 factors, and checking them. While this can yield results, it yields them far too slowly for a timed contest.
After some thought, I discovered a solution which worked for the numbers I tested, though it doesn't work for prime numbers and is very time consuming for large numbers. The solution goes as follows:
Assume you are given a number of factors $n$. To create a number with $n$ factors, we can factor $n$. If we use the example $12$ for $n$, we get $(3)\cdot(4)$ and $(2)\cdot(6)$. We then factor these factors, resulting in $(3)\cdot(2)\cdot(2)$ (We get this twice but we only need to use it once) Using these factors, we can create formulas to generate numbers with $12$ factors. To do this we use the formula
$$a^x b^y c^z$$ where x is one of the factors -1, y is another factor -1, and z is the third. (This also works with more than three factors, it just needs to be extended.) For 12, this yields us
$$a^1 b^1 c^2 \\ a^3 b^2 \\ a^5 b^1$$
Each of these formulas can generate a number with 12 factors if we input prime numbers into $a$, $b$, and $c$. In this case, we want to create the lowest numbers with 12 factors, so we can use the first prime numbers $2$, $3$, and $5$, and arrange them in such a way that we get the smallest value, ie. put the smallest numbers into the larger exponents. We then simply plug in the values and test. (The lowest possible combination produces $n$ instead of a number with $n$ factors
$$2^2 \cdot 3^1 \cdot 5^1 = 12 \\ 2^2 \cdot 3^1 \cdot 7^1 = 84\\ 2^3 \cdot 3^2 = 72 \\ 2^2 \cdot 3^1 \cdot 5^1 = 60$$ This means that $60$, $72$, and $84$ should be the smallest three numbers with $12$ factors. Let's check!
$60$ has the factors $(1,2,3,4,5,6,10,12,15,20,30,60)$, 12 of them!
$72$ has the factors $(1,2,3,4,6,8,9,12,18,24,36,72)$, again, 12 of them
$84$ has the factors $(1,2,3,4,6,7,12,14,21,28,42,84)$ again, 12!
What about the sum of these numbers, does it fit the solution?
$60+72+84 = 216$! Amazing!
While this solution works, it is rather inefficient and time consuming, and requires composite numbers. tl;dr: Is there a solution that exists such that it works on prime numbers or that requires less time? Will this method of calculating numbers by creating prime factors in this way always work? Why does this work?
Best Answer
Let $n \in \mathbb{N}$ and consider its unique prime factorization (fundamental theorem of arithmetic)
$$n = p_1^{a_1} p_2^{a_2} \cdots p_m^{a_m}.$$
How many factors does $n$ have?
Well, a basic counting argument will yield
$$(a_1+1)(a_2+1) \cdots (a_m+1).$$
So, try to come up with relatively small prime factorization that yield 12 here. The integers that you found work.
As an example, if we have $12 = 2^2*3$ then 12 has 6 factors, namely
$$2^0*3^0 = 1, 2^1*3^0 = 2, 2^2*3^0 = 4, 2^0*3^1 = 3, 2^1*3^1 = 6, 2^2*3^1 =12.$$
Further, to count the number of divisors (or factors) that an integer has, it is common to use the arithmetic function $\sigma_0(n)$. The function is multiplicative which means that if we have integers $k, l$ such that $k$ and $l$ are relatively prime (no common prime factors) then $\sigma_0(kl) = \sigma_0(k) \sigma_0(l) $. The upshot here is that powers of distinct primes are relatively prime and so if you know the prime factorization for an integer $n$ then you can calculate $\sigma_0(n)$ relatively fast.
For more on this, see the properties of the divisor function here: https://en.m.wikipedia.org/wiki/Divisor_function
I hope this helps!