# Between 1 and $n!$, how many elements will be there which divides $n!^2$

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.

-
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
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
@Gerry Myerson: Looks like not. –  Chris Eagle Mar 20 '12 at 12:34
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

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.

-
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