# God's Algorithm out to 16q*

d (mod M + inv)* positions -- -------------- ---------------- 0 1 1 1 1 12 2 5 114 3 17 1068 4 135 10011 5 1065 93840 6 9650 878880 7 88036 8221632 8 817224 76843595 9 7576845 717789576 10 70551288 6701836858 11 657234617 62549615248 12 6127729821 583570100997 13 57102780138 5442351625028 14 532228377080 50729620202582 15 4955060840390 472495678811004 16 46080486036498 4393570406220123

^{*}The (mod M + inv) column means symmetry reduced postions but only considering the edge cube positions. I just included it because I had those numbers. It is not comparable to earlier calculations because it may include duplicate positions of the full cube and is dependent on what cosets are used in the calculation.

Compared to my 14f* calculation I have switched to symmetry reduced edge cube positions as cosets. Instead of 934778 cosets I had 5022205 cosets to calculate. For the final results I used my combination method, but got rid of symmetry reduction inside the inner loop, and I tabulated symmetry reduced (but only considering edge cubes) positions up to 10 quarter turn moves. The final calculation took 36 and a half hours on 576 1.9 GHz Opteron cores.

Switching to edge cube positions as cosets made this calculation actually easy. On average you would expect that the positions in each cosets are reduced to one fifth. While this is certainly true on average, as both choices must give the same number of positions, the real problems are the cosets with the largest number of positions because they are the ones you have to fit into memory. I have no real numbers for 16q* only that my smallest coset had 9333371 positions (ignoring the ones with 0 positions) and the largest coset had 95678272 positions. Times 4 Bytes I need to store every position this is less than 400 MBytes for each coset.

I have better numbers for 14f* to show how big the impact really is. In my previous calculation using fixed corner cubes and twist as cosets, the smallest coset had 3394915 and the largest had 1121466975 different positions at 14 moves. If I had skipped on symmetry reduction this would have been 32656704 for the smallest and 1846987309 for the largest coset. After redoing the 14f* calculation (it is about 17% finished) the smallest so far has 11610701 and the largest has 35758291 positions. Chances are (because the largest seems to be the first the fully symmetric coset) this is actually the largest coset. So the largest number of positions in a coset is reduced by a factor of nearly 52 along with the memory consumption to store the positions.

All in all fixed edge cube positions are much better suited for this kind of calculation, because the distribution of positions on cosets is more even. Using these cosets 15f* and 17q* look doable if I find the time (CPU-time that is).