Could someone be so kind as to explain this little summation to me?

138 Views Asked by At

So basically, the wording in this question, to me, is weird. It goes as follows:

Explain why the following formula gives the power $e$ of a given prime $p$ in $n!$:

$$e = \sum\limits_{i=1}^{\log_pn}\left\lfloor\frac{n}{p^i}\right\rfloor.$$

Take $15!$: this function says $15! = 2^{11}\cdot 3^6\cdot 5^3\cdot 7^2\cdot 13$. This is really interesting, but I have no idea how this little function works. So if someone could give some intuition on that, it'd be much obliged!

4

There are 4 best solutions below

1
On BEST ANSWER

In certain sense, this is a generic way of transforming a sum to something else which is hopefully more manageable. To understand what it is doing, let us look at following figure and count the number of black squares.

$$\begin{array}{cccc|cc} \blacksquare & \square & \square & \square & \rightarrow & 1 \\ \blacksquare & \square & \blacksquare & \square & \rightarrow & 2 \\ \blacksquare & \square & \blacksquare & \blacksquare & \rightarrow & 3 \\ \blacksquare & \blacksquare & \blacksquare & \blacksquare & \rightarrow & 4\\ \hline \downarrow & \downarrow & \downarrow & \downarrow & & \downarrow \\ 4 & 1 & 3 & 2 & \rightarrow & 10 \end{array}$$ One obvious way of counting the black squares is count the number in each column and then sum the result. This gives us $$4 + 1 + 3 + 2 \to 10.$$

Another way is slice the figure horizontally in four layers. Count the number of black squares in each layer and then sum the result. This give us $$1 + 2 + 3 + 4 \to 10\;\text{ again!}$$ The key is no matter which way you count, you get the same number.

Now imagine you pick a prime $p$ and replace the figure above by one with $n$ column and at most $\lfloor \log_p n\rfloor$ layers.

For each integer $k$ between $1$ and $n$, you place $e_k$ black squares into the bottom of $k^{th}$ column where $e_k$ is the exponent of $p$ in the prime factorization of $k$. The total number of black squares will be the number $e$ you are looking for. i.e.

$$e = \sum_{k=1}^n e_k$$

Now slice your figure horizontally and count from bottom to top.

  • On the $1^{st}$ layer (i.e the bottom most layer), the number of black square is the number of integer $k$ which divides $p$. There are $\lfloor \frac{n}{p^1} \rfloor$ of them.

  • On the $2^{nd}$ layer, the number of black sqaure is the number of integer $k$ which divides $p^2$. There are $\lfloor \frac{n}{p^2} \rfloor$ of them.

  • Repeat this procedure to other layers. In general, there will be $\lfloor \frac{n}{p^j} \rfloor$ black squares in the $j^{th}$ layer.

If you add this up, you will get back same number of black squares. This implies:

$$e = \sum_{k=1}^n e_k = \sum_{j=1}^{\log_p n} \left\lfloor \frac{n}{p^j} \right\rfloor$$

0
On

How many numbers in the product $1\cdot 2 \cdots \cdot n$ are divisible by $p$? How many are divisible by $p^2$? $p^3$?

Answer the above questions and it should be more clear. Start with a smaller example than $n=15$. In fact, find the smallest $n$ for which you don't understand why the formula works, and go from there.

0
On

For better intuition, let us work with particular numbers. We want the highest power of $3$ that divides $100!$, that is, $(1)(2)(3)(4)\cdots (99)(100)$.

For any number $k$ from $1$ to $100$, let $e_k$ be the highest power of $3$ that divides $k$. So for example $e_2=0$, $e_{12}=1$, $e_{63}=2$, and $e_{81}=4$. Then $$e=e_1+e_2+e_3+\cdots+e_{99}+e_{100}.$$ To view things more concretely, suppose that each number $k$ has to pay a tax of $e_k$ dollars. Then $e$ is the total tax levied by the taxation authority.

First let us gather a tax of $1$ dollar from each multiple of $3$. We gather a total of $\left\lfloor \frac{100}{3}\right\rfloor$.

Now $3$, $6$, $12$, $15$, $\dots$ have paid what they owe. But $9$, $18$, $27$, $\dots$ still owe money, Let us gather a dollar from each of them. We get $\left\lfloor \frac{100}{9}\right\rfloor$ dollars.

But $27$, $54$, $81$ still owe money. Get a dollar from each. We get $\left\lfloor \frac{100}{27}\right\rfloor$ dollars.

But $81$ is still not fully paid up. We get an additional $\left\lfloor \frac{100}{81}\right\rfloor$ dollars. So the total tax $e$ paid is $$\left\lfloor \frac{100}{3}\right\rfloor+\left\lfloor \frac{100}{9}\right\rfloor+\left\lfloor \frac{100}{27}\right\rfloor+\left\lfloor \frac{100}{81}\right\rfloor.$$

The story is the same for any prime. To see how many terms we will have in the sum, let $p^t$ be the highest power of $p$ which is $\le n$. So $t=\lfloor \log_p(n)\rfloor$. Then the highest amount of tax owed by any number in the interval $1$ to $n$ is $t$, and therefore the sum has $t$ terms.

0
On

Every $p$th integer is divisible by $p$. There are $\left\lfloor\dfrac{n}{p}\right\rfloor$ such numbers $\le n$.

Every $p^2$th integer is divisible by another factor of $p$. There are $\left\lfloor\dfrac{n}{p^2}\right\rfloor$ such numbers $\le n$.

Every $p^3$th integer is divisible by yet another factor of $p$. There are $\left\lfloor\dfrac{n}{p^3}\right\rfloor$ such numbers $\le n$.

And so on. So the total number factors of $p$ in the product of all those numbers (i.e. in $n!$) is $$\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots$$

where the sum is infinite. Fortunately $\left\lfloor\dfrac{n}{p^r}\right\rfloor$ is zero for $r > \log_p n$, so we can truncate the sum there.