Some of you may have followed an exchange in the comments on my weblog a few weeks back about the end of the ShareCal experiment (which I had been conducting for 2 years using the idle time on many computers where I work).  For those of you who missed that, here's an e-mail I sent around the office about it that summarizes it nicely...

My friends:

It is with mixed emotions that I announce the end of the ShareCal experiment. My research attracted the attention of a real number theorist (Jens Kruse Andersen) whose mathematical knowledge FAR exceeds my own. Using C and the GMP library, he coded up an alternate method for finding prime trees and in a matter of minutes found a tree of depth 24 (whereas I, with my meagre mathematical knowledge have spent 2+ years trying to find a tree with depth 23.)

I'd like to thank everyone who has helped me by running the distributed ShareCal application, and especially our IT czar and the company for allowing me to run my experiment on company hardware. Those of you who are still running the ShareCal client can disable it now, I'll be shutting down the dispatcher today.

My algorithm was pretty much brute force, whereas Jens' algorithm focuses only on offsets which are the most likely to produce primes (by selecting offsets computed from contiguous series of small primes), reducing the search time by many orders of magnitude. To put that in perspective, for the 100,000th prime, ShareCal test every possible inverted tree for each coefficient (i.e. 99,999 tests). Jens' algorithm tests FIVE trees for the 100,000th prime. This means although ShareCal will ultimately find more large trees than Jens' application will, his algorithm hits the sweet spots in rapid succession and tears through the problem space at a rate ShareCal could never achieve.

In 2+ years of runtime (on multiple machines), ShareCal was testing primes in the vicinity of 4.6 million. The D24 tree Jens found was rooted up around 6 million.

Although I am happy to have a solution, I really wanted to be the person to discover it, and after 2 years it's a bit of a let-down to have someone else do it in under an hour. There are two sadder elements here.

1. Any tree of depth N necessarily contains a tree of depth N-1. Jens' D24 tree contains therefore a D23 tree. This D23 tree is rooted at 4.7 million. Which means in a matter of a few weeks, ShareCal (currently testing 4.6 million) would have found this tree for me, and I would have declared the experiment over under much happier circumstances. Irony can be pretty ironic sometimes. (Not to mention that through pushback analysis, which I run on all the largest trees ShareCal returns, I would have found the D24 tree that the D23 tree was contained in.) Boo hoo!
    
2. In order to reduce the problem space ShareCal only looks at inverted trees (first child is smaller than the root). Because Jens' algorithm is so fast, it can look at trees that are not inverted all the way up to the coefficient times the root prime (c*p). By implementing Jens' algorithm in Maple, and using a modified offset (to check more sweet spots) I myself found another D23 tree that Jens missed in about 10 minutes of runtime... it's not inverted, and it is rooted all the way down at 113,209, a number ShareCal churned past almost 2 years ago. ShareCal couldn't see that tree because ShareCal only looks at inverted trees. If I had coded ShareCal to explore all possible trees up to c*p it would have run much much slower but it still would have found the D23 tree a LONG time ago.

So the target is now a D25 tree, but now that a talented number theorist is on the job, I suspect he'll get there long before I do. I'll continue the search on my box at home using Maple and an offset that Jens is not using.

Thanks again everyone.

-- Chuck

Jens did indeed find a D25 tree in short order, and for that and his obvious skill and knowledge in this domain, he has my admiration.  As for me?  I was quite depressed for a few days.  It was not how I imagined the ShareCal experiment ending.  But I got over it.   Jens was very nice and sent me his application so I could continue to search for larger trees.  He even tweaked it to add features I was looking for and sent me two versions optimized for each of the processors sitting on my desk (an Athlon and a P3).  Thanks Jens!

It occurred to me that perhaps I could widen my search parameters and keep track of the deepest tree found for larger and larger coefficients.  As the coefficients get bigger, the trees get smaller.  It's very hard to find deep trees with larger coefficients.  And of course, now that I was empowered with Jens' cool application, I could also attempt to find a D26 tree for the coefficient 2.

Last night, after almost a month of runtime, I finally found a D26 tree:

2n+/-308843535 at 177857809 (Depth: 26, Population: 32)
+--1-----2---3---4---5---6---7---8---9---10--11--12--13--14--15--16--17--18--19--20--21--22--23--24--25--26--27--28--29--30
|  [177857809]
|    - = [46872083]
|    .   + = [402587701]
|    .       + = [1114018937]
|    .           + = [2536881409]
|    .               - = [4764919283]
|    .                   - = [9220995031]
|    .                       + = [18750833597]
|    .                           - = [37192823659]
|    .                               - = [74076803783]
|    .                                   - = [147844764031]
|    .                                       - = [295380684527]
|    .                                           + = [591070212589]
|    .                                               - = [1181831581643]
|    .                                                   + = [2363972006821]
|    .                                                       - = [4727635170107]
|    .                                                       .   + = [9455579183749]
|    .                                                       + = [4728252857177]
|    .                                                           - = [9456196870819]
|    .                                                               + = [18912702585173]
|    .                                                                   + = [37825714013881]
|    .                                                                       + = [75651736871297]
|    .                                                                           + = [151303782586129]
|    .                                                                               + = [302607874015793]
|    .                                                                                   - = [605215439188051]
|    .                                                                                       - = [1210430569532567]
|    .                                                                                       .   - = [2420860830221599]
|    .                                                                                       .       + = [4841721969286733]
|    .                                                                                       + = [1210431187219637]
|    .                                                                                           - = [2420862065595739]
|    + = [664559153]
|        + = [1637961841]
+--1-----2---3---4---5---6---7---8---9---10--11--12--13--14--15--16--17--18--19--20--21--22--23--24--25--26--27--28--29--30

Some time ago I also managed to find a D25 with coefficient 3:

3n+/-95635540 at 1624663 (Depth: 25, Population: 29)
+--1-----2---3---4---5---6---7---8---9---10--11--12--13--14--15--16--17--18--19--20--21--22--23--24--25--26--27--28--29--30
|  [1624663]
|    + = [100509529]
|        - = [205893047]
|        + = [397164127]
|            + = [1287127921]
|                + = [3957019303]
|                    - = [11775422369]
|                        + = [35421902647]
|                            + = [106361343481]
|                                - = [318988394903]
|                                    + = [957060820249]
|                                        + = [2871278096287]
|                                            - = [8613738653321]
|                                            + = [8613929924401]
|                                                - = [25841694137663]
|                                                    + = [77525178048529]
|                                                        + = [232575629781127]
|                                                            + = [697726984978921]
|                                                                + = [2093181050572303]
|                                                                    - = [6279543056081369]
|                                                                        - = [18838629072608567]
|                                                                            - = [56515887122190161]
|                                                                                + = [169547661462206023]
|                                                                                    - = [508642984290982529]
|                                                                                        - = [1525928952777312047]
|                                                                                        .   - = [4577786858236300601]
|                                                                                        .       + = [13733360574804537343]
|                                                                                        + = [1525928952968583127]
|                                                                                            - = [4577786858810113841]
+--1-----2---3---4---5---6---7---8---9---10--11--12--13--14--15--16--17--18--19--20--21--22--23--24--25--26--27--28--29--30

Beyond 4 and 5, I've devoted little time so far to other coefficients, but here is a summary of the current depth records for coefficients 2 to 21: