Thursday, February 19, 2009

The Prime

One of the most interesting types of numbers is the prime. A prime is a number that is only divisible by itself and one. 1 is the identity and is not considered a prime. The primes under 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97. There are 25 primes under 100, but between 100 and 200, there are 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, only 21 primes. Primes go in no definite pattern, but there is an easy primality test that can be performed by calculator. The is called the sieve of Eratosthenes.

For any integer m, the primality of m can be determined by dividing m by all the primes up to the square root of m. This is because, instead of dividing by every number, you only have to divide by primes, because any other number is already divisible by a prime. You only have to check up to the square root of m, because anything beyond that would be multiplied by a number that was already checked. For example, the number 91 isn't divisible by 2, 3, and 5. But it is divisible by the last prime you have to check, 7. You could keep going, and find that the number was divisible by 13, but this is unnecessary because 91/7 is 13. Therefore, you only need to check numbers up to the square root of m. Since it it obvious to see if a number is divisible by 2 or 5, the only primes after 10 end with either 1, 3, 7, or 9. Using this method, even numbers above 10,000 can be tested for primality by checking only 23 primes!

As the numbers get higher, the number of possible divisors for the prime increases and the number of primes decreases. As said above, from 1-100 there are 25 primes, but from 18800-18900, the same span, there are only 5 primes!

As well as measuring primes, we can also measure the gaps between primes. The first few gaps measure 1, 2, 2, 4, 2, 4, 2, 4, 6... As the primes get higher the gaps also increase. The average gap between primes from 1-100 is 4, found by dividing 100 (the span) by 25 (the number of primes), and the average gap between 100-200 is 4.719. By the time you reach 25000, the average gap is over 10. However, the average gap pails in comparison compared to the huge gaps that occur.

Even though the average gap form 1-100 is 4, the highest gap in that time is 8, between 89 and 97. The next time the record is broken is from 113-127 a 14 number gap! Note that the first gap of exactly 10 isn't until 139-149, so even if a gap is a first occurrence, it doesn't have to be a record gap. So although a gap of 18 arrives at 523 (523-541), there isn't a gap of 16 until 1831. Similarly, a gap of 34 occurs at 1327, and a gap of 32 does not until 5591. By 20,000 the highest prime gap is an amazing 52! For all the first occurrence prime gaps, see here.

For other types of primes, and some of the largest known primes, see here.