# Question regarding to canonical factorization of $n!$?

The problem is: write 101! in canonical form.
I solved it by try to find the highest power of each factor prime factor less than 101. When running factor() function using TI-89, I realized that the power of each prime factor decrease. So I guess I have two questions:

1. How can write this idea using Math notation? I'm think of $\prod$ and $\sum$ notation, but I don't know how to express this idea.
2. As a programmer, I want to write a program to handle this situation. I could check every prime factor, however, I'm curious about the decrease of these prime factor. Is there any pattern behind the scene? If there is, it would increase my algorithm a bit.

Update
Based on Aryabhata's answer, my attempt is: $$\prod_{i=1}^{\infty}p_i^{\sum_{k=1}^{\infty} \left\lfloor\frac{n}{p^k}\right\rfloor}$$

Does it make sense?

Thanks.

-
The edit is incorrect. The $\sum$ gives the power of prime $p$ that divides $n!$. So it must be $\prod p^{\sum\dots}$... – Aryabhata Feb 18 '11 at 6:50
@Moron: Thanks. Let me try one more time. – Chan Feb 18 '11 at 6:52
btw, are you doing the project euler (or was it euclid?) programming puzzles? – Aryabhata Feb 18 '11 at 6:52
@Moron: It's not a project, I just read the book and practice some problems. Just my curiosity since I really like expressing Math idea using programming. – Chan Feb 18 '11 at 6:54

You can use Legendre's formula that the highest power of a prime $p$ which divides $n!$ is given by

$$\text{ord}(n,p) = \sum_{k=1}^{\infty} \left\lfloor\frac{n}{p^k}\right\rfloor$$

Note, even though the upper limit says $\displaystyle \infty$, the summation is finite: $\displaystyle \left\lfloor\frac{n}{p^k}\right\rfloor$ is zero when $\displaystyle p^k \gt n$.

In your case, the only primes you need to consider are all in the range $\displaystyle 1 \lt p \le 101$.

You can thus write $n!$ as

$$n! = \prod_{p \le n} p^{\text{ord}(n,p)}$$

where $\displaystyle \text{ord}(n,p)$ is defined as above and $\displaystyle p$ runs through the primes.

-
Thanks, how about the $\prod$? Could I write it in a nested form? – Chan Feb 18 '11 at 6:44
@Chan: I have edited the answer using prod. No clue what you mean by nested form. – Aryabhata Feb 18 '11 at 6:48
Thanks, I see it now. By nested form, I meant combing product and summation. See my update, but I guess it's wrong :P. – Chan Feb 18 '11 at 6:51

First note that the largest prime dividing $N!$ has to be less than or equal to $N$. Let this prime be $p$.

Once you observe this, write $N!$ as a product of primes $N! = 2^{\alpha_2} 3^{\alpha_2} 5^{\alpha_5} 7^{\alpha_7} 11^{\alpha_{11}} \ldots p^{\alpha_p}$ where $\alpha_i \in \mathbb{N}$ and $p$ is the largest prime not exceeding $N$.

Now if you want to find the maximum power of a prime $q$ dividing $N!$, it is given by

$$\alpha_q = \left \lfloor \frac{N}{q} \right \rfloor + \left \lfloor \frac{N}{q^2} \right \rfloor + \left \lfloor \frac{N}{q^3} \right \rfloor + \cdots$$

The first term appears since you want to count the number of terms less than $N$ and are multiples of $q$ and each of these contribute one $q$ to $N!$. But then when you have multiples of $q^2$ you are not adding just one $q$ but you are adding two of these primes $q$ to the product. So you now count the number of multiple of $q^2$ less than $N$ and add and so on and so forth for higher powers of $q$ less than $N$.

-