1
$\begingroup$

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.

  • 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 1

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.

  • 0
    And Thanks Thomas. This is what I was looking for.2012-03-20