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
-
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.
-
0And Thanks Thomas. This is what I was looking for. – 2012-03-20