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.

Between 1 and $n!$, how many elements will be there which divides $n!^2$. How to dervive to the formula or any algorithm. I tried doing different combinations but not arriving to exact solutions.

share|improve this question
2  
I'm not sure what you would accept as an "exact solution". I'm not sure there's a simple, useful answer even for the number of divisors of $n$-factorial. –  Gerry Myerson Mar 20 '12 at 12:26
1  
Do you have reason to believe there's a closed form for the answer? It seems like a difficult problem at first sight. –  joriki Mar 20 '12 at 12:27
2  
@Gerry Myerson: Looks like not. –  Chris Eagle Mar 20 '12 at 12:34
1  
Graphth, no: for example, take $n=3$. How many elements between $1$ and $6$ divide $6^2$? (Maybe you were thinking of $(n!)!$ instead of $n!^2$ ...) –  Théophile Mar 20 '12 at 12:50
    
@Chris, nice find. One of the authors went to grad school with me, another is currently visiting my university. –  Gerry Myerson Mar 20 '12 at 12:57

1 Answer 1

up vote 5 down vote accepted

There is almost certainly no closed form solution.

Let $\tau(n)$ be the number of distinct factors of $n$. For any $N$, the number of factors of $N^2$ between $1$ and $N$ inclusive can be seen by a simple argument to be $\frac{\tau(N^2)+1}{2}$.

So the number you are looking for is: $$\frac{\tau(n!^2)+1}{2}$$

Computing $\tau(n!^2)$ amounts to finding a unique factorization of $n!$: $$n!=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$$

Then $\tau(n!^2)=(2\alpha_1 + 1)(2\alpha_2+1)...(2\alpha_k+1)$

This seems unlikely to have a closed form, but you might be able to come up with some asymptotic formula.

share|improve this answer
    
Instead of $(2\alpha_{n} + 1)$ should it be $(2\alpha_{k} +1)$. –  Manoj R Mar 20 '12 at 13:46
    
Thanks, @ManojR, fixed. –  Thomas Andrews Mar 20 '12 at 14:03
    
And Thanks Thomas. This is what I was looking for. –  Manoj R Mar 20 '12 at 14:16

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.