# How many factor triples?

At the New Cubed (NY, NJ, New England) math teachers summer conference that was held at Siena in July, a presenter posed a problem that required finding three numbers that multiplied to make 72. The list included 1, 8, 9 and 2, 2, 18 and 3, 4, 6 and several other triples (groups of three numbers).

So I wondered, could we look at 72 and see how many factor triples it has? In general, how many factor triples does a number have?

“How many factors” – I know that answer. Take the prime factorization, and increase each exponent by 1, and add them. I can explain.

- If the number is prime, there are two factors, the number and itself. If the number is the square of a prime (eg 49), there are three factors, 1, 7, and 49. But after some fussing, we realize that , and that our 3 factors are – and extending that, if we have a prime to a power, n, that we have from 0 to n possibilities… which comes out to 0, 1, 2,… , n so n+1 in total.
- If the number has several prime factors, such as 66, we get more factors. For 66, 1, 2, 3, 6, 11, 22, 33, 66, or a total of 8 factors. By examining the prime factorization – 2 x 3 x 11 – we might observe that there are 2 choices for how many 2s (0 or 1), 2 choices for how many 3s (0 or 1), and 2 choices for how many 11s (0 or 1). And 2x2x2 = 8. Makes sense.
- For numbers with more complicated prime factorizations, we combine these rules. , so we can include 0, 1, 2, or 3 factors of 2 (4 choices), times 3 choices for how many 3s, and two choices for how many fives. 4x3x2 = 24. Are there 24? 1, 2, 4, 8, 3, 6, 12, 24, 9, 18, 36, 72, 5, 10, 20, 40, 15, 30, 60, 120, 45, 90, 180, 360. Yup.

But how many factor triples? That’s a new question for me. If I try a prime, such as 2, there is only one: 1 x 1 x 2. A square of a prime gives two: 1 x 1 x 49, 1x7x7. A cube gives three: 1 x 1 x 1331, 1 x 11 x 121, 11 x 11 x 11. Pattern? Maybe. A prime to the fourth gives four: 1 x 1 x 16, 1 x 2 x 8, 1 x 4 x 4, 2 x 2 x 4. A prime to the fifth: 1 x 1 x 243, 1 x 3 x 81, 1 x 9 x 27, 3 x 3 x 27, 3 x 9 x 9. And a prime to the 6th: 1 x 1 x 15,625, 1 x 5 x 3125, 1 x 25 x 625, 1 x 125 x 125, 5 x 5 x 625, 5 x 25 x 125, 25 x 25 x 25. Looks good! Let’s generalize. can only be written as or or and wait just a minute – we could look at just the exponents – they have to add up to 3. And the answer for 7 will be… 0+0+7, 0+1+6, 0+2+5, 0+3+4, 1+1+5, 1+2+4, 1+3+3, 2+2+3. Eight. That pattern doesn’t work.

And there I leave you, with a bit of an exploration, and a false start.

A suggestion: for triples, you really need to take order into account. For example, if we’re factoring 36, the two 2s can go as 1 * 2 * 2 or as 1 * 1 * 4 and the two 3s can go as 1 * 3 * 3 or as 1 * 1 * 9, but there are more than four ways to put them together because of the orders: from 1 * 2 * 2 and 1 * 1 * 9 you can form two different triples 2 * 2 * 9 and 1 * 2 * 18, etc. So it might be more profitable to think of there being *six* ways to do the two 2s: 1 * 2 * 2 and 2 * 1 * 2 and 2 * 2 * 1 and 1 * 1 * 4 and 1 * 4 * 1 and 4 * 1 * 1. Then the ways to combine different primes are unambiguous. (Of course at the end you’ll have to think about how much you over-counted by ….)

Further on the over-counting issue: if you consider how many unordered factor pairs a number has (that is, how many solutions {a, b} there are to a * b = n), it is not the same as the number of factors. Every factor pair {a, b} counts twice (once as a, once as b), except for when it only counts once (when n is a perfect square and a = b = sqrt(n)). In general, unordered counting can be tricky!

If we knew all the distributions for one prime factor, and we knew all the distributions for the second – how could we combine this information to find an answer – I think I want to start there.

I still see a lot of overcounting.

If you know the number of *ordered* distributions for one prime factor, and the number of *ordered* distributions for the second prime factor (etc.), then the number of *ordered triples* whose product is n will just be the product of these two numbers, as in the case of counting factors.

In order to count unordered triples, one approach is to understand (1) how many ordered ones there are and (2) how much duplication there is. For example, the unordered 1 + 2 + 4 corresponds to more ordered triples than the unordered 1 + 1 + 5.

Also, you might want to recheck your counting in the 6th power case. (You’ve listed all the unordered factorizations, but there aren’t 6 of them!)

Finally, I should be clear that I don’t actually know if there’s a “nice” answer for the number of *unordered* triples {a, b, c} such that a * b * c = n. (When n is a prime power, there is, but working out how the different primes play together seems like it will be delicate!)

“In order to count unordered triples” oy vey

Ok, I haven’t forgotten about this, I’ve just been crazily busy. Here are some thoughts:

First, in the ordered case: suppose we want to factor an integer n into a product

n = a * b * c.

How many ordered triples (a, b, c) are there for which this works? Let’s say n = p^k is just a power of a single prime. Then a = p^d, b = p^e and c = p^f and d + e + f = k. So we’re trying to count (ordered!) nonnegative integer solutions to d + e + f = k. Following the calculations in the OP, we get 1 when k = 0, 3 when k = 1 (1 + 0 + 0, 0 + 1 + 0, 0 + 0 + 1), 6 when k = 2, 10 when k = 3 (there are three rearrangements of 0+0+3, six rearrangements of 0+1+2, and one rearrangement of 1+1+1). This looks like triangular numbers, and it is. Then if n is the product of more prime powers, we have to choose for each prime how to divide its powers up, and these choices are totally independent. So we multiply, just like in point (3) in the OP, and we get products of triangular numbers corresponding to the powers of primes in the prime factorization.

Some thoughts about the unordered case to follow eventually :)