Solution to "Product Pairs"


The number of divisors d for some number n with prime factorization p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} where p_1,p_2,\dots,p_k are distinct primes, is given by

d(n)=\prod\limits_{j=1}^k{(a_j+1)}.

In other words, you take the exponents, add one, and multiply. (This can be shown easily enough if you view each distinct prime as a certain color ball, then for each color ball you can choose either none of them, or one, or two, or ..., up to a_i; then each color of ball can be chosen a_i+1 ways, the product of which gives you the total ball groupings possible.) So for example, 12=2^2\cdot 3^1 should have (2+1)(1+1)=6 divisors (including 1 and itself). The divisors of 12 are 1,2,3,4,6,12, which number 6.

Then for each divisor, it has another divisor to which it multiplies to give the number. For instance, the 1 is paired with 12, 2 with 6, and so on. Then the total number of pairs in the example for 12 would be 6/2=3. The exception is when a number is a square, in which case it would have an odd number of divisors, the one in the middle when ordered would be the square root. For instance, the divisors of 16 are 1,2,4,8,16, the middle number being paired with itself.

So in order to have exactly 40 pairings as described in the problem, we need the divisor function to give us either 80 divisors, or 79 divisors. Then the increment of each exponent in the prime factorization of such a number must multiply together to give us 80 or 79. Thus our goal is to see how many ways we can make a product of 79 or 80, then set those factors (minus 1) as the exponents to primes, and see which one is the smallest.

Then what are all the ways to make 80 or 79? We build quite an extensive list, and I will write them in the form \{ x_1,x_2,\dots\}, meaning that x_1\cdot x_2\cdots=80\text{ or }79. Of course 79 is prime so there is only one way to make it, so I will make it first in the list, followed by ways to make 80.

\{ 1,79\} \ , \ \{ 1, 80\} \ , \ \{ 2, 40\} \ , \ \{ 4, 20\} \ , \ \{ 5, 16\} \ , \ \{ 8, 10\} \ , \ \{ 2, 4, 10\}

\{ 2, 5, 8\}\ , \ \{ 2, 2, 20\}\ , \ \{ 2, 2, 4, 5\} \ , \ \{ 2, 2, 2, 10\} \ , \ \{ 2, 2, 2, 2, 5\} .

I believe that is all the ways to get either 79 or 80 when multiplied, then the sets of exponents will be all these minus 1, giving us

\{ 0,78\} \ , \ \{ 0, 79\} \ , \ \{ 1, 39\} \ , \ \{ 3, 19\} \ , \ \{ 4, 15\} \ , \ \{ 7, 9\} \ , \ \{ 1, 3, 9\}

\{ 1, 4, 7\}\ , \ \{ 1, 1, 19\}\ , \ \{ 1, 1, 3, 4\} \ , \ \{ 1, 1, 1, 9\} \ , \ \{ 1, 1, 1, 1, 4\} .

The number we are looking for must have these exponents in its factorization, and since we are looking for the smallest number, the smallest prime will be assigned the highest exponent, and then we can easily compare two by two until we have the victor. For odd numbers, the smallest prime is 3, and after comparing the resulting numbers, we discover that \{ 1, 1, 1, 1, 4\} results in the smallest odd number 3^4\cdot 5\cdot 7\cdot 11\cdot 13=405405. Then the smallest odd number with exactly 40 "product pairs" is 405405.

The same process is done for even numbers with the only difference being that the smallest prime factor is 2, therefore we take each exponents set, assign them in decreasing order to increasing primes, and compare them with each other. In this case the smallest value comes out from the set \{ 1,1,3,4\} to be 2^4\cdot 3^3\cdot 5\cdot 7=15120. So the smallest even number, actually smallest positive number altogether which can be factored into exactly 40 product pairs is 15120.