# Why does $\mathrm{ord}_p(n!)=\sum_{i=1}^k a_i(1+p+\cdots+p^{i-1})$?.

Suppose $$n=a_0+a_1p+\cdots+a_kp^k\qquad 0\leq a_i<p$$ is the base $p$ (for $p$ a prime) representation of an integer $n$. I'm trying to prove to myself that $$ord_p(n!)=\sum_{i=1}^k a_i(1+p+\cdots+p^{i-1}).$$

I know the formula that $\displaystyle ord_p(n!)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\cdots$. Substituting the representation of $n$ base $p$, I find something like $$\left\lfloor\frac{a_0}{p}+a_1+\cdots a_kp^{k-1}\right\rfloor+\cdots+\left\lfloor\frac{a_0}{p^k}+\cdots+\frac{a_{k-1}}{p}+a_k\right\rfloor+\left\lfloor\frac{a_0}{p^{k+1}}+\cdots+\frac{a_k}{p}\right\rfloor+\cdots$$ Pulling out the integer terms, this can be rewritten as $$\left\lfloor\frac{a_0}{p}\right\rfloor+\cdots+\left\lfloor\frac{a_0}{p^{k+1}}+\cdots+\frac{a_k}{p}\right\rfloor+\cdots+\sum_{i=1}^k a_i(1+p+\cdots+p^{i-1}).$$

So I have the formula I want at the right, and it amounts to showing that all the terms on the left are actually $0$. For instance, it's clear $\left\lfloor\frac{a_0}{p}\right\rfloor=0$, but I don't know what to do for the other terms. For $\left\lfloor\frac{a_0}{p^2}+\frac{a_1}{p}\right\rfloor$, I can only bound $$\frac{a_0}{p^2}+\frac{a_1}{p}=\frac{a_0+a_1p}{p^2}\leq\frac{p+p^2}{p^2}$$ which doesn't give anything conclusive. How can one conclude the leftmost terms are all $0$ to get the alternative formula?

Edit: I wouldn't mind seeing the alternative with induction on $n$ instead if it's less messy.

-
It's cleaner to do this by induction on $n$. –  Qiaochu Yuan Jun 8 '12 at 3:49
I thought of trying that, using the fact that $ord_p(n!)=ord_p((n-1)!)+ord_p(n)$, but didn't know how to proceed since the expansions of $n-1$ and $n$ could have different coefficients. –  Nastassja Jun 8 '12 at 3:51
Think about adding $1$ in base $p$ and looking carefully at carries. –  Qiaochu Yuan Jun 8 '12 at 19:16

EDIT: It appears the main point of confusion relates to these: $$\left\lfloor \frac{a_0}{p^2} + \frac{a_1}{p} \right\rfloor \leq \left\lfloor \frac{p-1}{p^2} + \frac{p-1}{p} \right\rfloor = \left\lfloor \frac{p^2-1}{p^2} \right\rfloor = 0.$$ $$\left\lfloor \frac{a_0}{p^3} + \frac{a_1}{p^2} + \frac{a_2}{p} \right\rfloor \leq \left\lfloor \frac{p-1}{p^3} + \frac{p-1}{p^2} + \frac{p-1}{p} \right\rfloor = \left\lfloor \frac{p^3-1}{p^3} \right\rfloor = 0.$$

ORIGINAL: Need to be more careful about the floor function. With $$0 \leq a_j \leq p-1, \; \; a_k \neq 0,$$ we get $$\left\lfloor \frac{n}{p} \right\rfloor = a_1 + a_2 p + a_3 p^2 + \cdots + a_k p^{k-1},$$ $$\left\lfloor \frac{n}{p^2} \right\rfloor = a_2 + a_3 p + \cdots + a_k p^{k-2},$$ $$\left\lfloor \frac{n}{p^3} \right\rfloor = a_3 + a_4 p + \cdots + a_k p^{k-3},$$ $$\cdots$$ $$\left\lfloor \frac{n}{p^{k-1}} \right\rfloor = a_{k-1} + a_k p,$$ $$\left\lfloor \frac{n}{p^{k}} \right\rfloor = a_k.$$

So, the coefficient of $a_1$ is $1,$ the total coefficient of $a_2$ is $1+p,$ the total coefficient of $a_3$ is $1+p + p^2,$ and so on. What we get is the sum of $$a_j \frac{p^j - 1}{p - 1}.$$ Let us look at that a little more. $$v_p (n!) = \sum_{j=0}^k a_j \frac{p^j - 1}{p - 1} = \sum_{j=0}^k a_j \frac{p^j }{p - 1} \; - \; \sum_{j=0}^k a_j \frac{1 }{p - 1},$$ $$v_p (n!) = \sum_{j=0}^k \frac{ a_j p^j }{p - 1} - \sum_{j=0}^k \frac{a_j }{p - 1} = \frac{\sum_{j=0}^k a_j p^j }{p - 1} \; - \; \frac{\sum_{j=0}^k a_j }{p - 1}.$$ So, if we name $$S_p(n) = \sum_{j=0}^k a_j,$$ we get $$v_p (n!) = \frac{n }{p - 1} \; - \; \frac{ S_p(n) }{p - 1} = \frac{n - S_p(n) }{p - 1}.$$

Let's see, $v_p$ means the same as $\mbox{ord}_p.$ The $v$ stands for valuation. The quantity $S_p(n)$ can be called the sum of the digits of $n$ when written in base $p.$ So,

$$v_p (n!) \; \; = \; \; \frac{n - S_p(n) }{p - 1}.$$

-
How do you know for instance that $\left\lfloor \frac{n}{p^2} \right\rfloor = a_2 + a_3 p + \cdots + a_k p^{k-2}$? This seems to assume $\left\lfloor\frac{a_0}{p^2}+\frac{a_1}{p}\right\rfloor=0$, and likewise in all the other cases, which is what I felt uneasy about in the first place. –  Nastassja Jun 8 '12 at 4:29
@Nastassja: $a_0+a_1p<p^2$ for the same reason $99<100$, it's built in to how base expansions are defined. –  anon Jun 8 '12 at 4:33
@Nastassja, $$\left\lfloor \frac{a_0}{p^2} + \frac{a_1}{p} \right\rfloor \leq \left\lfloor \frac{p-1}{p^2} + \frac{p-1}{p} \right\rfloor = \left\lfloor \frac{p^2-1}{p^2} \right\rfloor = 0.$$ –  Will Jagy Jun 8 '12 at 4:34
@anon, I get it now, thanks. Thanks Will. –  Nastassja Jun 8 '12 at 4:36

In the section Counting Prime Factors of n! in Prime Multinomial Divisors, it is shown that

If $n=\sum\limits_{j=0}^ka_jp^j$ and $\sigma_p(n)=\sum\limits_{j=0}^ka_j$ is the sum of the base-$p$ digits of $n$, then $$\mathrm{ord}_p(n!)=\frac{n-\sigma_p(n)}{p-1}$$ I think this is the same as the formula you are looking for, but easier on the eye.

Note that \begin{align} \left\lfloor\frac{n}{p^m}\right\rfloor &=\left\lfloor\frac{1}{p^m}\sum_{j=0}^ka_jp^j\right\rfloor\\ &=\left\lfloor\sum_{j=m}^ka_jp^{j-m}\;+\;\frac{1}{p^m}\sum_{j=0}^{m-1}a_jp^j\right\rfloor\\ &=\sum_{j=m}^ka_jp^{j-m}+\left\lfloor\frac{1}{p^m}\sum_{j=0}^{m-1}a_jp^j\right\rfloor\\ &=\sum_{j=m}^ka_jp^{j-m} \end{align} since $\sum\limits_{j=0}^{m-1}a_jp^j<p^m$. That is, even if all the $a_j=p-1$, $\sum\limits_{j=0}^{m-1}(p-1)p^j=p^m-1$.

-
Thanks robjohn. –  Nastassja Jun 8 '12 at 4:36