Factorials!

If you’ve ever dealt with factorials, you may have felt like yelling, and not because of the exclamation point. Evaluating something like 20! by hand will feel like forever, and you might make a mistake along the way.

20! =1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \cdot 11 \cdot 12 \cdot 13 \cdot 14 \cdot 15 \cdot 16 \cdot 17 \cdot 18 \cdot 19 \cdot 20

You might ask if there a nice formula to evaluate all this multiplication quickly, since there is a nice formula for the sum of all these numbers.

1 + 2 + 3 + 4 + 5 + 6 + 7 +8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 = \frac{1}{2} \cdot 20 \cdot 21 = 210
Or more generally:
\sum\limits_{k=1}^N k = \frac{1}{2} N (N+1)
The reason why this nice addition formula works can be demonstrated with a little geometry. A sum from 1 to N can be arranged like stacked blocks in a triangle (here we’ll go up to 5).

tri1

Then the area of the triangle can be found by taking a twin triangle and fitting it together into a rectangle, then divide by 2 to get the original triangle area (to arrive at 15).

rect1

1+2+3+4+5 = 5\cdot6/2 = 15.
(These sums are called triangular numbers.)

So what about a nice formula for factorials? Well, one was discovered by a happy fellow named Adrien-Marie Legendre (pictured below). It’s called Legendre’s Formula.

Legendre

This formula allows you to express factorials as a product of prime numbers. For example:
10! = 2^8 3^4 5^2 7
This may seem ugly at first, but it is better than chugging through the multiplication to arrive at the long, boring answer of 3628800. Legendre’s formula is faster, and it gives you more information about the number. In any case, you can always evaluate 2^8 3^4 5^2 7 to get 3628800 later. The only caveat to finding N! is knowing all the prime numbers less than or equal to N.

The reason we need the primes is because we want to find the prime factors of N!
Integers are either prime or composite. Composite integers can be broken up into prime factors. For example:
12 = 2\cdot 2\cdot 3
10 = 2\cdot 5
51 = 3\cdot 17
Since a factorial number is definitely composite, it can be broken down into prime factors as well.

Let’s use 10! as our example:
10! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10
We want to find all the prime factors of 10! First, we need to know which prime numbers are factors of 10! To do that is easy, find all the primes less than 10, which are:
{2, 3, 5, 7}
No other primes are needed, since we see all the numbers being multiplied in 10! are 10 and lower. So that is pretty convenient. We know from this that 10! = 2^a 3^b 5^c 7^d. So now we want to find a,b,c and d.

We will start with 2. How many factors of 2 are there in 10! We can start by underlining the multiples of 2 in the factorial:
1 \cdot \underline{2} \cdot 3 \cdot \underline{4} \cdot 5 \cdot \underline{6} \cdot 7 \cdot \underline{8} \cdot 9 \cdot \underline{10}
There are 5 multiples of 2. So make a list of 1 to 5 and find the multiples of 2 in that list:
1, \underline{2}, 3, \underline{4}, 5
There are 2 multiples of 2 in this list. So make a list of 1 to 2 and find multiples of 2 in that list:
1, \underline{2}
There is 1 multiple of 2 in this list, and 1 is less than 2, so we can stop.
We can then sum these numbers from each list:
5 + 2 + 1 = 8
There are 8 factors of 2 in 10!

You might have noticed that this sort of recurring list pattern works because some of the numbers between 1 and 10 have more than 1 factor of 2. For example: 4 has 2, and 8 has 3.
So you could have counted factors of 2 more directly:
1 \cdot \underline{2} \cdot 3 \cdot \underline{\underline{4}} \cdot 5 \cdot \underline{6} \cdot 7 \cdot \underline{\underline{\underline{8}}} \cdot 9 \cdot \underline{10}.
Both methods are equivalent, but the previous one requires less thinking in my opinion.

The same is done with 3, 5 and 7. For 3:
1 \cdot 2 \cdot \underline{3} \cdot 4 \cdot 5 \cdot \underline{6} \cdot 7 \cdot 8 \cdot \underline{9} \cdot 10
1,2,\underline{3}
Count the underlines to see that there are 4 factors of 3 in 10!

For 5:
1 \cdot 2 \cdot 3 \cdot 4 \cdot \underline{5} \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot \underline{10}
There are 2 factors of 5 in 10!

For 7:
1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot \underline{7} \cdot 8 \cdot 9 \cdot 10

Finally, 1 factor of 7 in 10!

So we can then write:
10! = 2^8 3^4 5^2 7

So if this is Legendre’s Formula, there should be a formula, right? What I showed above seems more like an algorithm, but it is equivalent to:

\nu_p (N!) = \sum\limits_{k=1}^\infty  \lfloor \frac{N}{p^k} \rfloor

Where the \lfloor \rfloor brackets are the floor function, which rounds a number downward to the next integer. For example: \lfloor 2.7 \rfloor = 2.
The resulting \nu_p is the exponent for the prime of interest p.
So going back to the 10! example, for p=2:
\nu_2(10!) =  \lfloor \frac{10}{2} \rfloor + \lfloor \frac{10}{4} \rfloor + \lfloor \frac{10}{8} \rfloor + \lfloor \frac{10}{16} \rfloor  + ... = 5+2+1 = 8
Then do the same for p= 3,5, and 7, to arrive at 2^8 3^4 5^2 7 once again.

As a side note: even though this sum technically goes to infinity, any term where p^k > N will be pushed to zero by the floor function.

Now that you know how to quickly evaluate a factorial, try evaluating 20!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s