5
$\begingroup$

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.

  • 0
    @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.2011-02-18

2 Answers 2

11

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.

  • 0
    Thanks, I see it now. By `nested form`, I meant combing product and summation. See my update, but I guess it's wrong :P.2011-02-18
6

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$.