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!?
(A) 504 (B) 672 (C) 864 (D) 936 (E) 1008

The exclamation after the number means factorial.

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

---

Let's 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² or 6⁴ or 14⁰ and such.

---

Prime It

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

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 wanna 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 2's.

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

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

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 3's.

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

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.

And that's it.

d = 3

---

Therefore

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

2 ³⁰ • 3 ¹³ • 5 ⁵ • 7 ³

---

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.

---

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 it is a multiplication combinatoric pattern, so we multiply them.

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

---

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...