*Premature optimisation is the root of all evil
*

**D. Knuth
**

There's just *something* about prime numbers. They are islands in the sea of integers — pillars of chastity amongst so much promiscuous division, becoming exquisitely rare, but still infinite in number...

Like jewels in... No, quite enough of that. A prime number is just a number that has no factors except itself and one. That is, it is not evenly divisible except by itself and the number one.

This is most easily illustrated by example:

- 6 is divisible by 1, 2, 3 and itself. Not a prime.
- 13 is divisible only by one and itself. A prime!
- 64 is divisible by 1, 2, 4, 8, 16, 32, and itself. Definitely
*not*a prime! - 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, & 97 are all the primes smaller than 100. Try finding factors for them...

By a strange coincidence 173, the street number of my current flat, and 347, the street number of my *previous* flat are also both prime numbers. Totally accidental, I promise. I'm sometimes a little odd, but not *that* much...

As numbers get bigger, primes get rarer. Large primes have to 'resist' division from many more potential factors than do their lesser brethren. Despite that, primes keep popping up no matter how high up the integer food chain you go. Some *really big* prime numbers have been found by mathematicians over the years. The biggest prime found so far is a so-called Mersenne prime.

Glad you asked. Mersenne primes are a small sub-set of ordinary prime numbers that happen to take a special form — a Mersenne prime is an ordinary prime that can also be written as two to the power of another prime (though not all primes work), minus one.

For example, the third Mersenne prime is 2 to the power of five, minus one. Thirty-one.

2^^{5} = 32

32 - 1 = 31

31 is a prime.

They are named after a monk from the 16th century, Marin Mersenne (1588-1648), who defended Galileo and Descartes, first suggested the use of pendulums in clocks, and struggled to expose the pseudo sciences of alchemy and astrology. He discovered Mersenne primes while trying to find a formula that would represent all primes. He failed in that, but his name became attached to these rare primes in any case.

Mersenne primes have become famous because it's relatively easy to calculate whether or not a given number is a Mersenne prime (details...). As a result, the largest, most glamorous, primes found are often Mersenne primes.

The 41st known Mersenne prime, and the largest prime number known to man, was found in May 2004 by the GIMPS project. It is:

299410429404157172089048926340446938257367722975418473547677348600097640221 100741026265865109912320858493344156415212635335213499669984946466002434564 247027257716956426621052611077416379956346589355834130669179364555490042058 951262711810999963071602089591146249605845552251245175040614646796742775814 169877977351895778922652339915229521619514779556831364845026895095824052712 207416118596253594344535443908358061475952581306252393965564387213568808870 109554001647102077512671720670861148470378380158230147594698428563233367938 062853437133547200496603279419358430694076277478477322725968421442213903047 497381792744687785378954139863274105174997747578653752738664908983344134408 505892942859396418378478851802939536123167178004544423712782896000307876370 ... ... 7,234,973 other digits ... ...

The full prime number has 7,235,733 decimal digits. To print it out would require more characters than the complete works of Shakespeare. The number itself is far, far too big to imagine.

Care to be involved with the discovery of the next *world shaking* prime number?

For the several years now I have been donating the unused CPU time of my computers to the 'Great Internet Mersenne Prime Search' (or GIMPS...). Thanks to the untiring efforts of George Woltman, you can too. Point your web browser at www.mersenne.org, and download a program for either Linux or Windows.

The program runs on your computer all the time, but only uses CPU time that no other programs are using, a valuable resource that would otherwise go to waste! You may even win a share of US$100,000 — but the important thing is that you'll be helping add to humanity's store of knowledge, just by donating the CPU cycles that you are not even using...

They are a rather rare bunch. It's interesting to note that the majority have only been found in the computer age (from the 1950s to the present)...

## | Mersenne Prime | Year Discovered | Digits in Prime |

1 | 2^{2}-1 | unknown | 1 |

2 | 2^{3}-1 | unknown | 1 |

3 | 2^{5}-1 | unknown | 2 |

4 | 2^{7}-1 | unknown | 3 |

5 | 2^{13}-1 | 1456 | 4 |

6 | 2^{17}-1 | 1588 | 6 |

7 | 2^{19}-1 | 1588 | 6 |

8 | 2^{31}-1 | 1772 | 10 |

9 | 2^{61}-1 | 1883 | 19 |

10 | 2^{89}-1 | 1911 | 27 |

11 | 2^{107}-1 | 1914 | 33 |

12 | 2^{127}-1 | 1876 | 39 |

13 | 2^{521}-1 | 1952 | 157 |

14 | 2^{607}-1 | 1952 | 183 |

15 | 2^{1,279}-1 | 1952 | 386 |

16 | 2^{2,203}-1 | 1952 | 664 |

17 | 2^{2,281}-1 | 1952 | 687 |

18 | 2^{3,217}-1 | 1957 | 969 |

19 | 2^{4,253}-1 | 1961 | 1,281 |

20 | 2^{4,423}-1 | 1961 | 1,332 |

21 | 2^{9,689}-1 | 1963 | 2,917 |

22 | 2^{9,941}-1 | 1963 | 2,993 |

23 | 2^{11,213}-1 | 1963 | 3,376 |

24 | 2^{19,937}-1 | 1971 | 6,002 |

25 | 2^{21,701}-1 | 1978 | 6,533 |

26 | 2^{23,209}-1 | 1979 | 6,987 |

27 | 2^{44,497}-1 | 1979 | 13,395 |

28 | 2^{86,243}-1 | 1982 | 25,962 |

29 | 2^{110,503}-1 | 1988 | 33,265 |

30 | 2^{132,049}-1 | 1983 | 39,751 |

31 | 2^{216,091}-1 | 1985 | 65,050 |

32 | 2^{756,839}-1 | 1992 | 227,832 |

33 | 2^{859,433}-1 | 1994 | 258,716 |

34 | 2^{1,257,787}-1 | 1996 | 378,632 |

35 | 2^{1,398,269}-1 | 1996 | 420,921 |

36 | 2^{2,976,221}-1 | 1997 | 895,932 |

37 | 2^{3,021,377}-1 | 1998 | 909,526 |

38 | 2^{6,972,593}-1 | 1999 | 2,098,960 |

39^{*} | 2^{13,466,917}-1 | 2001 | 4,053,946 |

40^{*} | 2^{20,996,011}-1 | 2003 | 6,320,430 |

41^{*} | 2^{24,036,583}-1 | 2004 | 7,235,733 |

^{*}It is not yet known if these are in fact the 39th, 40th, and 41st Mersenne primes, as some of the intermediate candidates have not been checked as yet...