Factorials: Special Cases for Prime Factor Counting
Special Cases of Factorial Problems
Introduction to Special Factorial Cases
Factorial problems can appear intimidating initially.
A systematic approach involving breaking down numbers into prime factors simplifies these problems.
This video focuses on three special cases.
Example 1: Finding Nines in
Problem: How many nines are there in ?
Initial Misconception: You might be tempted to simply count multiples of nine (), which would lead to an incorrect answer of .
Key Concept: Break down into its prime factors: . This means that each nine requires two factors of three.
Explanation: Factorials contain many numbers that are multiples of three (, etc.), not just direct multiples of nine. For example, and (which is ) can
Lecture Notes: Factorial Problems and Prime Factorization
Introduction
Factorial problems (n! = 1 × 2 × 3 × … × n) look intimidating at first.
Breaking numbers into prime factors and working step by step makes them simpler.
The goal is usually to find how many times a certain prime factor (or a number made of primes) appears in n!.
Example 1: How many 9’s are in 30!
9 can be written as 3 × 3.
So the real question: how many 3’s are in 30! ?
Count the multiples of 3, then multiples of 9, then multiples of 27.
From 3’s → 10 threes. 30/3 =10
From 9’s → 3 more threes. 30/9=3.333
From 27’s → 1 more three. 30/27=1.111
Total = 14 threes.
Since each 9 needs 2 threes, 14 ÷ 2 = 7.
Answer: 7 nines in 30!
Example 2: How many 77’s are in 300!
77 can be written as 7 × 11.
To find how many 77’s, check how many 7’s and how many 11’s are in 300!.
Multiples of 7 give 42 sevens.
Multiples of 11 give 30 elevens.
Because 30 is less than 42, elevens are the limiting factor.
Answer: 30 seventy-sevens in 300!
Example 3: Maximum power of 24 dividing 517!
24 can be written as 2 × 2 × 2 × 3 (three twos and one three).
First count how many 2’s are in 517! → total of 514 twos.
Then count how many 3’s are in 517! → total of 257 threes.
Each 24 needs three 2’s and one 3.
From 514 twos, we can make 171 groups of three.
From 257 threes, we can make 257 groups of one.
The smaller number is 171, so that is the maximum.
Answer: 24^171 divides 517!
Key Takeaways
Always break the target number into prime factors.
Count how many of each prime shows up in n!.
Divide the counts according to how many of each prime you need.
The smallest count tells you the final answer.
Step-by-Step Method (Slow & Safe)
Break the target number into prime factors.
Example: 24 = 2 × 2 × 2 × 3 (2³ × 3).
Example: 77 = 7 × 11.
For each prime, count how many times it shows up in n!
Divide n by the prime.
Then divide n by the prime², prime³, and so on.
Add up all the results.
Stop when the prime power is larger than n.
Adjust for exponents.
If your number needs more than one copy of a prime, divide the total count by that exponent.
Example: 24 needs 3 twos, so take (count of 2’s ÷ 3).
Take the smallest result.
This is the maximum power of the target number inside n!.
Shortcut Method (Quick Version)
Bigger primes almost always run out first, so they are usually the limiting factor.
For a fast estimate, check the largest prime first.
Then double-check the smaller ones if needed.
Example 1: How many 77’s in 300!
77 = 7 × 11.
Count 7’s: 300 ÷ 7 = 42, 300 ÷ 49 = 6 → total = 48.
Count 11’s: 300 ÷ 11 = 27, 300 ÷ 121 = 2 → total = 29.
Minimum = 29.
Answer: 29 seventy-sevens in 300!
Example 2: Maximum power of 24 in 517!
24 = 2³ × 3.
Count 2’s: 517 ÷ 2 = 258, 517 ÷ 4 = 129, 517 ÷ 8 = 64, 517 ÷ 16 = 32, 517 ÷ 32 = 16, 517 ÷ 64 = 8, 517 ÷ 128 = 4, 517 ÷ 256 = 2 → total = 513.
Count 3’s: 517 ÷ 3 = 172, 517 ÷ 9 = 57, 517 ÷ 27 = 19, 517 ÷ 81 = 6, 517 ÷ 243 = 2 → total = 256.
Adjust for exponents:
2’s: 513 ÷ 3 = 171 groups.
3’s: 256 ÷ 1 = 256 groups.
Minimum = 171.
Answer: 24^171 divides 517!
Key Takeaways
Always split into prime factors.
Count multiples of each prime and their powers.
Divide by exponents if needed.
The smallest number is the final answer