Prime Factorization of Factorials

In a previous post I wrote how the sum of the integers from one to n could be calculate with the formula 0.5*n*(n+1).  Then I started to wonder if there was something similar for the product of the integers from one to n, or n!, other than just brute force?

By the fundamental theorem of arithmetic n! can be written as it’s prime factorization, which will be the product of all the primes between 1 and n, inclusively, to some power.  The trick is to calculate the powers for each prime number.  Consider the prime factorization of all the numbers from one to n.  It’s obvious than any prime greater than n/2, denote this number k, has a power of one since there will exist no other number between one and n that k will divide.  To write this in a more formal way, let S={2,3,5,7,11,13,…p} be the ordered set of primes which divide n.  S has finite order, m, and p is the largest prime dividing n.  Let R={r1,r2,r3,…,rm} be the set of powers for each prime number.  Then n! factorial can be written as

n!=\prod\limits_{i} s_i^{r_i}=2^{r_1}*3^{r_2}*5^{r_3}*...*p

Here’s an example of how to find 10!.  The prime factors between one and ten are 2, 3, 5, and 7 so S={2,3,5,7}.  Then 10! can be written in the form:

10!=(2^a)*(3^b)*(5^c)*7

First compute two’s power.  There are five numbers between one and ten that two divides into.  These numbers are given 2*1, 2*2, …, 2*5.  Further, two also divides two numbers in the set {1,2,3,4,5}.  These numbers are 2*1 and 2*2.  Continuing in this pattern, there is one number between one and two that two divides into.  Then a=5+2+1=8.

Now look at finding three’s power.  There are three numbers from one to ten that three divides into, and then one number between one and three that three divides into.  Thus b=3+1=4.  In a similar fashion c=2.  Then the set R={8,4,2,1}.  The final answer is:

10!=2^8*3^4*5^2*7

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





%d bloggers like this: