# Even and odd cube positions

0 11 1 0 0 0 12 1 121477 121477 0 13 1 0 0 0 14 1 2981152 2981152 0 15 1 0 0so I only have positions for coset 0 at even depths (12 and 14) and none at odd depths (11, 13 and 15). I get the same for coset 1:

1 11 12 4284 51408 1 12 12 0 0 1 13 12 165274 1983288 1 14 12 0 0 1 15 12 7548786 90585432but now this coset only contributes to odd depths. The same holds true for all 400000 of 5022205 cosets I have already calculated. This seems hardly to be a coincidence. So it looks like that you can classify cube positions as even or odd in the sense that you need an even or odd number of quarter turns to solve it. And more important you only have to look at the edge cube positions to find out which type it is. For me at least it has the effect that going to 16q* I can completely skip half of the cosets, because I already know that they give no contribution. Has no one ever noticed this? Or, which is more likely, have I just never read about it? Are there other classifications like this?

## Comment viewing options

### Odd/Even in the Quarter Turn Metric

Permutations are classified as even or odd depending on whether their decompositions into 2-cycles contain an even or odd number of 2-cycles. Such a decomposition into 2-cycles is not unique. But there is a theorem that states that either all such decompositions contain an even number of 2-cycles or else all such decompositions contain an odd number of 2-cycles.

Quarter turns are odd permutations, so odd permutations must be an odd distance from Start and even permutations must be an even distance from Start in the quarter turn metric. This result obviously doesn't hold in the face turn metric.

The set of even permutations of a group is a subgroup. Typically, for a group G its subgroup of even permutations is called A (i.e., the Alternating group). If G consists entirely of even permutations, then G and A are identical. Otherwise, A is a subgroup of index 2 and there are exactly the same number of even permutations as odd permutations in G. So the number of cube positions that are an even number of moves from Start will be the same as the number of cube positions that are an odd number of moves from Start in the quarter turn metric.

Also, quarter turns are odd in the corners group and also in the edges group. So odd corner positions can only occur with odd edge positions and the same for even positions. Suppose G

_{e}is the edges group and that A

_{e}is the even edges subgroup. Then, the coset associated with a particular corner position x

_{c}may be described as x

_{c}*A

_{e}if x

_{c}is even, and as x

_{c}*(y

_{e}A

_{e}) for some fixed odd y

_{e}if x

_{c}is odd.

### I suspected as much

Well, on the other hand my new code is quite a bit faster than expected. I got rid of symmetry analysis all together. I still use symmetry and only calculate 5022205 cosets instead of 479 million, but I skip the symmetry reduction beyond that. On the plus side it makes the code a lot simpler, while only increasing the size of tabulated positions by about 1%. On the "minus" side I only get the totals right. I still get symmetry reduced numbers, but these are only symmetry reduced in whatever cosets I decide to use. It increases the number of positions I have to store for symmetric cosets, but on the other hand it makes cosets more equal and evens out calculation time between cores.

My 15q* calculation took only about 15 hours (with only 20 minutes differences between cores) on 120 1.9GHz Opteron cores. The results are:

d positions -- --------------- 11 62549615248 12 583570100997 13 5442351625028 14 50729620202582 15 472495678811004verifying the earlier results (at least the totals) by Tom and others.

Now I have to assess how feasible 16q* is. I use more cosets than Tom so I had no memory problems at all for 15q*. My hope to get a two times speedup because I only have to look at half the cosets is probably wrong. I mean I can skip half the cosets, but since they give no contribution they would have been the fast ones. It still saves a lot of CPU Time but nowhere near 50%. On the other hand it doubles the number of positions I have to store for the remaining cosets.

At depth 14 the smallest coset has 65597 and the largest has 2981152 different positions. At depth 15 the smallest has 839930 and the largest has 13034920 different positions (neglecting of course all the cosets with 0 positions). Even if I expect a ten times increase, the largest coset would have 130 million positions and times 4 Bytes would easily fit in 1GB of memory. The numbers suggest only a five times increase, so 16q* looks easy and even 17q* should not be to difficult.

### Opteron cores

more information on what CPU and motherboard? Is it a

collection of single-socket quads, or is it two-socket

boards with quads, or what CPU? Have you measured the

scalability as the core count increases? Are you

multithreading each coset, or are you just assigning each

core a separate coset?

I'd be interested in seeing the code; I'm sure I can learn

some cool tricks from your code. But of course I understand

if you do not wish to share.

### Cray XT6m

For the time being I am just assigning each core a separate coset, which is the easiest and fastest way if each problem can be solved independently on a single core. Since I actually don't multithread, scalability is nearly a non issue. On the other hand I am told that scalability of the machine itself is very good, like Jaguar the No. 1 Top 500 Computer is essentially the same machine just a "few" more racks and a bit older processors.

About sharing the code, I have no problem with that. The code is in C++, the biggest part is a C++ class definition of the cube, which I wrote and spent a little time optimizing for speed. The actual code is surprisingly small. If you don't mind that my comments are mostly in german, I can email it to you right away.

## similar experience