Let v_p(n) denote the p-adic valuation of n.

The number of times that a prime p appears in all numbers <= n is given by:

$$ \nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor, $$ where [ x ] is the floor function of x

For example I have calculated this expression for some primes in a pull n = 10^6. $$ \nu_2(10^6!) = 999993 $$ $$ \nu_3(10^6!) = 499993 $$ $$ \nu_5(10^6!) = 249998 $$ $$ \nu_7(10^6!) = 166664 $$ and so on

My question

Is there any asymptotic solution for
$$ \nu_p(n!) $$

I would need a general expression for doing an stochastic model.

Thank you

  • 1
    $\begingroup$ $\nu_p(n!)=(n-s_p(n))/(p-1)$ where $s_p(n)$ denotes the sum of the $p$-ary digits of $n$. $\endgroup$ – user72870 Jun 15 '15 at 16:14

Let $k=\lfloor\log_pn\rfloor$. The formula in the question gives an upper bound $$\nu_p(n!)\le\sum_{i=1}^\infty\frac n{p^i}=\frac n{p-1},$$ and a lower bound $$\nu_p(n!)\ge\sum_{i=1}^k\left(\frac n{p^i}-1\right)\ge\frac n{p-1}-1-k,$$ hence asymptotically, $$\nu_p(n!)=\frac n{p-1}+O(\log_pn).$$

With a bit more care, one can compute $$\frac n{p-1}-\log_p(n+1)\le\nu_p(n!)\le\frac{n-1}{p-1},$$ where both bounds are tight: the upper bound is attained when $n$ is a power of $p$, and the lower bound is attained when $n$ is one less than a power of $p$.


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.