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

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.

-
Suppose $f(x)$ is $1$ when $x$ is a square and zero otherwise. We need $\sum_{d|n}f(d)$. But $f$ is multiplicative. So $\sum_{d|n}f(d)=\prod_i(1+f(p_i)+f(p_i^2)+...+f(p_i^{a_i}))$, where $p_1^{a_1}...p_k^{a_k}$ is the factorization of $n$. – Mlazhinka Shung Gronzalez LeWy Jan 3 '14 at 3:17
It is helpful for users to know where the question came from.In this case,simply copying a Brilliant.org NT question without citing the source is unorthodox. – rah4927 Jan 3 '14 at 10:04

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

-
I see what you mean. But you made a mistake, $2^{22}$ does divide the factorial product lol. But I know exactly what you mean, if I choose the elements $p_{15}$ and $p_6$ then $p_{15}p_6=2^{42}$ which clearly doesn't divide the product which means that my thinking here was incorrect. At least my counting was incorrect. Thank you for the explanation. – genius12 Jan 3 '14 at 6:10
Thanks. I corrected the error. – MJD Jan 3 '14 at 14:55

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.

-
The answer is $672$, by the way. – 2012ssohn Jan 3 '14 at 3:21
@2012ssohn: Thanks, I added it. – mathlove Jan 3 '14 at 3:24