Prime numbers are fascinating. They are the atoms from which all natural numbers are built. Why is it so difficult to tell for certain if an arbitrary number is prime? And even more difficult to split the number into its factors, if it is not prime?
Many questions arise in connection with prime numbers, and many of them are still not answered. In some cases not even a hypothesis exists because there are not enough known examples. It is interesting that everyone who has a computer with an Internet connection can help to extend the known data. Some hints are in the links at the bottom of this page.
Among the many programs I've written so far are some that deal with prime numbers (esp. those that satisfy certain formulas), amicable numbers, Golomb rulers, natural constants (like Pi), and so on.
Since late 1996 I run some number theoretical programs on my site which use up every available CPU cycle. It goes without saying that - not only for this reason - all my computers run 24 hours a day.
The core of my programs is an efficient primality test and factorization function. Although perhaps not optimal, it is able to handle numbers with up to 70 digits in reasonable time. Its strategy can be descibed roughly like this:
The naive method to factorize a number (trial divisons) is much too slow for numbers with more than 12 digits. There are a number of primality tests and factorization algorithms which are better but might not yield a result under certain conditions. This is especially the case if a limit for the running time of the algorithm is given.
An interesting fact is that many primality tests require the factorization of certain auxiliary numbers, and the factorization methods require efficient primality tests (eg. to test the found factors). So they call each other mutually recursively. Fortunately the handled numbers decrease by at least factor 2 with each call, so that the recursion ends (sooner or later :-).
Because of this, my function combines several of these methods in a way so that information which is obtained during earlier calculations can be used in the next calculation. If a trace level > 0 is activated one can see exactly like in this example how the function works. It correctly factors the Carmichael number 999905550669144001 into the three factors 264559, 529117, and 7143067, using an upper bound for trial divisions of only 100. With a larger upper bound (up to a maximum of 10 million) the amount of recursion would be smaller.
My programs run since months without any fault, so they seem to be stable. Additionally there is some protection against calculation errors (Pentium ;-) built in.
In December 1999 I discovered that I could speed up my programs by changing a constant. This unexpectedly (how could I be so naive?) revealed some bugs in my programs. Luckily all of these were guarded by assertions. After some debugging I improved the code, and now everything runs fine again.
Between Jan 16 and Jan 23, 2000 I discovered a pair of Amicable Numbers that was unknown to date:
1640320645088 = 2^5*59*199*4365899 1660299754912 = 2^5*269*349*419*1319
The funny thing about this pair is that some people thought all Amicable Numbers in the range 1012 to 1013 were already known.
In late January 2000 I discovered a chain of four Amicable Numbers that was unknown to date:
1420500714850 = 2*5^2*7*109*37234619 1626780585950 = 2*5^2*13*43*89*653969 1745036416450 = 2*5^2*683*1187*43049 1508297544350 = 2*5^2*29*109*9543167
On Feb 13, 2000 I sped up my programs by another 50% by implementing a better primality test for "small" numbers (smaller than 1012). Also since that time all discoveries are attached an exact time stamp.
On October 16, 2003 I discovered another chain of four Amicable Numbers that was unknown to date:
741158497112 = 2^3*11*71*79*1501561 815660984488 = 2^3*7*53*274818391 965162195672 = 2^3*1637*4481*16447 846136631848 = 2^3*2011*52594271
The funny thing about this one is that I only found out on Jun 30, 2004 that I had discovered this sequence. All the time I hadn't checked the log file!