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.

  • 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.2012-03-20
  • 1
    Do 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
  • 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$ ...)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 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
    Instead of $(2\alpha_{n} + 1)$ should it be $(2\alpha_{k} +1)$.2012-03-20
  • 0
    And Thanks Thomas. This is what I was looking for.2012-03-20