Stars among the numbers...

(last update see Golomb ruler search on 22. Apr 2000)


The Mersenne Numbers Database
 
The numbers defined as Mp = 2p- 1 are the Mersenne Numbers, there p means a prime number. If Mpis also a prime number, than it's a Mersenne prime (number). Early discovered in the 18th century by Marin Mersenne, they have gained some fame especially in the last decades, because the highest so far known prime numbers are without exception such Mersenne primes (remark: if the exponent is no prime, than Mpis always also composite).

This has two reasons: first, only numbers of the type of Mersenne or Fermat allow an enormous efficient algorithm to work for checking if they are primes. And the second reason is, that (see below) only the Fermat numbers with the lowest possible exponents are primes, leaving all checked higher ones as composite numbers, and furthermore it's believed, that these are all Fermat primes. Therefore for higher exponents only the Mersenne numbers can be primes - at least today it seems so.

The scheme of checking is called Lucas-Lehmer Test and goes like this: a sequence s of numbers is calculated with 

s(1) = 4, s(n+1) = (s(n)2-2) mod Mp

and finally the answer is, if and only if s(p-1) = 0, then Mp is prime.

Possible factors of Mersenne numbers are all like this: 2k*p + 1, where k >= 1 is any natural number. This helps to factorize composite Mersenne numbers and can also be used to check a number of possible divisors for a Mersenne number with unknown state: because the most not tested Mersenne numbers are composite, this often avoids the necessity to run the Lucas-Lehmer Test in every case. Simply a limited number of possible factors is tested by dividing.

The presented homepage is owned by David Slowinski, who used and uses exclusively the finest super computers of "his" Cray Research Corporation to search for these Mersenne primes. Also a distributed computation approach is used, to combine the power of many computers for this expensive search. This modern, common effort is called GIMPS (Great Internet Mersenne Prime Search). This search has revealed the now highest prime (currently the 38. of Mersenne type) number with more than 2 million digits (!) and prime exponent p=6,972,593 shortly before I typed these lines in, but as formerly it's now also unknown, if any further primes exist between it's predecessor and itself. For example the Mersenne prime with p=110,503 was discovered after the one with p=132,049 - this is simply due to the fact, that not always all consecutive prime exponents are tested. Often simple guessing or random trials are used, because a complete search is much more time consuming and is carried out only for a lower limit at any time.

You can gain all types of statistics about the results and current standings at the above link. Should anyone be interested, than he or she can get assembler code for CPUs Motorola 68000 (16 bit version) and 68030 (32 bit version) for the Lucas-Lehmer Test (embedded in Modula-2 language): number theory programs. Also I hope to write in the near future analog code for the Pentium II. You can get source code at the above site too, of course.

One final remark: it's believed, but yet unproven, that there are infinite many Mersenne primes despite of their scarcity. 

This and other sites about Mersenne primes could be found in a webring, which is now deleted! I wish, that Yahoo would have never taken the aggressive move to absorp the webring.org, because the signs of decay of the formerly highly valuable system are quite clear...


 
 

Fermat Number Overview
 
At a first glance the Fermat numbers seem to be similar to the Mersenne numbers: they have the building formula Fn = 2k + 1 with k = 2n, where n >= 0 is any natural number (0 included). The differences are the addition instead subtraction of 1 respective the power of 2 and, what can easily proved, the only exponents k, which allow Fn to be a prime, are also powers of 2. As I mentioned above, the practical difference is, that n=0 up to 4 delivers the Fermat primes 

F0 = 3, F1 = 5, F2 = 17, F3 = 257 and F4 = 65537

but n >= 5 seems to deliver no more Fermat primes, i.e. all of these are composite! At least this is the majorities opinion, it's also unproven.

Therefore the only question remains, how to factorize them and if there is really no further Fermat prime with n >= 5. A lot of sometimes only partly factorizations is presented. Again two methods are used: possible divisors obey the formula k*2n + 1 and the checking without finding factors is performed with a very similar algorithm to the above described Lucas-Lehmer Test. My own contribution (compare above): number theory programs .
 

Conjectures and Open Questions regarding Numbers
 
The main problems presented at this page are connected with Goldbach's Conjecture: every even number > 2 is the sum of two primes. This sounds easy, but so far no mathematician was able to prove it, despite of believing, that it holds true.

With a modified and adapted version of the Sieve of Eratosthenes you can check considerable ranges of numbers respective obeying this conjecture. But this helps at now nothing to answer the question. This may change, if the various trials of a proof, often delivering a lower limit, below it isn't proved (but above it is, of course), arrive at a acceptable low value of this lower limit, that we are able to close the gap by the above mentioned brute force approach with one or many number crunchers. On that site various links are presented, which lead to more number theoretical pages with broader discussions. An own program example.


 

IBMs personal homepages signGolomb rulers overview   join the search(es)!
 
This is a related, but seemingly somewhat more exotic topic. It has practical applications in interferometry, to get the most information out of a limited number of detectors (positions), seperated by optimal spaces in between. For this reason the best and most desired Golomb rulers are defined as follows: between any of his n marks every difference, which can be calculated respective measured, may occur at most one and the length has to be minimal. A perfect Golomb ruler is one, in which every such difference from 1 to the length of the ruler occurs exactly one time. As far too often also in this case there are very few perfect Golomb rulers: only the ones with length 1 (two marks), 3 (three marks) and 6 (four marks) are perfect ones and it can be proved, that these are all of them, obeying the unavoidable connection of length l and mark number m according  l = m*(m-1)/2 . The case for 5 marks is non-perferct (the perfect length would be 10) and not unique, for there are two different equivalent solutions. Even mirroring is useless, they are essentially different. This problem grows rapidly with the ruler size, and for 10 marks you can witness the existence of one solution of length 55 and at least one for lengths of 58 and greater, but none of the lengths 56 and 57! There seemingly some patterns exist, which reign the ruler properties, but they are not easy to grasp. Other examples for such "solution gaps" are: length 73 for 11 marks, lengths 86 up to 89 for 12 marks and 107 and 108 for 13 marks.

Probably the worst thing about this problem is, that like the Travelling Salesman Problem it is one of the dammit - sorry - and notorious difficult NP problems, for which no efficient methods for exact solutions are so far available and the majority of experts think, there are even none. They feature an exponential and therefore Non-Polynomial growth of required computation time with problem size. That's the reason, why the table is comparatively short.

If somebody is interested (but consider the time consuming algorithmic behaviour!), I have developed a searching program for such Golomb rulers, which is available in C and Modula-2: number theory programs.

Additional second URL: this leads to distributed net, which is a similar effort like SETI@home, but this time for number theoretical and related problems. From there you can download for many platforms a software bundle, which is capable in participating in the distributed Golomb ruler search (ogr) with your computer(s) and also some other efforts, like decoding DES keys (a little dangerous project, I think, because it can severe the security of the widely used DES encoding in the Internet), CSC or RC5 (read there on). If you are like me interested only in one of these (especially ogr), you may choose as configuration after starting the client for the first time ogr as first, and all others (now there are three others, see above) with a :0 appended immediately (without spaces in between!) like DES:0 (or alternatively DES=0), than only the desired project(s) are performed by your computer.


 

back to top     back to main

comments, suggestions, wishes to:  stefan.urbat@apastron.lb.shuttle.de

(URL:  http://www.lb.shuttle.de/apastron/numbers.htm)