How many perfect squares divide 1!2!3!4!5!6!7!8!9!

Question

What I naturally did was to find the prime factorisation of the product of factorials which is $ 2^{30}3^{13}5^5 7^3 $. Clearly there is 15 unique perfect squares that divide $2^{30}$, 6 unique perfect squares that divide $3^{13}$, 2 unique perfect squares that divide $ 5^5$ and 1 unique perfect square that divides $7^3$. This gives us a total of 24 perfect squares so far. Now we create a set $ A$ of 24 unique elements, where each element represents one of the 24 unique perfect squares. (Note that we have not counted $ 1^2$ as a perfect square that divides the product yet; we'll do this later).

$ S=\{p_1,p_2,p_3,p_4,...,p_{24}\} $

Since we have that the product of any number of perfect squares is also a perfect square, then we have count to the number of ways we can choose $1,2,3,4,...,23,24$ elements from the set since the product of $n$ elements, where $ 1 \le n \le 24$, is also a perfect square. Hence we evaluate:

$ \displaystyle \sum_{n=1}^{24} {24 \choose n}=2^{24}-1 $

Since we still have to count $ 1^2$, we add that in hence the number of perfect squares that divide $ \displaystyle \prod_{n=1}^9n!$ is $ 2^{24}-1+1=\boxed{2^{24}} $.

However this answer is incorrect since the answer is supposed to be an integer in the range $[0,999]$ (inclusive) but my answer is clearly way off. I don't know where I made a mistake and so I'd appreciate any help. Thanks.

Answer 1

You let the $p_i$ be the perfect squares that are powers of 2, 3, 5, and 7, so for example $p_1 = 2^2, p_2 = 2^4, p_6 = 2^{12}, \ldots, p_{16} = 3^2, p_{24} = 7^2$.

Then you said that any product of any of the $p_i$ would be a perfect square (true) which would divide $1!2!3!4!5!6!7!8!9!$ (false). For example, $p_6p_{10} = 2^{12}2^{20} = 2^{32}$ which does not divide $1!2!3!4!5!6!7!8!9!$. Also you double-counted: $p_2p_3 = 2^42^6 = 2^{10}$, but $p_5 = 2^{10}$ also. These are the same divisor, but you counted them separately.

What you need to do is say that a divisor of $1!2!3!4!5!6!7!8!9!$ is a product of at most one of the powers of 2, at most one of the powers of 3, and so on. You don't need to concern yourself with $p_2p_4 = 2^42^8$ say, because you already are considering $2^42^8 = 2^{12}$ when you consider $p_6$.

When making up a divisor of $1!2!3!4!5!6!7!8!9!$, you 16 choices for how many 2's are in the divisor (could be no 2s, or 2 or 4 or … or 30), 7 choices for how many 3's (no 3's, or 2 or 4 or …), 3 choices for how many 5's, and 2 choices for how many 7's, so the answer is $$16\cdot7\cdot3\cdot 2 = 672.$$

Answer 2

The perfect square can be represented as $$2^a3^b5^c7^d$$ where each of $a,b,c,d$ is even.

For example, $a$ has $16$ possibilities as $a=0,2,4,\cdots, 28, 30.$

Since you can choose any even in each letter, the answer will be $$16\times 7\times 3\times 2=672.$$

In general, the number of the perfect square which divide $${p_1}^{a_1}{p_2}^{a_2}\cdots {p_k}^{a_k}$$ will be $$\left({\left\lfloor \frac{a_1}{2}\right\rfloor}+1\right) \left({\left\lfloor \frac{a_2}{2}\right\rfloor}+1\right) \cdots \left({\left\lfloor \frac{a_k}{2}\right\rfloor}+1\right).$$

Here, $p_1\lt p_2\lt\cdots\lt p_k$ are prime numbers.