# Asymptotic solution for p-adic order of n! for all primes

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

• $\nu_p(n!)=(n-s_p(n))/(p-1)$ where $s_p(n)$ denotes the sum of the $p$-ary digits of $n$. Commented Jun 15, 2015 at 16:14

## 1 Answer

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$.