* A really interesting distributed computing project: Seventeen or Bust
Wouldn’t it be great to have at least a small place in the history of mathematics? The problem is that unless you are very skilled that’s not going to happen, a fact that is obvious when you consider the achievements of the greats in the field. Consider Waclaw Sierpinski, a Polish mathematician, who in 1960 discovered something very interesting.
Sierpinski’s discovery was that there are odd-valued natural numbers, k, called Sierpinski Numbers, that when substituted into the formula k2^n + 1 generate composite numbers, that is, values that aren’t primes, for all natural values of n.
Sierpinski created a proof that showed that there are infinitely many Sierpinski Numbers and went on to create the Sierpinski Problem: “What is the smallest Sierpinski number?”
In 1962, the mathematician John Selfridge proved that 78,557 is a Sierpinski Number and thus conceived of the Selfridge Conjecture: That the value 78,557 is the answer to the Sierpinski Problem.
So how to test this conjecture? This is easier said than done because proving 78,557 really is the smallest Sierpinski Number means that you have to prove that all the odd-valued numbers smaller than 78,557 are not Sierpinski Numbers.
Why does this matter? According to the “The Largest Known Primes–A Summary” on “The Prime Pages” at the University of Tennessee, the mathematician, Carl Friedrich Gauss, wrote in his treatise “Disquisitiones Arithmeticae” in 1801: “The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length… Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.”
Since 1801 we’ve found out that primes are far more useful than being just purely abstract elements of number theory as they are the underpinnings of public-key cryptography, a technology that is crucial to everything from banking to the military.
The only known way find out if the Selfridge Conjecture is true is to use brute force calculation as no one has yet figured out how to solve the problem any other way. A really interesting distributed computing project, Seventeen or Bust, has been responsible for eliminating all but eight of these numbers to date.
Seventeen or Bust entered the picture in March 2002 when there were, as you might guess, 17 candidates for k (4847, 5359, 10223, 19249, 21181, 22699, 24737, 27653, 28433, 33661, 44131, 46157, 54767, 55459, 65567, 67607, 69109) were left. The “or Bust” part of the name comes from the fact that if primes aren’t found in the values generated from the candidate numbers the search will continue forever.
By Dec. 20, 2003, it was found that 44131 x 2^995972+1, 46157 x 2^698207+1, 54767 x 2^1337287+1, 65567 x 2^1013803+1, 69109 x 2^1157446+1, and 5359 x 2^5054502+1 are all primes thus eliminating as candidates the values 44131, 46157, 54767, 65567, 69109, and 5359 respectively.
The seventh candidate 28433 was eliminated Dec. 30, 2002, when it was found that 28433 * 2^7830457 + 1 is prime (the value has 2,357,207 digits and is currently the eighth-largest known prime).
The eighth candidate was found to have a prime, 27653 * 2^9167433 + 1, on June 15, 2005. This value has 2,759,677 digits and is the largest non-Mersenne prime ever discovered and the seventh largest currently known prime of any form. The ninth candidate was found to have a prime, 4847 * 2^3321063 + 1, on Oct. 9, 2005.
We will skip the deeper details of values tested, other than noting the methodology relies on Proth’s Theorem and the Eratosthenes’ Sieve algorithm to eliminate as many values of n from testing as possible. Even so, what you are left with is a huge number of values to be tested and for that a huge amount of computing power is required. This is what the Seventeen or Bust project is all about – using as many people’s extra computing power as possible.
To join Seventeen or Bust you create an account (free) and then download the client side code which runs on Windows, Linux, FreeBSD, and BeOS 4.5/5. This code uses the idle time of your processor to search for primes in a chunk of the set of values of n for a given candidate value of k.
I joined some years ago as member 8,557 (over 12,535 users have joined the project and of those 9,998 have ever submitted work). The project has been running for 1,773 days (as of Feb. 7, 2007) and the minimum size of the next prime to be tested will be 1,919,547 digits in length. My work stats are old because I had to stop running the client because of products I was testing but I plan to join in again.
These user-driven distributed computing projects are not only interesting examples of what can be achieved through collaboration they are also producing some truly valuable results that can have real social value. For a list of currently active user-driven distributed computing projects see the index at DistributedComputing.info.
As an example, just consider folding@home, a project that is attempting to calculate how proteins fold. This is another phenomenally sized mathematical challenge and the benefits are potentially huge leading to better understanding of diseases such as Alzheimer’s, cancer, Huntington’s, Osteogenesis Imperfecta, and Parkinson’s.
Many of these projects deserve your corporate support if at all possible which raises the question of what it would take for your organization to be comfortable running the client code for these projects? Your thoughts on these distributed computing projects would be welcome.
Now I’m going to fire up my Seventeen or Bust client on a few of my machines and keep my fingers crossed that I’ll discover a new prime as it is the only way that I will enter the history of mathematics. Fame is within my grasp …
Editor’s Note: Check out Networkworld.com’s latest feature, Microsoft Subnet
Every day, our editors scour the Web to collect the most interesting and important Microsoft-related blogs, news, discussion forums and security alerts and present them to you on one page. At Microsoft Subnet, readers can create their own blogs and comment on the Microsoft news and issues of the day.
