The Prime Challenge

This is a deepzoom of the world’s largest known prime number.


Click to watch the DeepZoom in action.

Almost 17 and a half million digits. There are only 2 numbers that will divide in to it. One and itself. It’s incredible to think, that within the sheer vastness of this number, there is no other whole number that will divide in to it.

The record for a hand-calculated prime is 44 digits, in 1951. Before that, the largest known prime was 39 digits – and that record had stood for 75 years. If you use a modern-day computer-based primality proving programme such as Primo, it will give you the answer for that same 44 digit number the very instant you press the enter key.

That same year, 1951, an electronic computer found a 79 digit prime. In 1952, using a Standard Western Automatic Computer, Raphael Robinson found a rash of new primes, even finding 2 on the same day. You can see some of them here in the DeepZoom – primes M607 and M1279.

Those of us with an interest in computer history might recognise the names of the computers that were used over the next few years to discover primes: the Swedish BESK; an IBM 7090, the ILLIAC-2, the IBM360.

Progress continued and of course the sophistication of the computers increased. From the late 70s until 1996, the space was dominated by the Cray Supercomputer, but it’s funny how things took a big jump from the Cray T94 Supercomputer in 1996 with a 378,632 digit discovery to the desktop PC with a Pentium chip calculating a 420,921 digit prime the very same year. It’s incredible to think that Amazon went online in 1995 and back then, we hadn’t even got as far as half a million digits with prime discoveries despite over a decade of supercomputer involvement.

Steady progress has been made since then with a scheme known as the Great Internet Mersenne Prime Search which is essentially a crowd-sourced solution to the problem. A very specific type of prime is searched for, known as a Mersenne Prime, by anybody who’d like to donate the idle time on their computer to the task.

Mersenne Primes are numbers of the form 2p-1, where p is prime. Most of the big discoveries are Mersenne Primes. Using this method leaves huge unexplored areas in the number space between the Mersennes. We have christened these numbers the “Lost Primes”.

This unexplored space is the target of The Prime Challenge……..

There is a problem: the unexplored areas of the number-space. And there are resources to solve the problem – cloud computers running in Windows Azure. They are available free for 30 days, for anybody who’d like to be part of the challenge. Whether you are going to take the BigData or BigCompute approach to solving the problem with your own solution, or just follow the 5-step process, provision some servers to run in the cloud and use some of the free tools used by academics to help you, you might discover the biggest lost-prime and win the challenge.

This means you can take part in this challenge if you want to use the Infrastructure Services (IaaS) or the Platform Services (PaaS) features of Windows Azure. You can take part if you are an IT Pro, a Developer, a maths-head or just somebody interested in maths, science and technology. If you haven’t got a clue how to get started, follow the 5-step process. You have as much chance as anyone of winning the challenge. If you are a BigData maths-head with a view on how to use HDInsight to solve this problem, there’s nothing stopping you either. And if you sit somewhere in between those 2 extremes, you are also catered for – and – you could win.

Prime Numbers:

We all know a prime number is any number greater than one that is divisible only by itself and one. It starts with 2 then 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 and so on. There is no known pattern to the distribution of these numbers other than the prime distribution. Nobody has yet devised a prime prediction algorithm.

Primes are the building blocks of all other numbers. Every number can be uniquely decomposed in to prime numbers in a unique way. For example 2012 is equal to 2 times 2 times 503.

2 and 503 are prime numbers. This notion works with every number. 1 is not a prime number. It’s not a prime because you lose the uniqueness. For example, we can attach as many one as we like in this calculation and not impact the result (1 * 1 * 1 * 1 * 1 * 2 * 2 * 503).

What’s the biggest prime number? 2 and a half thousand years ago, Euclid proved there is no maximum prime. There is an infinite number of primes. But the biggest known prime, the one which is over 17 million digits, is two to the power of fifty seven million, eight hundred and eighty five thousand, one hundred and sixty one - minus 1 (257885161-1).

This is a special number called a Mersenne Prime, named after a 16th Century Monk who was a theologian, philosopher, music theorist and mathematicion, though many disagree about his fame as a mathematician. He wrote a complete list of Mersenne Primes but he’d missed some numbers that were prime and added some that weren’t prime and he thought it was a finite list – which most people disagree with now. The hunt for the largest ever primes tends to concentrate on Mersenne Primes.

In the 17th century Fermat, famous for his last theorem also tried to create a prime prediction formula. He said you take a number, n and you take 2 to the power of n and raise 2 to the power of that and add 1 (Fn=2^2n + 1).

2 to the power 1 is 2, 2 to the power 2 is 4, add one and you get 5 – which is prime.

2 to the power 2 is 4, 2 to the power 4 is 16, add one and you get 17 – which is prime.

2 to the power 3 is 8, 2 to the power 8 is 256, add one and you get 257 – which is prime.

2 to the power 4 is 16, 2 to the power 16 is 65,536, add one and you get 65,537 – which is prime

Remember this was the 17th Century – so checking if the next one is prime will make your eyes water:

2 to the power 5 is 32, 2 to the power 32 is 4 billion, 294 million, 967 thousand, 2 hundred and 96 (4294967296), add one and you get 4 billion, 294 million, 967 thousand, 2 hundred and 97 – is that prime or not? Fermat couldn’t answer that question in the 17th century.

But about a hundred years later, Euler came along and said “4 billion, 294 million, 967 thousand, 2 hundred and 97 is equal to 641 multiplied by 6 million, seven hundred thousand, 4 hundred and seventeen. So it’s not prime.

After that, the numbers get very big very quickly. Computers have since proven that rather a lot of the subsequent Fermat numbers are also not prime. Just because the first few seem to indicate a pattern it doesn’t provide a proof.