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.
Between 1 and $n!$, how many elements will be there which divides $n!^2$
1
$\begingroup$
number-theory
-
2I'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. – 2012-03-20
-
1Do you have reason to believe there's a closed form for the answer? It seems like a difficult problem at first sight. – 2012-03-20
-
2@Gerry Myerson: [Looks like not](http://www.cst.cmich.edu/users/graha1sw/Pub/Papers/divfactorial.pdf). – 2012-03-20
-
1Graphth, 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$ ...) – 2012-03-20
-
0@Chris, nice find. One of the authors went to grad school with me, another is currently visiting my university. – 2012-03-20
1 Answers
5
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.
-
0Instead of $(2\alpha_{n} + 1)$ should it be $(2\alpha_{k} +1)$. – 2012-03-20
-
0And Thanks Thomas. This is what I was looking for. – 2012-03-20