After an initial false start I have now calculated the path-lengths in
phase 1 of Kociemba's algorithm.  The figures are as follows:
path	configurations
  0:          1
  1:          4
  2:         50
  3:        592
  4:       7156
  5:      87236
  6:    1043817
  7:   12070278
  8:  124946368
  9:  821605960
 10: 1199128738
 11:   58202444
 12:        476
The figure 50 for path length 2 is easily verified by hand.  I have a list
with information about the configurations requiring a path-length of 12
(actually the paths leading to such a configurations).  As should be true
for each minimal path in phase 1, all paths start and terminate with a
quarter turn of F, R, B or L.

Some details.

Phase 1 of the algorithm brings the cube in the subgroup generated by
[F^2, R^2, B^2, L^2, U, D]. There are in this case 2,217,093,120
(2048 * 2187 * 495) cosets. This can be (and has been) reduced largely
by observing symmetries. In this case rotating the complete cube
along the UD axis by a quarter turn, rotating the cube along the RL
axis by a half turn and mirroring through the FRBL plane reveal
equivalent cosets. Although it is possible to remove *all* cosets that
are equivalent to some canonical coset this was not done. The removal
has only been done for the twists of corner cubes, reducing the factor
2187 to 168, and reducing the number of configurations to be handled to
170,311,680. For each configuration a minimal path was calculated.
This was done starting with an absolute minimum found through the coordinate
axis and through the 2-dimensional coordinate spaces. When a path of that
length was not found the path length was increased and a new attempt was made.
This was done until a path was found. All searches were exhaustive. On
average paths were searched for 3 different lengths (519,177,716 attempts
for 170,311,679 configurations).

The computations were done on a farm of workstations where each workstation
got a portion of the flip dimension (2048 cases of 83,160 configurations).
Computation time for one portion was from 1 to 2 hours (1.5 on average), so
the total computation was about 3000 hours. On a system with enough
memory (50 MByte) it would have taken only 1 hour (this based on experiments
with the corner cubes-only part). It could also have been with a single
processor and a 50 MByte file, in that case CP time would also be about 1
hour, but the I/O time would exceed the 3000 hours very much.

Using this result and the result by Hans Kloosterman the diameter of the
cube group is at most 37. I conjecture the maximal path length in phase 2
of Kociemba's algorithm is 16, although the requirements on computer time
cq. memory do inhibit calculations at this moment (only in memory would be
feasible, but that requires 500 to 1000 MByte and computation time would be
about one day). This figure of 16 would reduce the upperbound of the groups
diameter to 28.

dik
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland
dik@cwi.nl