Skip to content

How many factor triples?

October 6, 2019 am31 8:56 am

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 49 = 7^2, and that our 3 factors are 7^0, 7^1, and 7^2 – 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. 360 = 2^3 \times 3^2 \times 5^1, 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. p^3 can only be written as 1\times 1\times p^3 or 1\times p\times p^2 or p\times p\times p 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.

Advertisements
5 Comments leave one →
  1. October 6, 2019 am31 10:13 am 10:13 am

    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 ….)

  2. October 6, 2019 am31 10:18 am 10:18 am

    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!

    • October 6, 2019 pm31 4:31 pm 4:31 pm

      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.

      • October 7, 2019 pm31 12:46 pm 12:46 pm

        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!)

        • October 7, 2019 pm31 12:47 pm 12:47 pm

          “In order to count unordered triples” oy vey

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: