Highest power of a prime $p$ dividing $N!$

How does one find the highest power of a prime $p$ that divides $N!$ and other related products?

Related question: How many zeros are there at the end of $N!$?

This is being done to reduce abstract duplicates. See Coping with *abstract* duplicate questions. and List of Generalizations of Common Questions for more details.

10 Answers

Largest power of a prime dividing $N!$

In general, the highest power of a prime $p$ dividing $N!$ is given by

$$s_p(N!) = \left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots$$

The first term appears since you want to count the number of terms less than $N$ and are multiples of $p$ and each of these contribute one $p$ to $N!$. But then when you have multiples of $p^2$ you are not multiplying just one $p$ but you are multiplying two of these primes $p$ to the product. So you now count the number of multiple of $p^2$ less than $N$ and add them. This is captured by the second term $\displaystyle \left \lfloor \frac{N}{p^2} \right \rfloor$. Repeat this to account for higher powers of $p$ less than $N$.

Number of zeros at the end of $N!$

The number of zeros at the end of $N!$ is given by $$\left \lfloor \frac{N}{5} \right \rfloor + \left \lfloor \frac{N}{5^2} \right \rfloor + \left \lfloor \frac{N}{5^3} \right \rfloor + \cdots$$ where $\left \lfloor \frac{x}{y} \right \rfloor$ is the greatest integer $\leq \frac{x}{y}$.

To make it clear, write $N!$ as a product of primes $N! = 2^{\alpha_2} 3^{\alpha_2} 5^{\alpha_5} 7^{\alpha_7} 11^{\alpha_{11}} \ldots$ where $\alpha_i \in \mathbb{N}$.

Note that $\alpha_5 < \alpha_2$ whenever $N \geq 2$. (Why?)

The number of zeros at the end of $N!$ is the highest power of $10$ dividing $N!$

If $10^{\alpha}$ divides $N!$ and since $10 = 2 \times 5$, $2^{\alpha} | N!$ and $5^{\alpha} | N!$. Further since $\alpha_5 < \alpha_2$, the highest power of $10$ dividing $N!$ is the highest power of $5$ dividing $N!$ which is $\alpha_5$.

Note that there will be

1. A jump of $1$ zero going from $(N-1)!$ to $N!$ if $5 \mathrel\| N$

2. A jump of $2$ zeroes going from $(N-1)!$ to $N!$ if $5^2 \mathrel\| N$

3. A jump of $3$ zeroes going from $(N-1)!$ to $N!$ if $5^3 \mathrel\| N$ and in general

4. A jump of $k$ zeroes going from $(N-1)!$ to $N!$ if $5^k \mathrel\| N$

where $a \mathrel\| b$ means $a$ divides $b$ and $\gcd\left(a,\dfrac{b}{a} \right)$ = 1.

Largest power of a prime dividing other related products

In general, if we want to find the highest power of a prime $p$ dividing numbers like $\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1)$, $\displaystyle P(N,r)$, $\displaystyle \binom{N}{r}$, the key is to write them in terms of factorials.

For instance, $$\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1) = \frac{(2N)!}{2^N N!}.$$ Hence, the largest power of a prime, $p>2$, dividing $\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1)$ is given by $s_p((2N)!) - s_p(N!)$, where $s_p(N!)$ is defined above. If $p = 2$, then the answer is $s_p((2N)!) - s_p(N!) - N$.

Similarly, $$\displaystyle P(N,r) = \frac{N!}{(N-r)!}.$$ Hence, the largest power of a prime, dividing $\displaystyle P(N,r)$ is given by $s_p(N!) - s_p((N-r)!)$, where $s_p(N!)$ is defined above.

Similarly, $$\displaystyle C(N,r) = \binom{N}{r} = \frac{N!}{r!(N-r)!}.$$ Hence, the largest power of a prime, dividing $\displaystyle C(N,r)$ is given by $$s_p(N!) - s_p(r!) - s_p((N-r)!)$$ where $s_p(N!)$ is defined above.

• In my example, I meant highest power of $12$ that divides $3!$. If $m$ is square-free, then indeed the largest prime that divides $m$ is the obstruction. Commented May 5, 2012 at 1:32
• @AndréNicolas Yes I recognized it. Thanks. For instance, in the highest power of $24$ dividing $10!$ the prime $2$ acts as the bottleneck since $2^3$ divides $24$ whereas only $3^1$ divides $24$ and since $10$ is square-free it works. Is there a generic formula known for composite $m$?
– user17762
Commented May 5, 2012 at 1:36
• One trick that makes computations easier is $$\left\lfloor \dfrac{N}{p^{n+1}} \right\rfloor = \left\lfloor \dfrac{\left\lfloor \dfrac{N}{p^n} \right\rfloor}{p} \right\rfloor$$ Commented Jun 1, 2016 at 8:26

For a number $n$, define $\Lambda(n)=\log p$ if $n=p^k$ and zero elsewhen.

Note that $\log n=\sum\limits_{d\mid n}\Lambda(d)$. If $N=n!$, then $$\log N=\sum_{k=1}^n\log k=\sum_{k=1}^n\sum_{d\mid k}\Lambda (d)=\sum_{d=1}^n \Lambda(d)\left\lfloor \frac nd\right\rfloor$$

Since $\Lambda(d)$ is nonzero precisely when $d$ is a power of a prime and in such case it equals $\log p$, the last sum equals $$\sum_{p}\sum_{k\geqslant 1}\log p \left\lfloor\frac n{p^k}\right\rfloor$$ and this gives $$\nu_p(n!)=\sum_{k\geqslant 1}\left\lfloor\frac n{p^k}\right\rfloor$$ If you write $n$ is base $p$, say $n=a_0+a_1p+\cdots+a_kp^k$, the above gives that $$\nu_p(n!)=\frac{s(n)-n}{1-p}$$ where $s(n)=a_0+\cdots+a_k$.

• Very nice proof with using von Mangoldt function! +1
– RFZ
Commented Jun 9, 2016 at 11:08
• Cool and simple. I think the hardest part is the last equality in the first formula. But it becomes obvious if you change the summation order. Commented Jun 6, 2020 at 10:18

de Polignac's formula named after Alphonse de Polignac, gives the prime decomposition of the factorial $n!$.

• Sometimes the formula is also attributed to Legendre. Commented May 5, 2012 at 4:46

For something completely different, see page 114 of Concrete Mathematics by Graham, Knuth, Patashnik. The highest power of a prime $p$ dividing $n!$ is $n$ minus the sum of the integer digits of $n$ in base $p$, all divided by $p-1$. In Mathematica you would write:

(n-Total[IntegerDigits[n,p]])/(p-1)


Hence, the number of trailing zeros of $n!$ is

(n-Total[IntegerDigits[n,5]])/4


I've found this method to be much faster than the sum of Floor functions...

Walking down the street I realized how to proof the formula in a very simple way. The key idea is to know how many numbers contain a given prime in the exact $$q$$-th power.

Let us denote the set of all numbers up to $$n$$ (inclusive) that are divisible by $$q$$-th power of prime $$p$$ but not divisible by the greater ($$q+1, q+2, ...$$) power of that prime: $$M^p_q(n) := \{ m : m \le n, p^q | m, p^{q+1} \nmid m\}$$ How many numbers in that set? Well, obviously, the number of those that are divisible by $$p^q$$ minus the number of those which are divisible by $$p^{q+1}$$: $$|M^p_q(n)| = \bigg\lfloor \frac{n}{p^q}\bigg\rfloor - \bigg\lfloor \frac{n}{p^{q+1}}\bigg\rfloor$$ OK. Each of the numbers in $$M^p_q$$ gives us the $$q$$-th power of $$p$$ in $$n!$$ so we need just add them all: $$s_p(n!)=\sum_{q=1}^{\infty}q|M^p_q(n)|$$ Which is the desired result.

Define $e_p(n) = s_p(n!),$ as Marvis is using $s_p$ for the highest exponent function...

We get $$e_p(n) = s_p(n!) = \sum_{i \geq 1} \left\lfloor \frac{n}{p^i} \right\rfloor$$

I thought I would prove this by mathematical induction. We need, for any positive integers $m,n,$

LEMMA:

(A) If $n + 1 \equiv 0 \pmod m,$ then $$\left\lfloor \frac{n + 1}{m} \right\rfloor = 1 + \left\lfloor \frac{n}{m} \right\rfloor$$ (B) If $n + 1 \neq 0 \pmod m,$ then $$\left\lfloor \frac{n + 1}{m} \right\rfloor = \left\lfloor \frac{n}{m} \right\rfloor$$

For $n < p,$ we know that $p$ does not divide $n!$ so that $e_p(n) = s_p(n!)$ is $0.$ But all the $\left\lfloor \frac{n}{p^i} \right\rfloor$ are $0$ as well. So the base cases of the induction is true.

Now for induction, increasing $n$ by $1.$ If $n+1$ is not divisible by $p,$ then $e_p(n+1) = e_p(n),$ while part (A) of the Lemma says that the sum does not change.

If $n+1$ is divisible by $p,$ let $s_p(n+1) = k.$ That is, there is some number $c \neq 0 \pmod p$ such that $n+1 = c p^k.$ From the Lemma, part (B), all the $\left\lfloor \frac{n}{p^i} \right\rfloor$ increase by $1$ for $i \leq k,$ but stay the same for $i > k.$ So the sum increases by exactly $k.$ But, of course, $e_p(n+1) = s_p((n+1)!) = s_p(n!) + s_p(n+1) = e_p(n) + k.$ So both sides of the middle equation increase by the same $s_p(n+1) = k,$ completing the proof by induction.

Note that it is not necessary to have $n$ divisible by $p$ to get nonzero $e_p(n).$ All that is necessary is that $n \geq p,$ because we are not factoring $n,$ we are factoring $n!$

Here's a different approach I found while thinking in terms of relating the sum of digits of consecutive numbers written in base $$p$$. Part of the appeal of this approach is you might have at one point learned that there is a connection but don't remember what, this gives a quick way to reconstruct it.

Let's consider $$s_p(n)$$, the sum of digits of $$n$$ in base $$p$$. How does the sum of digits change if we add $$1$$ to it? It usually just increments the last digit by 1, so most of the time,

$$s_p(n+1) = s_p(n)+1$$

But that's not always true. If the last digit was $$p-1$$ we'd end up carrying, so we'd lose $$p-1$$ in the sum of digits, but still gain $$1$$. So the formula in that case would be,

$$s_p(n+1) = s_p(n) + 1 - (p-1)$$

But what if after carrying, we end up carrying again? Then we'd keep losing another $$p-1$$ term. Every time we carry, we leave a $$0$$ behind as a digit in that place, so the total number of times we lose $$p-1$$ is exactly the number of $$0$$s that $$n+1$$ ends in, $$v_p(n+1)$$.

$$s_p(n+1) = s_p(n) + 1 - (p-1)v_p(n+1)$$

Now let's rearrange to make the telescoping series and sum over,

$$\sum_{n=0}^{k-1} s_p(n+1) - s_p(n) = \sum_{n=0}^{k-1}1 - (p-1)v_p(n+1)$$ $$s_p(k) = k - (p-1) \sum_{n=0}^{k-1}v_p(n+1)$$

Notice that since $$v_p$$ is completely additive so long as $$p$$ is a prime number,

$$s_p(k) = k - (p-1) v_p\left(\prod_{n=0}^{k-1}(n+1)\right)$$

$$s_p(k) = k - (p-1) v_p(k!)$$

This rearranges to the well-known Legendre's formula,

$$v_p(k!) = \frac{k-s_p(k)}{p-1}$$

• WOW! Not bad. Though I would recommend you to add the parentheses in order to show what are the terms in the summations. It's a bit confusing. BTW. It's funny that you gave the answer to this old question almost at the same time as I did. Commented Jun 6, 2020 at 10:31

$$s_{p}(n!)=\sum_{i=1}^{\infty}[\frac{n}{p^i}]$$

Since $$n!$$ is the product of the integers $$1$$ through $$n$$, we have at least one factor of $$p$$ in $$n!$$ for each multiple of $$p$$ in $$\{1,2,\ldots ,n\}$$, of which there are $$[ \frac{n}{p}]$$. Each multiple of $$p^2$$ contributes an additional factor of $$p$$, each multiple of $$p^3$$ contributes yet another factor of $$p$$, etc. Adding up the number of these factors gives the infinite sum for $$s _{p}(n!)$$.

This is essentially a variation on the answer by LRDPRDX.

For each $$k\geq 1$$ let $$M_k$$ denote the set of positive multiples of $$p^k$$, i.e, $$M_k=\{a p^k: a\geq 1 \text{ and } ap^k\leq n\}.$$ Observe that $$M_{k+1}\subset M_k$$, $$M_k=\emptyset$$ for $$k>\lfloor n/(\log p)\rfloor$$ and $$|M_k| = \lfloor p/n^k\rfloor$$.

The $$p$$-adic valuation of $$n!$$ is

\begin{align} &\sum_{i=2}^n \nu_p(i) = \sum_{k=1}^\infty k |\{i\in \{2,\ldots, n\}: \nu_p(i) = k\}| \\&=\sum_{k=1}^\infty k |M_k \setminus M_{k+1}| \\&= \sum_{k=1}^\infty k (|M_k| - |M_{k+1}|) \\&= \sum_{k=1}^\infty k |M_k| - \sum_{k=2}^\infty (k-1)|M_{k}| \\&= \sum_{k=1}^\infty k |M_k| - \sum_{k=1}^\infty (k-1)|M_{k}| \\&= \sum_{k=1}^\infty |M_k| = \sum_{k=1}^\infty \lfloor p/n^k\rfloor. \end{align}

Maximum value of x such that $$\frac{n!}{p^x}\in\mathbb{Z}$$:

$$n!=n(n-1)(n-2)\ldots{}2=n_p q$$, where $$p\mid n_p \land p\nmid q$$ . Therefore: $$\frac{n!}{p^x}\in\mathbb{Z} \Leftrightarrow \frac{n_p}{p^x}\in\mathbb{Z}$$ $$n_p = \prod_{i=1}^kip, \,k = \lfloor \frac{n}{p}\rfloor$$ $$\Updownarrow$$ $$n_p = p^k\prod_{i=1}^ki = p^k k!$$ Let $$\gamma(n!)_p$$ be the function which returns the max value of x. Then: $$\gamma(n!)_p = \lfloor\frac{n}{p}\rfloor + \gamma(\lfloor\frac{n}{p}\rfloor !)_p$$ $$\gamma(0)_p = 0$$ $$\gamma(n)_p$$ can also be interpreted as the sum: $$\sum_{i=1}^m\lfloor \frac{n}{p^i}\rfloor$$ Where m is the largest value of $$x$$ where $$\lfloor\frac{n}{p^x}\rfloor>0$$.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
Highest power of a prime $p$ dividing $N!$

How does one find the highest power of a prime $p$ that divides $N!$ and other related products?

Related question: How many zeros are there at the end of $N!$?

This is being done to reduce abstract duplicates. See Coping with *abstract* duplicate questions. and List of Generalizations of Common Questions for more details.

10 Answers

Largest power of a prime dividing $N!$

In general, the highest power of a prime $p$ dividing $N!$ is given by

$$s_p(N!) = \left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots$$

The first term appears since you want to count the number of terms less than $N$ and are multiples of $p$ and each of these contribute one $p$ to $N!$. But then when you have multiples of $p^2$ you are not multiplying just one $p$ but you are multiplying two of these primes $p$ to the product. So you now count the number of multiple of $p^2$ less than $N$ and add them. This is captured by the second term $\displaystyle \left \lfloor \frac{N}{p^2} \right \rfloor$. Repeat this to account for higher powers of $p$ less than $N$.

Number of zeros at the end of $N!$

The number of zeros at the end of $N!$ is given by $$\left \lfloor \frac{N}{5} \right \rfloor + \left \lfloor \frac{N}{5^2} \right \rfloor + \left \lfloor \frac{N}{5^3} \right \rfloor + \cdots$$ where $\left \lfloor \frac{x}{y} \right \rfloor$ is the greatest integer $\leq \frac{x}{y}$.

To make it clear, write $N!$ as a product of primes $N! = 2^{\alpha_2} 3^{\alpha_2} 5^{\alpha_5} 7^{\alpha_7} 11^{\alpha_{11}} \ldots$ where $\alpha_i \in \mathbb{N}$.

Note that $\alpha_5 < \alpha_2$ whenever $N \geq 2$. (Why?)

The number of zeros at the end of $N!$ is the highest power of $10$ dividing $N!$

If $10^{\alpha}$ divides $N!$ and since $10 = 2 \times 5$, $2^{\alpha} | N!$ and $5^{\alpha} | N!$. Further since $\alpha_5 < \alpha_2$, the highest power of $10$ dividing $N!$ is the highest power of $5$ dividing $N!$ which is $\alpha_5$.

Note that there will be

1. A jump of $1$ zero going from $(N-1)!$ to $N!$ if $5 \mathrel\| N$

2. A jump of $2$ zeroes going from $(N-1)!$ to $N!$ if $5^2 \mathrel\| N$

3. A jump of $3$ zeroes going from $(N-1)!$ to $N!$ if $5^3 \mathrel\| N$ and in general

4. A jump of $k$ zeroes going from $(N-1)!$ to $N!$ if $5^k \mathrel\| N$

where $a \mathrel\| b$ means $a$ divides $b$ and $\gcd\left(a,\dfrac{b}{a} \right)$ = 1.

Largest power of a prime dividing other related products

In general, if we want to find the highest power of a prime $p$ dividing numbers like $\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1)$, $\displaystyle P(N,r)$, $\displaystyle \binom{N}{r}$, the key is to write them in terms of factorials.

For instance, $$\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1) = \frac{(2N)!}{2^N N!}.$$ Hence, the largest power of a prime, $p>2$, dividing $\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1)$ is given by $s_p((2N)!) - s_p(N!)$, where $s_p(N!)$ is defined above. If $p = 2$, then the answer is $s_p((2N)!) - s_p(N!) - N$.

Similarly, $$\displaystyle P(N,r) = \frac{N!}{(N-r)!}.$$ Hence, the largest power of a prime, dividing $\displaystyle P(N,r)$ is given by $s_p(N!) - s_p((N-r)!)$, where $s_p(N!)$ is defined above.

Similarly, $$\displaystyle C(N,r) = \binom{N}{r} = \frac{N!}{r!(N-r)!}.$$ Hence, the largest power of a prime, dividing $\displaystyle C(N,r)$ is given by $$s_p(N!) - s_p(r!) - s_p((N-r)!)$$ where $s_p(N!)$ is defined above.

• In my example, I meant highest power of $12$ that divides $3!$. If $m$ is square-free, then indeed the largest prime that divides $m$ is the obstruction. Commented May 5, 2012 at 1:32
• @AndréNicolas Yes I recognized it. Thanks. For instance, in the highest power of $24$ dividing $10!$ the prime $2$ acts as the bottleneck since $2^3$ divides $24$ whereas only $3^1$ divides $24$ and since $10$ is square-free it works. Is there a generic formula known for composite $m$?
– user17762
Commented May 5, 2012 at 1:36
• One trick that makes computations easier is $$\left\lfloor \dfrac{N}{p^{n+1}} \right\rfloor = \left\lfloor \dfrac{\left\lfloor \dfrac{N}{p^n} \right\rfloor}{p} \right\rfloor$$ Commented Jun 1, 2016 at 8:26

For a number $n$, define $\Lambda(n)=\log p$ if $n=p^k$ and zero elsewhen.

Note that $\log n=\sum\limits_{d\mid n}\Lambda(d)$. If $N=n!$, then $$\log N=\sum_{k=1}^n\log k=\sum_{k=1}^n\sum_{d\mid k}\Lambda (d)=\sum_{d=1}^n \Lambda(d)\left\lfloor \frac nd\right\rfloor$$

Since $\Lambda(d)$ is nonzero precisely when $d$ is a power of a prime and in such case it equals $\log p$, the last sum equals $$\sum_{p}\sum_{k\geqslant 1}\log p \left\lfloor\frac n{p^k}\right\rfloor$$ and this gives $$\nu_p(n!)=\sum_{k\geqslant 1}\left\lfloor\frac n{p^k}\right\rfloor$$ If you write $n$ is base $p$, say $n=a_0+a_1p+\cdots+a_kp^k$, the above gives that $$\nu_p(n!)=\frac{s(n)-n}{1-p}$$ where $s(n)=a_0+\cdots+a_k$.

• Very nice proof with using von Mangoldt function! +1
– RFZ
Commented Jun 9, 2016 at 11:08
• Cool and simple. I think the hardest part is the last equality in the first formula. But it becomes obvious if you change the summation order. Commented Jun 6, 2020 at 10:18

de Polignac's formula named after Alphonse de Polignac, gives the prime decomposition of the factorial $n!$.

• Sometimes the formula is also attributed to Legendre. Commented May 5, 2012 at 4:46

For something completely different, see page 114 of Concrete Mathematics by Graham, Knuth, Patashnik. The highest power of a prime $p$ dividing $n!$ is $n$ minus the sum of the integer digits of $n$ in base $p$, all divided by $p-1$. In Mathematica you would write:

(n-Total[IntegerDigits[n,p]])/(p-1)


Hence, the number of trailing zeros of $n!$ is

(n-Total[IntegerDigits[n,5]])/4


I've found this method to be much faster than the sum of Floor functions...

Walking down the street I realized how to proof the formula in a very simple way. The key idea is to know how many numbers contain a given prime in the exact $$q$$-th power.

Let us denote the set of all numbers up to $$n$$ (inclusive) that are divisible by $$q$$-th power of prime $$p$$ but not divisible by the greater ($$q+1, q+2, ...$$) power of that prime: $$M^p_q(n) := \{ m : m \le n, p^q | m, p^{q+1} \nmid m\}$$ How many numbers in that set? Well, obviously, the number of those that are divisible by $$p^q$$ minus the number of those which are divisible by $$p^{q+1}$$: $$|M^p_q(n)| = \bigg\lfloor \frac{n}{p^q}\bigg\rfloor - \bigg\lfloor \frac{n}{p^{q+1}}\bigg\rfloor$$ OK. Each of the numbers in $$M^p_q$$ gives us the $$q$$-th power of $$p$$ in $$n!$$ so we need just add them all: $$s_p(n!)=\sum_{q=1}^{\infty}q|M^p_q(n)|$$ Which is the desired result.

Define $e_p(n) = s_p(n!),$ as Marvis is using $s_p$ for the highest exponent function...

We get $$e_p(n) = s_p(n!) = \sum_{i \geq 1} \left\lfloor \frac{n}{p^i} \right\rfloor$$

I thought I would prove this by mathematical induction. We need, for any positive integers $m,n,$

LEMMA:

(A) If $n + 1 \equiv 0 \pmod m,$ then $$\left\lfloor \frac{n + 1}{m} \right\rfloor = 1 + \left\lfloor \frac{n}{m} \right\rfloor$$ (B) If $n + 1 \neq 0 \pmod m,$ then $$\left\lfloor \frac{n + 1}{m} \right\rfloor = \left\lfloor \frac{n}{m} \right\rfloor$$

For $n < p,$ we know that $p$ does not divide $n!$ so that $e_p(n) = s_p(n!)$ is $0.$ But all the $\left\lfloor \frac{n}{p^i} \right\rfloor$ are $0$ as well. So the base cases of the induction is true.

Now for induction, increasing $n$ by $1.$ If $n+1$ is not divisible by $p,$ then $e_p(n+1) = e_p(n),$ while part (A) of the Lemma says that the sum does not change.

If $n+1$ is divisible by $p,$ let $s_p(n+1) = k.$ That is, there is some number $c \neq 0 \pmod p$ such that $n+1 = c p^k.$ From the Lemma, part (B), all the $\left\lfloor \frac{n}{p^i} \right\rfloor$ increase by $1$ for $i \leq k,$ but stay the same for $i > k.$ So the sum increases by exactly $k.$ But, of course, $e_p(n+1) = s_p((n+1)!) = s_p(n!) + s_p(n+1) = e_p(n) + k.$ So both sides of the middle equation increase by the same $s_p(n+1) = k,$ completing the proof by induction.

Note that it is not necessary to have $n$ divisible by $p$ to get nonzero $e_p(n).$ All that is necessary is that $n \geq p,$ because we are not factoring $n,$ we are factoring $n!$

Here's a different approach I found while thinking in terms of relating the sum of digits of consecutive numbers written in base $$p$$. Part of the appeal of this approach is you might have at one point learned that there is a connection but don't remember what, this gives a quick way to reconstruct it.

Let's consider $$s_p(n)$$, the sum of digits of $$n$$ in base $$p$$. How does the sum of digits change if we add $$1$$ to it? It usually just increments the last digit by 1, so most of the time,

$$s_p(n+1) = s_p(n)+1$$

But that's not always true. If the last digit was $$p-1$$ we'd end up carrying, so we'd lose $$p-1$$ in the sum of digits, but still gain $$1$$. So the formula in that case would be,

$$s_p(n+1) = s_p(n) + 1 - (p-1)$$

But what if after carrying, we end up carrying again? Then we'd keep losing another $$p-1$$ term. Every time we carry, we leave a $$0$$ behind as a digit in that place, so the total number of times we lose $$p-1$$ is exactly the number of $$0$$s that $$n+1$$ ends in, $$v_p(n+1)$$.

$$s_p(n+1) = s_p(n) + 1 - (p-1)v_p(n+1)$$

Now let's rearrange to make the telescoping series and sum over,

$$\sum_{n=0}^{k-1} s_p(n+1) - s_p(n) = \sum_{n=0}^{k-1}1 - (p-1)v_p(n+1)$$ $$s_p(k) = k - (p-1) \sum_{n=0}^{k-1}v_p(n+1)$$

Notice that since $$v_p$$ is completely additive so long as $$p$$ is a prime number,

$$s_p(k) = k - (p-1) v_p\left(\prod_{n=0}^{k-1}(n+1)\right)$$

$$s_p(k) = k - (p-1) v_p(k!)$$

This rearranges to the well-known Legendre's formula,

$$v_p(k!) = \frac{k-s_p(k)}{p-1}$$

• WOW! Not bad. Though I would recommend you to add the parentheses in order to show what are the terms in the summations. It's a bit confusing. BTW. It's funny that you gave the answer to this old question almost at the same time as I did. Commented Jun 6, 2020 at 10:31

$$s_{p}(n!)=\sum_{i=1}^{\infty}[\frac{n}{p^i}]$$

Since $$n!$$ is the product of the integers $$1$$ through $$n$$, we have at least one factor of $$p$$ in $$n!$$ for each multiple of $$p$$ in $$\{1,2,\ldots ,n\}$$, of which there are $$[ \frac{n}{p}]$$. Each multiple of $$p^2$$ contributes an additional factor of $$p$$, each multiple of $$p^3$$ contributes yet another factor of $$p$$, etc. Adding up the number of these factors gives the infinite sum for $$s _{p}(n!)$$.

This is essentially a variation on the answer by LRDPRDX.

For each $$k\geq 1$$ let $$M_k$$ denote the set of positive multiples of $$p^k$$, i.e, $$M_k=\{a p^k: a\geq 1 \text{ and } ap^k\leq n\}.$$ Observe that $$M_{k+1}\subset M_k$$, $$M_k=\emptyset$$ for $$k>\lfloor n/(\log p)\rfloor$$ and $$|M_k| = \lfloor p/n^k\rfloor$$.

The $$p$$-adic valuation of $$n!$$ is

\begin{align} &\sum_{i=2}^n \nu_p(i) = \sum_{k=1}^\infty k |\{i\in \{2,\ldots, n\}: \nu_p(i) = k\}| \\&=\sum_{k=1}^\infty k |M_k \setminus M_{k+1}| \\&= \sum_{k=1}^\infty k (|M_k| - |M_{k+1}|) \\&= \sum_{k=1}^\infty k |M_k| - \sum_{k=2}^\infty (k-1)|M_{k}| \\&= \sum_{k=1}^\infty k |M_k| - \sum_{k=1}^\infty (k-1)|M_{k}| \\&= \sum_{k=1}^\infty |M_k| = \sum_{k=1}^\infty \lfloor p/n^k\rfloor. \end{align}

Maximum value of x such that $$\frac{n!}{p^x}\in\mathbb{Z}$$:

$$n!=n(n-1)(n-2)\ldots{}2=n_p q$$, where $$p\mid n_p \land p\nmid q$$ . Therefore: $$\frac{n!}{p^x}\in\mathbb{Z} \Leftrightarrow \frac{n_p}{p^x}\in\mathbb{Z}$$ $$n_p = \prod_{i=1}^kip, \,k = \lfloor \frac{n}{p}\rfloor$$ $$\Updownarrow$$ $$n_p = p^k\prod_{i=1}^ki = p^k k!$$ Let $$\gamma(n!)_p$$ be the function which returns the max value of x. Then: $$\gamma(n!)_p = \lfloor\frac{n}{p}\rfloor + \gamma(\lfloor\frac{n}{p}\rfloor !)_p$$ $$\gamma(0)_p = 0$$ $$\gamma(n)_p$$ can also be interpreted as the sum: $$\sum_{i=1}^m\lfloor \frac{n}{p^i}\rfloor$$ Where m is the largest value of $$x$$ where $$\lfloor\frac{n}{p^x}\rfloor>0$$.
user
The content of the passage primarily revolves around the mathematical problem of finding the highest power of a prime \( p \) that divides \( N! \) (the factorial of \( N \)). It also discusses the related problem of determining the number of trailing zeros in \( N! \). The passage provides detailed explanations and formulas for both problems, including the use of the floor function and the sum of digits in base \( p \).

### Analysis:
1. **Mathematical Question**: The passage contains multiple mathematical questions:
   - How to find the highest power of a prime \( p \) dividing \( N! \).
   - How to determine the number of trailing zeros in \( N! \).

2. **Answers Provided**: The passage provides answers to both questions:
   - The highest power of a prime \( p \) dividing \( N! \) is given by:
     \[
     s_p(N!) = \left\lfloor \frac{N}{p} \right\rfloor + \left\lfloor \frac{N}{p^2} \right\rfloor + \left\lfloor \frac{N}{p^3} \right\rfloor + \cdots
     \]
   - The number of