From:

~~~ ~~~ Subject:

Distance Number Branching Number Branching Ratio of from of Factor of Factor Cubes to Start Cubes M-Conjugate M-Conjugate Classes Classes 0 1 1 1 12 12.000 1 1.000 12.000 2 114 9.500 5 5.000 22.800 3 1,068 9.368 25 5.000 42.720 4 10,011 9.374 219 8.760 45.712 5 93,840 9.374 1,978 9.032 47.442 6 878,880 9.366 18,395 9.300 47.778 7 8,221,632 9.355 171,529 9.325 47.931 8 76,843,595 9.347 1,601,725 9.338 47.976 9 717,789,576 9.341 14,956,266 9.338 47.993 10 6,701,836,858 9.337 139,629,194 9.336 47.997

Some of you may remember previous results where I calculated equivalence

classes of the form {m'Xmc} for all 48 elements m in M, the set of all

cube rotations and reflections, and for all 24 elements c in C, the set

of all cube rotations. This is effectively calculating M-conjugate classes

for centerless cubes. My previous data bases have contained

representative elements Y for each equivalent class {m'Xmc}. To get

cubes with centers (where rotational orientation makes a difference),

I then calculated Yc for each c in C, forming a matrix indexed by

Y and c.

The previous approach permits a very compact representation of God's

algorithm, and I used it for corners-only cubes and am presently

using it for edges-only cubes. However, I find that the {m'Xmc}

approach does not work well for whole cubes. The problem is that

the matrix is extremely sparse close to Start. With corners-only

or edges-only cube, I can calculate the entire problem. With the

whole cube, I cannot even come close to calculating the whole problem,

and the matrix representation wastes space rather than saving space.

Hence, for whole cubes, I am calculating equivalence classes (which

are M-conjugate classes) of the form {m'Xm} for all 48 elements m in M.

My data base includes a representative element Z for each M-conjugate

class {m'Xm}. This reduces the size of the problem by about 48 times,

and lets me calculate about two more levels of the search tree with the

same level of effort as before.

Just to reiterate some obvious points that have appeared before:

1) X is an arbitrary element of {m'Xm}, but Z is a particular element

of {m'Xm} chosen with a selection function.2) Z is in {m'Xm} and we have {m'Zm} = {m'Xm}.3) |Z| = |X| = |m'Xm| = |m'Zm| for all m in M and for all X in

{m'Xm}. This trivial equivalence is what makes M-conjugate

classes a viable approach for brute force calculation of

God's algorithm.4) Most M-conjugate classes of the form {m'Xm} contain 48 elements.

The size of {m'Xm} can be used as a measure of the symmetry of

X, with |{m'Xm}|=1 for the most symmetric cubes and |{m'Xm}|=48

for the least symmetric cubes. Conversely, Symm(X) is the

set of all m in M such that m'Xm=X. |Symm(X)|=48 for the

most symmetric cubes, |Symm(X)|=1 for the least symmetric cubes,

and |{m'Xm}| * |Symm(X)| = 48 in all cases.5) The ratio of cubes to M-conjugate classes is close to, but not

exactly equal to, 48. The reason the equality is inexact is

symmetry (see item #4 above). The ratio is closer to 48 when

you get further from Start because the proportion of asymmetric

cubes is higher when you are further from Start.

I actually calculated (and previously reported) God's Algorithm directly

through level 8. For levels 9 and 10, I only calculated the number of

M-equivalence classes directly. I then calculated the size of each

M-equivalence class to obtain the number of cubes. This particular data

base has 14 bytes for each cube (actually for each representative element

Z). Hence, 14*139,629,194= 1,954,808,716 bytes are required to store

level 10 (each level is in a separate file). This is about

2 gigabytes of storage, which is quite large, but which is by no means

outrageous.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU

If you don't have time to do it right today, what makes you think you are

going to have time to do it over again tomorrow?