How Many Factors?

Posted on by Clio

A post on G+ Mathematics asks: “How many of the positive divisors of 8400 have four or more positive divisors?” A divisor, or a factor, is an integer which evenly divides another integer; in other words, it is the opposite of a multiple (with the exception of 0). For instance, 8 has the factors {1, 2, 4, 8}, while 30 has the factors {1, 2, 3, 5, 6, 10, 15, 30}. In other words, 8 is a multiple of 1, 2, 4, and 8, while 30 is a multiple of 1, 2, 3, 5, 6, 10, 15, and 30.

In this post, I’ll discuss the general pattern of factors, and then solve the specific problem. For the remainder of the post, “factor” and “integer” will be limited to positive integers.

1 has one factor, itself. All integers have factors of 1 and themselves, and so all integers except 1 have two factors. By definition, prime numbers are numbers that have two factors: Themselves and 1. Hence, all composites have at least three factors. Here are the number of factors of positive integers, based on its composition:

  1. 1
  2. A prime (2, 3, 5, 7, 11, …)
  3. A square of a prime (4, 9, 25, 49, 121, …)
  4. The product of two primes (6, 10, 14, 15, 21, 22, 33, 35, 55, 77, …); cubes of primes (8, 27, 125, 343, 1331, …)
  5. The fourth power of a prime
  6. A prime times the square of a different prime; the fifth power of a prime
  7. The sixth power of a prime
  8. A prime times the cube of a different prime; the seventh power of a prime
  9. The product of the squares of two different primes; the ninth power of a prime
  10. A prime times the fourth power of a different prime; the ninth power of a prime
  11. The tenth power of a prime
  12. The square of one prime times the cube of a different prime; a prime times the fifth power of a different prime; the square of a prime times a different prime times a third prime; the eleventh power of a prime

… and so on. In general, the way to determine the number of factors a given number has, first list all of the prime factors and the number of times each occurs. If the prime factors of a number are \((p_1, p_2, p_3, …)\) and the corresponding number of occurrences are \((v_1, v_2, v_3, …)\), then the number of factors is \[n = (v_1 + 1)\cdot (v_2 + 1) \cdot (v_3 + 1)…\]

Note that we can determine the possible configurations of primes that yield a given number of factors. For instance, since \[9 = (8 + 1) = 3 \cdot 3 = (2 + 1) \cdot (2 + 1),\] then a composite of the form \(p_1^8\) or \(p_1^2p_2^2\) will have nine factors. Since \[12 = 3 \cdot 4 = 2 \cdot 6 = 3 \cdot 2 \cdot 2,\] then a compote of the form \(p_1^{11}\) or \(p_1^2p_2^3\) or \(p_1p_2^5\) or \(p_1^2p_2p_3\) will have twelve factors.

Incidentally, this means that \(2^2\cdot 3\cdot 5 = 60\) is the lowest number that has twelve or more factors: 1, 2, 3, 4, 5, 6, 10, 12, 20, 15, 30,  and 60.

Now that we have a strategy, we can determine the number of factors of 8400. First, list the prime factors. We can quickly convert each terminal zero into 2 and 5: 8400 = 840 ⋅ 2 ⋅ 5 = 84 ⋅ 2 ⋅ 2 ⋅ 5 ⋅ 5. Since 84 is even, we can continue dividing by 2: 84 = 2 ⋅ 42 = 2 ⋅ 2 ⋅ 21. We should be able to recognize 21 = 3 ⋅ 7. Collect all the factors: \[8400 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 \cdot 5 \cdot 7 = 2^43^15^27^1\]

To determine the number of factors, apply the formula: \[n = (4 + 1)(1 + 1)(2 + 1)(1+ 1) = 5\cdot 2 \cdot 3 \cdot 2 = 60\]

We can also quickly determine the number of these factors in each of the first three categories:

  1. 1
  2. 4, since there are four primes
  3. 2, since there are two primes with a power of two or higher

Thus the number of factors of 8400 with four or more factors themselves is \(60 – (1 + 4 + 2) = 53\).

Extension

Let’s say that we wanted to find out how many factors of 8400 (or any other integer) have five or more factors. First, let me introduce a piece of general notation: \(e_f\) represents the number of a prime factors with a power of at least f. In the case of 8400, \(e_1 = 4, e_2 = 2, e_3 = 1, e_4 = 1,\) and all other \(e_f = 0\).

Finding the number of factors with four factors is a little trickier, because we need to know two numbers: How many cubes of primes there are, and how many products of two primes. We can easily read how many cubes of primes there are in the factor set (\(e_3 = 1\)), but we also need to know how many products of different primes there are. If there are \(n\) distinct prime factors, then there are \(\frac{n(n-1)}{2}\) unique ways of combining them. So we can add this to our list; we can also easily count the number of factors with five factors, since that’s \(e_4\):

  1. 1
  2. 4
  3. 2
  4. 7: 1 (\(e_3\)) + 6 (\(4 \cdot 3 \div 2\))
  5. 1 (\(e_4\))

For the next category, six factors, we need \(e_2\) and \(e_1\). The general formula for “a prime times the square of a different prime” is \(e_2\cdot (e_1 – 1)\); in this case, it’s \(2 \cdot (4-1) = 6\). \(e_5 = e_6 = 0\), so that’s it for the next two categories.

The count of numbers with eight factors is \(e_7 + e_3 \cdot (e_1 – 1) + e_1 \cdot (e_1 – 1) \cdot (e_1 – 2) \div 6 \). In this case, that \(0 + 1 \cdot (4 – 1) + 4 \cdot (4 – 1) \cdot (4 -2) \div 6 = 7\). The count of numbers with nine factors is \(e_8 + e_2 \cdot (e_2 – 1) \div 2\), which in this case is \(0 + 2 \cdot (2-1) \div 2 = 1\).

Continuing along the pattern, the count of numbers with ten factors is \(e_9 + e_4 \cdot (e_1 – 1) = 0 + 1 \cdot (4 – 1) = 3\); for eleven factors, it’s simply \(e_{10} = 0\).

  1. 1
  2. 4
  3. 2
  4. 7
  5. 1
  6. 6
  7. 0
  8. 7
  9. 1
  10. 3
  11. 0

For 12, we have four different configurations:

  1. The square of a prime times the cube of a different prime, that is, \(e_3 \cdot (e_2 – 1) = 1 \cdot (2 – 1) = 1\)
  2. A prime times the fifth power of a different prime, that is \(e_5 \cdot (e_1 – 1) = 0 \cdot (4 – 1) = 0\)
  3. The square of a prime times a different prime times a third prime, that is \(e_2 \cdot (e_1 – 1) \cdot (e_1 – 2) \div 2 = 2 \cdot (4 – 1) \cdot (4 – 2) \div 2 = 6 \)
  4. The eleventh power of a prime, that is, \(e_{11} = 0\)

The third of these deserves an explanation. First, there are \(e_2\) primes with squares. That leaves \(e_1 – 1\) possible second values and \(e_1 – 2\) possible third values. However, since the second and third values are interchangeable, we divide by 2.

That means there are seven factors of 8400 with exactly twelve factors: \[2^3\cdot5^2 = 200, \\ 2^2\cdot3\cdot5 = 60, 2^2\cdot3\cdot7 = 84, 2^2\cdot5\cdot 7 = 140, \\ 5^2\cdot2\cdot3 = 150, 5^2\cdot2\cdot 7 = 350, 5^2\cdot3\cdot7 = 525\]

For 13, we see that \(e_{12} = 0\). For 14, we see that \(e_{13} = 0\) and \(e_{6} = 0\). For 15, we see that \(e_{14} = 0\) while \(e_4 \cdot (e_2 – 1) = 1 \cdot 1 = 1\). Adding these to our list:

  1. 1
  2. 4
  3. 2
  4. 7
  5. 1
  6. 6
  7. 0
  8. 7
  9. 1
  10. 3
  11. 0
  12. 7
  13. 0
  14. 0
  15. 1

Sixteen can be factored in a variety of ways: 1 ⋅ 16, 2 ⋅ 8, 2 ⋅ 2 ⋅ 4, 4 ⋅ 4, and 2 ⋅ 2 ⋅ 2 ⋅ 2. In the case of 8400, the first two yield zero, the third yields 3, the fourth yields 0, and the last yields 1, for a total of 4.

We could continue in this fashion, developing formulas for each category up to sixty, which would have a single entry for 8400 (8400 itself). Notice that we’re already accounted for 45 of the 60, though, so there are only fifteen factors between 16 and 60. We know that the remaining factor counts will not be odd, since that would entail a prime (the largest prime we can have is 5) or a composite without any evens (the largest such composite we can have is 15). We can likewise rule out any evens with factors greater than 5: 22, 26, 28, 34, 38, 42, 44, 46, 52, 56, 58. We can also rule out 50 (two prime factors greater than 3) and 54 (three prime factors greater than 2).

That leaves the following as candidates: 18, 20, 24, 30, 32, 36, 40, and 48. As it turns out, there is at least one factor of 8400 in each of these categories.

A Different Approach

We could also mechanically process through each possible combination of prime factors and use the formula for factor count to determine how many each has. This is perhaps more onerous when done manually, but a program is straightforward enough to write, particularly for a specific value. Here is a VBA macro that returns each factor of 8400 and how many factors it has.

Sub GetFactors()
 currrow = 0
 For i2 = 0 To 4
   For i3 = 0 To 1
     For i5 = 0 To 2
       For i7 = 0 To 1
         factorvalue = 2 ^ i2 * 3 ^ i3 * _
           5 ^ i5 * 7 ^ i7
         bucket = (i2 + 1) * (i3 + 1) * _
           (i5 + 1) * (i7 + 1)
         currrow = currrow + 1
         Cells(currrow, 1) = factorvalue
         Cells(currrow, 2) = bucket
       Next i7
     Next i5
   Next i3
 Next i2
End Sub

Notice that this is hard-coded for the specific factors of 8400; a properly robust program would find the prime factors and such. I wrote this to verify my work above (which, it turns out, had some errors) and to find the missing categories. The full counts:

  1. 1
  2. 4
  3. 2
  4. 7
  5. 1
  6. 6
  7. 7
  8. 1
  9. 3
  10. 7
  11. 1
  12. 4
  13. 2
  14. 3
  15. 4
  16. 2
  17. 1
  18. 1
  19. 1
  20. 1
  21. 1

Leave a Reply

Your email address will not be published. Required fields are marked *