Math: How many perfect squares are divisors of the product 1! • 2! • 3! • 4! • 5! • 6! • 7! • 8! • 9!?

This is from 2003 AMC (American Mathematics Competitions).

The problem looks like this:

How many perfect squares are divisors of the product 1! • 2! • 3! • 4! • 5! • 6! • 7! • 8! • 9!?

1. 504.
2. 672.
3. 864.
4. 936.
5. 1008.

The exclamation after the number means factorial.

For instance, 3! = 3 • 2 • 1 = 6.

---

Let Us Break the Sequence

The multiplication of that factorial sequence above looks like so:

1 • 1 • 2 • 1 • 2 • 3 • 1 • 2 • 3 • 4 • 1 • 2 • 3 • 4 • 5 • 1 • 2 • 3 • 4 • 5 • 6 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9

🤺

I use middle dot (•) as the multiplication operator (usually ×) to make it consistent with the title above.

---

Perfect Square

It is a number (prime or composite — in this case, a positive integer) with (positive) even exponent (0 is also even).

For example: $2^2$, $6^4$, or $14^0$.

---

Prime It

The sequence above can be grouped into only prime numbers (such as in prime factorisation).

The prime parts are 2, 3, 5, and 7. The others (besides 1) are composites, let them be. We're gonna take just the primes.

We need to construct them into:

$2^a • 3^b • 5^c • 7^d$

This will be useful because later we can find the ones with even exponent (perfect square) much easier.

---

The a (Exponent for 2)

1 • 1 • 2 • 1 • 2 • 3 • 1 • 2 • 3 • 4 • 1 • 2 • 3 • 4 • 5 • 1 • 2 • 3 • 4 • 5 • 6 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9

Take a look the sequence above vertically, and find all numbers which have 2 in them.

For purely number 2, we have 8.

For number 4, we have 6. Since 4 = 2 • 2, then we have another 12 (6 × 2) of 2s.

For number 6, we have 4. Since 6 = 2 • 3, then we have another 4 of 2s.

For number 8, we have 2. Since 8 = 2 • 2 • 2, then we have another 6 (2 × 3) of 2s.

So then, all of probable factors (or the maximum exponent) for 2 is 8 + 12 + 4 + 6 = 30.

a = 30

---

The b (Exponent for 3)

1 • 1 • 2 • 1 • 2 • 3 • 1 • 2 • 3 • 4 • 1 • 2 • 3 • 4 • 5 • 1 • 2 • 3 • 4 • 5 • 6 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9

Let's find all numbers which have 3.

For purely number 3, we have 7.

For number 6, we have 4. Since 6 = 2 • 3, then we have another 4 of 3s.

For number 9, we have 2. Since 9 = 3 • 3, then we have another 4 (2 × 2) of 3s.

So then, total exponent for 3 is 7 + 4 + 2 = 13.

b = 13

---

The c (Exponent for 5)

1 • 1 • 2 • 1 • 2 • 3 • 1 • 2 • 3 • 4 • 1 • 2 • 3 • 4 • 5 • 1 • 2 • 3 • 4 • 5 • 6 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9

Let's find all numbers which have 5.

For purely number 5, we have 5.

That's it, nothing else.

c = 5

---

The d (Exponent for 7)

1 • 1 • 2 • 1 • 2 • 3 • 1 • 2 • 3 • 4 • 1 • 2 • 3 • 4 • 5 • 1 • 2 • 3 • 4 • 5 • 6 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9

Let's find all numbers which have 7.

For purely number 7, we have 3.

d = 3

And that's it.

---

Therefore

1! • 2! • 3! • 4! • 5! • 6! • 7! • 8! • 9! can also be written as:

$2^30 • 3^13 • 5^5 • 7^3$

---

The Perfect Square

We are only interested in the even ones.

• For 2, the exponent is 30, it has 16 even parts: 0, 2, 4, 6, 8, 10, 12, ..., 30.
• For 3, the exponent is 13, it has 7 even parts: 0, 2, 4, 6, 8, 10, 12.
• For 5, the exponent is 5, it has 3 even parts: 0, 2, 4.
• For 7, the exponent is 3, it has 2 even parts: 0, 2.

We can count the even numbers instictively with... thoughts. 😂 Or, we can use the formulation below.

The general formulation is $⌊N/2⌋ + 1$ — where N is the last number of the sequence — to find out how many even numbers in the sequence.

0-30 ➡️ N = 30 ➡️ $⌊30/2⌋ + 1 = 15 + 1 = 16$ ✅

0-12 ➡️ N = 12 ➡️ $⌊12/2⌋ + 1 = 6 + 1 = 7$ ✅

0-4 ➡️ N = 4 ➡️ $⌊4/2⌋ + 1 = 2 + 1 = 3$ ✅

0-2 ➡️ N = 2 ➡️ $⌊2/2⌋ + 1 = 1 + 1 = 2$ ✅

$+1$ because the 0 is included. In mathematics, 0 is an even number.

---

Multiply Even Ones

16 • 7 • 3 • 2 = 672

The answer is 672 (B option). ✅

This means there are 672 perfect square divisors of the given product, each dividing it exactly without leaving a remainder.

Why multiply? Because the pattern involves combining factors multiplicatively, we multiply them. It sounds circular, but hey.

For instance, the multiplication of 2⁴ and 5² is a perfect square that can be used to divide the given product.

As in, (1! • 2! • 3! • 4! • 5! • 6! • 7! • 8! • 9!) divided by the multiplication of $2^4$ and $5^2 = 16 x 25 = 400$ ➡️ $400 = 20^2$ (perfect square, even exponent) ➡️ (1! • 2! • 3! • 4! • 5! • 6! • 7! • 8! • 9!) ➗ 400, will yield no remainder.

Perfect square means all the exponents in its prime factorisation must be even. Therefore, 27 = 3³ is not a perfect square. But 625 = 5⁴ is. And from our expounding above, indeed 625 can also be used to divide the product without leaving a remainder.

---

The solution above can be proven with a smaller sequence.

For example:

• 1! • 2! • 3! ➡️ total of perfect square divisors for the multiplication product is 2 (1 and 4).
• 1! • 2! • 3! • 4! ➡️ total of perfect square divisors for this product is 6 (1, 4, 9, 16, 36, and 144 — we cannot form 25 or 49 or 64 or other from this sequence).
• And so forth...