Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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$. –  ABC Jan 3 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 at 10:04

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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 at 6:10
    
Thanks. I corrected the error. –  MJD Jan 3 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.

share|improve this answer
    
The answer is $672$, by the way. –  2012ssohn Jan 3 at 3:21
    
@2012ssohn: Thanks, I added it. –  mathlove Jan 3 at 3:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.