Finding Prime Factors in Factorials or # of Numbers in Factorials

Finding the Number of Prime Factors in a Factorial

This section details a systematic method for determining the count of a specific prime factor within a given factorial.

Initial Approach and its Limitations

When asked to find the number of a particular prime factor in a factorial (e.g., how many twos are in $8!$), a natural first thought might be to list out the factorial and count the multiples:

• Example: $8!$

  • $8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1$

  • Multiples of $2$: $2, 4, 6, 8$

  • An initial incorrect count might be $4$.

• Why this is incomplete: This simple count overlooks that numbers like $4$ contain more than one factor of $2$ ($4 = 2^2$ has two twos), and $8$ contains even more ($8 = 2^3$ has three twos). A more rigorous system is needed.

Example 1: Finding Twos in $8!$

To find the number of twos in $8!$:

• Multiples of $2^1 = 2$:

  • Numbers: $2, 4, 6, 8$

  • Count: $\lfloor 8/2 \rfloor = 4$

• Multiples of $2^2 = 4$:

  • Numbers: $4, 8$

  • Count: $\lfloor 8/4 \rfloor = 2$

• Multiples of $2^3 = 8$:

  • Numbers: $8$

  • Count: $\lfloor 8/8 \rfloor = 1$

• Multiples of $2^4 = 16$:

  • Numbers: None (since 16 > 8)

  • Count: $\lfloor 8/16 \rfloor = 0$

• Total Number of Twos: $4 + 2 + 1 + 0 = 7$

  • The correct answer is $7$.

Example 2: Finding Threes in $15!$

To find the number of threes in $15!$:

• Multiples of $3^1 = 3$:

  • Numbers: $3, 6, 9, 12, 15$

  • Count: $\lfloor 15/3 \rfloor = 5$

• Multiples of $3^2 = 9$:

  • Numbers: $9$

  • Count: $\lfloor 15/9 \rfloor = 1$

• Multiples of $3^3 = 27$:

  • Numbers: None (since 27 > 15)

  • Count: $\lfloor 15/27 \rfloor = 0$

• Total Number of Threes: $5 + 1 + 0 = 6$

Example 3: Finding Fives in $50!$

This method is especially useful for larger factorials where listing out numbers is impractical.

• Multiples of $5^1 = 5$:

  • Count: $\lfloor 50/5 \rfloor = 10$

• Multiples of $5^2 = 25$:

  • Count: $\lfloor 50/25 \rfloor = 2$

  • (Numbers: $25, 50$)

• Multiples of $5^3 = 125$:

  • Count: $\lfloor 50/125 \rfloor = 0$

• Total Number of Fives: $10 + 2 + 0 = 12$

Application Problem: Maximum Exponent

Question: If $\frac{30!}{3^x}$ is an integer, what is the maximum value of $x$?

• Rephrasing the question: This question is equivalent to asking: "How many threes are there in $30!$?"

• Applying the system for $30!$ and prime $3$:

  • Multiples of $3^1 = 3$:

    • Count: $\lfloor 30/3 \rfloor = 10$

    • (Numbers: $3, 6, 9, 12, 15, 18, 21, 24, 27, 30$)

  • Multiples of $3^2 = 9$:

    • Count: $\lfloor 30/9 \rfloor = 3$

    • (Numbers: $9, 18, 27$)

  • Multiples of $3^3 = 27$:

    • Count: $\lfloor 30/27 \rfloor = 1$

    • (Numbers: $27$)

  • Multiples of $3^4 = 81$:

    • Count: $\lfloor 30/81 \rfloor = 0$

• Total Number of Threes: $10 + 3 + 1 + 0 = 14$

• Conclusion: The maximum value of $x$ is $14$.