How many ways can we choose 3 positive integers a<b<c so that a•b•c=30,030

Question

For an eighth grade math class that is talking about factoring with integers. Thank you to anyone who helps me. 

Answer 1

There are six primes, each appearing just once. We can indeed look at it combinatorially, as the number of ways of choosing 3 subsets (order of the 3 irrelevant) from six. That is because they are ordered in ascending order after we choose them, and because of the uniqueness of prime factorization. Here are the multinomials

 

(6 choose 1,1,4)/2! + (6 choose 1,2,3) + (6 choose 2,2,2)/3! 

 

6!/(4!*2) + 6!/(3!*2!) + 6!/(2!*2!*2!*3!) = 90

 

Then you consider a=1, and find 

 

(6 choose 1,5) + (6 choose 2,4) + (6 choose 3,3)/2!

 

= 31

 

90+31=121

Answer 2

First, find all the prime factors of 30,030:
     2*3*5*7*11*13

Then include 1:
   1*2*3*5*7*11*13

 

Now, group all these factors to become a*b*c.  Select all integers a, b, and c such that a<b<c
  a          b                 c 
  1          2              3*5*7*11*13=15015

  1         2*3=6       5*7*11*13=5005
 . . .

Now, it becomes a matter of combinations.  "How many ways" (combinations) can we construct a, b, and c such that a<b<c ?

 

It may be a bit beyond eighth grade math to explain how to count the combinations, but I'll start with a simple introduction:

  - We must use all 7 factors as factors to construct a, b and c.  For example (1, 2, 3*4*7*11*13=15015) is o.k.

  - We are limited by the restriction (constraint) that a<b<c.  That limits which factors we may choose.  If we keep the factors in order, we can select products (that is, a, b, and c) that are in order [note: but we may also take them out of order]

   - So, if a=1, we can choose b=2 or b=5 or b=24, or ...  but we must allow at least one number (like 11*13=131 to be the value for c.

  -  Then, we can do this again for a=1*2=2.  And again for a=1*2*3.  And again for a=1*2*3*5.  And so on.

  -  Once we have a value for both a and b, we only need to consider

                 c=30030/(ab)  [when c is an integer].

  -  If we count those possibilities, that gives us the answer.

 

I find that using a computer to do "exhaustive enumeration" (that is, try all numbers and count the triplets that work) is a very practical solution (because computers today are very, very, very fast).  So, here's my program and the output:

 

 

count = 0

FOR a = 1 TO 30030                 /* might as well check them all */

  FOR b = a+1 TO 30030/a        /* must have b>a up to b = 30030/a */

    c = INT( 30030 / (a*b) )                /* that makes c=INTEGER( 30030/(a*b) ) */

                                            /* provided that a*b*c=30030 */

    IF ( (a*b*c=30030) AND (a<b) AND (b<c) ) THEN

      count = count + 1

      OUTPUT (a, b, c)

    ENDIF

  NEXT b

NEXT a

OUTPUT ("done.", count)

END

 

1 2 15015
1 3 10010
1 5 6006
1 6 5005
1 7 4290
1 10 3003
1 11 2730
1 13 2310
1 14 2145
1 15 2002
1 21 1430
1 22 1365
1 26 1155
1 30 1001
1 33 910
1 35 858
1 39 770
1 42 715
1 55 546
1 65 462
1 66 455
1 70 429
1 77 390
1 78 385
1 91 330
1 105 286
1 110 273
1 130 231
1 143 210
1 154 195
1 165 182
2 3 5005
2 5 3003
2 7 2145
2 11 1365
2 13 1155
2 15 1001
2 21 715
2 33 455
2 35 429
2 39 385
2 55 273
2 65 231
2 77 195
2 91 165
2 105 143
3 5 2002
3 7 1430
3 10 1001
3 11 910
3 13 770
3 14 715
3 22 455
3 26 385
3 35 286
3 55 182
3 65 154
3 70 143
3 77 130
3 91 110
5 6 1001
5 7 858
5 11 546
5 13 462
5 14 429
5 21 286
5 22 273
5 26 231
5 33 182
5 39 154
5 42 143
5 66 91
5 77 78
6 7 715
6 11 455
6 13 385
6 35 143
6 55 91
6 65 77
7 10 429
7 11 390
7 13 330
7 15 286
7 22 195
7 26 165
7 30 143
7 33 130
7 39 110
7 55 78
7 65 66
10 11 273
10 13 231
10 21 143
10 33 91
10 39 77
11 13 210
11 14 195
11 15 182
11 21 130
11 26 105
11 30 91
11 35 78
11 39 70
11 42 65
13 14 165
13 15 154
13 21 110
13 22 105
13 30 77
13 33 70
13 35 66
13 42 55
14 15 143
14 33 65
14 39 55
15 22 91
15 26 77
21 22 65
21 26 55
22 35 39
26 33 35

done. 121