3
$\begingroup$

Suppose we have a fixed (generally composite) $k$, and we want to find the largest power of $k$ that divides $n!$ for $n$ large.

If $k$ is square-free, we need only consider the behavior of the largest prime $p$ dividing $k$: if $p^i | n!$, then certainly $q^i|n!$ for any prime $q<p$, and so $k^i|n!$.

Most of the time, when $k$ is composite, a similar argument is possible and we need only consider a single prime factor of $k$. Legendre's formula for the prime factorization of $n!$ tells us that the highest power of $p$ dividing $n!$ is $$ \sum_{j=1}^\infty \left\lfloor \frac{n}{p^j}\right\rfloor = \frac{n}{p-1} + O(\log n) \, . $$ So, for a fixed prime power $p^a$, the largest power of $p^a$ that divides $n!$ is $\frac{n}{a(p-1)} + o(n)$.

It follows that, if $k=p_1^{a_1}\dots p_n^{a_n}$, then we need only consider those $p_i$ which minimize $a_i(p_i-1)$. Most of the time there will only be one such $p_i$, in which case our life is no harder than it was when $k$ was square-free.

For example, if $k=24$, then we are interested only in the divisibility of $n!$ by the prime powers $8$ and $3$. The above analysis tells us that the largest power of $8$ that divides $n!$ is roughly $\frac{n}{3(2-1)}=\frac{n}{3}$, while the largest power of $3$ that divides $n!$ is roughly $\frac{n}{3-1}=\frac{n}{2}$. So the largest power of $24$ that divides $n!$ is always the same as the largest power of $8$ that divides $n!$, for $n$ sufficiently large.

However, there are exceptions!

For example, if $k=12=2^2 \cdot 3$, then the largest power of both $4$ and $3$ that divides $n!$ will be roughly $\frac{n}{2}$. Numerical experimentation suggests that $n!$ usually has more than twice as many factors of $2$ as it has factors of $3$, but the number of exceptions is large (for $n<10^7$, the factors of $2$ are the scarce ones about $17\%$ of the time, and that number seems to decrease only slowly as $n$ increases).

Can anything be said about which prime factor of $k$ will be the most scarce, in cases where the basic asymptotic analysis given above isn't strong enough?

$\endgroup$
3
$\begingroup$

This comes down to the relative size of the exponents of the primes dividing $n!,$ because your power is limited by the smallest exponent ratio for each prime, the exponent in $n!$ divided by the exponent in your given $k.$

I happen to know that the exponent of prime $p$ in $\operatorname{lcm} (1,2,\ldots,n)$ is proportional to $1 / \log p,$ so that the exponent of $2$ over the exponent of $3$ is approximately $\log 3 / \log 2.$

I'm trying to think if the limiting proportions are the same for factorials, using Legendre's theorem. And i would need to say no. For large $n,$ Legendre's theorem says that the exponent ratio for small primes $p,q$ may be calculated by ignoring the "floor" symbols, giving a limiting exponent ratio of $(q-1)/(p-1).$

So, for each prime factor $p$ of your $k,$ calculate $$ \frac{n}{(p-1) \, a} $$ where $$ p^a \parallel k. $$ The smallest value of this ratio is a good estimate for your biggest power.

$\endgroup$
  • $\begingroup$ Agreed. Unless I'm misunderstanding what you're saying, the limiting proportions in your last sentence are precisely the computation I did in my question, and the fundamental problem is that (unlike in the case of $\operatorname{lcm}$) they wind up being rational. $\endgroup$ – Micah Jan 25 '14 at 23:16
  • 1
    $\begingroup$ @Micah, I see, you do have that in your post. I guess the message is that, when this is not good enough, one must put back the floor signs to get exact ratios. You might try reading articles by Jean-Louis Nicolas and Guy Robin. I'm not sure any by Robin are in English, all French. I am thinking of the papers using superior highly composite numbers and colossally abundant numbers. Robin worked up what he called operations research methods for finding all highly composite numbers between two s.h.c. numbers. Heavy number crunching. $\endgroup$ – Will Jagy Jan 25 '14 at 23:27
  • 2
    $\begingroup$ @Micah, math.univ-lyon1.fr/~nicolas/publications.html $\endgroup$ – Will Jagy Jan 25 '14 at 23:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.