Earlier than expected I have gotten my results. Using a farm of workstations I have calculated the distances for all cosets in phase 1 of Kociemba's algorithm. As I have conjectured already, the maximal distance is 12. Together with Kloosterman's result for their third and fourth phase (which together form Kociemba's second phase) the upperbound on God's algorithm is now 37. Below follows the set of distances for the first phase: 0: 1 1: 4 2: 74 3: 1230 4: 18056 5: 245902 6: 3082221 7: 34529024 8: 301243996 9: 1209021801 10: 663711855 11: 5238847 12: 109 tot: 2217093120
It took quite a bit of computer time. In all 116 processors in 112 different
machines have cooperated, although not all at the same time %. The maximal
amount of concurrent processing was on 100 processors last night. The
distribution was: 69 Sun's (SS 1, SS 1+, SLC, ELC), 40 SGI's, 1 SGI 4D/310VGX,
5 processors of an SGI 260S compute server and the scalar (SPARC) processor
of an FPS 500. I expect it would have taken one or two hours only on a machine
with 1 GByte of memory. Calculations on the second phase are still out of
the question. Distributing the processing would take much more than 9 times
as much. I expect it would take about a day on a machine with 4 GByte of
I conjecture that the maximal distance in phase 2 is at most 16. There is a
lower bound on it of 14. This would make the upperbound for God's algorithm 28.
% These processors would have been idle most of the time otherwise!
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland