Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 10 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.