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

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:

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:

Infinite Number Base

If the number base is finite then in base-n there are n^4 possible four digit numbers, and the set has cardinality n^4.  However, what occurs with an infinite number base, and is it even possible to have an infinite number base?

The first task was to find a way to represent every single digit with a unique number from one to infinity (zero is represented by 0).  It  may not be very pragmatic, but it can be done.   Since the number base is infinite there exist no numbers containing more the one digit.  When considering fractions and decimals it can be found that any fraction or decimal is equivalent to zero. Therefore an infinite number base is just equivalent to the set of integers.

This is interesting because the set of numbers base n (finite) with the binary operations of addition and multiplication form a field, but an infinite number base with the binary operations of addition and multiplication forms an integral domain.  Thus computation with an infinite number base is similar to dealing with just the integers in base ten.

Considering the previous problem this means that the set of numbers with four digits with an infinite number base is equal to the null set since no four digit numbers exist.  Thus for any number base the set of numbers four digits long is finite.

Addition Techniques

Let’s say you want to add a set of consecutive natural numbers from 1 to n.  Instead of taking the time to add every number together the sum can be found be using the formula below.

Consider the case where n is even.  Now take the nth number and 1.  Their sum is n+1.  Now shift the numbers by adding one to the lower number and subtracting one from the higher number.  So now (1+1)+(n-1)= n+1 + (1-1) = n+1.  In general, when n is even there are n/2 pairs of numbers which sum up to n+1.  Therefore the sum of natural numbers from 1 to n is 1/2*n*(n+1).

When n is odd take the (n-1)st number and one.  Their sum is n.  Now add one to the lower number and subtract one from the higher number.  Then (1+1) +(n–1) -1 = n + (2-2) = n.  By taking numbers in the sum in pairs there are (n-1)/2 pairs of numbers which sum to n; plus n itself.  Therefore the sum can be written as the sum of (n+1)/2 numbers with a value of n.  Thus, the sum from 1 to n is 1/2*n*(n+1).

Examples:

Sum the numbers from one to ten.  The pairs which sum to eleven are: (1,10), (2,9), (3,8), (4,7), and (5,6).  There are 10/2 = 5 pairs of these numbers.  Therefore, the sum is 1/2*10*11 = 55.

Sum the numbers from one to eleven.  The pairs which sum to eleven are: (1,10), (2,9), (3,8), (4,7), and (5,6).  There are 10/2 = 5 pairs of these numbers, and then there is eleven itself.  Then the sum can be written as 11+11+11+11+11+11 or the sum of (n+1)/2=6 numbers whose value is n.  Therefore, the sum is 1/2*11*12 = 66.

Integral of csc(x) and sec(x)

The integrals of sec(x) and csc(x) can usually be found in tables of integrals, and if all you are looking for is the answer, then here it is:

However, if you would like to know more, then here are the derivations for the integrals broken down step-by-step.  I tried to give as much detail as possible so it would be easy to read and comprehend.

Proof for integral of sec(x).

Proof for integral of csc(x).

Power Series

I began to write a simple calculator program about a week ago, and some of the features I wanted to include were trigonometric functions and exponents/ logarithms.  I found a good place to start was with recursive functions and power series.

Geometric Series, Taylor and Maclaurin Series

The only two ways I know to write a function as a power series are by the manipulation of the geometric series, or by using a Maclaurin series.  I usually don’t use Taylor series because it is simpler to center the series at zero if possible.  By using a geometric series I was able to come up with a function for natural logarithms. The exponential, sine, cosine, and tangent functions are all calculated with a Maclaurin series.

Logarithms

The natural log function comes from the manipulation of the geometric series.

1/(1-x) = ∑x^n = 1 + x + x^2 + x^3 + ...

Start with the derivative of ln(x) which is 1/x.  However we want a series in the form of 1/(1-x).  So to do this just take derivative of ln(1-x).  Integrating the series yields a power series with a radius of convergence of one.

ln(1-a) = (n=1->∞) ∑ a^n/n

At first glance this may appear to be unhelpful for the most part because you can’t compute the natural log of a number greater than one.  There is a trick to this.  First remember this relation ln(1/a) = ln(1) – ln(a) = -ln(a).  So then for all numbers larger than one take the natural log of its reciprocal and then multiply the result by negative one to get the real answer.  Also take notice of the fact the function is the ln(1-a), so set x = 1 – a, and find a.  Then plug a into the series to find the ln(x).  Logarithms can now be found by using natural logs.  This is simple.

log(x)=y or a^y=x    First take the natural log of both sides.
ln(a^y) = ln(x)      Then just rearrage the equation to solve for y.
y*ln(a) = ln(x)
y=ln(x)/ln(a)

Sine, Cosine, Tangent, and exponential functions

All of these functions are found with a Maclaurin series and they converge for all real numbers.  Well of course tangent is undefined when cosine is zero.  The sine and cosine series are as follows:

sin(x) = (n=0->∞) ∑[(-1)^n * x^(2*n+1) / (2*n+1)!]
cos(x) = (n=0->∞) ∑[(-1)^n * x^(2*n)/(2*n)!]

To find the value of tangent of x divide sin(x) by cos(x)  Remember though that asymptotes exist whereever cos(x) is equal to zero.  The last series now is for exponential functions.

exp(x) = (n=0->∞) ∑[x^n/n!]

Update July 5, 2005

I created this pdf using texmacs to help understand geometric series, power series, and taylor/maclaurin series.  I’m assuming that the person reading this document has some knowledge already of what a series is, and how to find where it converges/diverges.

series.pdf