Home »

God's Algorithm out to 15q*

Submitted by rokicki on Sat, 09/19/2009 - 13:56.
I've finally managed to compute God's Algorithm out to 15q*. This took longer than I expected; I had difficulties using multiple cores because occasionally the memory consumption of the concurrently-calculated cosets would exceed my physical RAM; even though this was rare, it happened frequently enough to completely stall the computation. Also, the way memory was allocated and freed led to pretty intense memory fragmentation.

In any case, it is finally done; here are the results. First we have positions at exactly that depth: 

 d   mod M + inv          mod M       positions
-- ------------- -------------- ---------------
 0             1              1               1
 1             1              1              12
 2             5              5             114
 3            17             25            1068
 4           130            219           10011
 5          1031           1978           93840
 6          9393          18395          878880
 7         86183         171529         8221632
 8        802788        1601725        76843595
 9       7482382       14956266       717789576
10      69833772      139629194      6701836858
11     651613601     1303138445     62549615248
12    6079089087    12157779067    583570100997
13   56691773613   113382522382   5442351625028
14  528436196526  1056867697737  50729620202582
15 4921838392506  9843661720634 472495678811004
Next, we have positions at that depth or less: 
 d   mod M + inv          mod M       positions
-- ------------- -------------- ---------------
 0             1              1               1
 1             2              2              13
 2             7              7             127
 3            24             32            1195
 4           154            251           11206
 5          1185           2229          105046
 6         10578          20624          983926
 7         96761         192153         9205558
 8        899549        1793878        86049153
 9       8381931       16750144       803838729
10      78215703      156379338      7505675587
11     729829304     1459517783     70055290835
12    6808918391    13617296850    653625391832
13   63500692004   126999819232   6095977016860
14  591936888530  1183867516969  56825597219442
15 5513775281036 11027529237603 529321276030446
One interesting thing to note is how, in the first table, only those depths where d is divisible by 4 have an odd number of total positions. This pattern holds for the known 16 depths so far. Small puzzle for the reader: show that this is unlikely to hold true for the remaining depths.
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

odding positions

Submitted by brac37 on Mon, 09/21/2009 - 07:12.
The odding position of d=0 is the clean cube. The odding position of d=4 is U2D2. The odding position of d=8 is R2L2F2B2. The odding position of d=12 is U2D2R2L2F2B2. There are 128 odding positions and by solving them, you can determine all parities of positions on a certain depth. Here they are:

D2 L2 R2 D2 U2 L2 R2 U2 (8f*)
F L2 R2 F L2 R2 U2 L R' F2 U' F2 L' R U2 F' (16f*)
D B2 F2 D' U L2 R2 U' (8f*)
R' B2 R2 D U' B D2 U2 F R2 F2 D U' R' (14f*)
B' F' D' U' L' R' B' F' D' U' L' R' (12f*)
F' U2 F' R2 B' U2 F' L R F2 D' L2 U2 R2 B' F R' F2 D' U' (20f)
D' L' R U2 L2 D2 B F D2 R2 U2 L R' U' (14f*)
L2 F2 R2 F' L2 F' L' R D R2 F2 D R2 B' F' R' D U' F' (19f)
D B2 L2 B2 D U' R2 F2 R2 U' (10f*)
L' D2 B F' L2 D' B2 F2 D' R2 B F' L2 R2 U2 R' (16f*)
D2 L2 F2 L2 R2 F2 R2 U2 (8f*)
R' D2 B' F L2 U' L2 B F' U2 R' U2 L2 R2 U2 R' (16f*)
L R D U B F L' R' D' U' B' F' (12f*)
U2 R D2 R2 U2 R' D U' F' U2 R2 F' U2 L R U B F' R' (19f)
B2 R2 B2 D U F2 R2 F2 L' R B' F' L R' (14f*)
R U2 F2 L B2 R' D' U B' R2 D2 F2 R2 F' L' R' U' B F' (19f)
L2 F2 R2 B2 F2 R2 F2 R2 (8f*)
D2 L' D2 U2 L D2 B F' L2 U R2 B F' U2 R' U2 (16f*)
D2 B2 F2 L2 R2 U2 (6f*)
U2 L B2 F2 L' U2 B F' R2 D L2 B' F U2 R' U2 (16f*)
U L' R' B' D2 U2 B' F D2 U2 F L R U' (14f*)
U L2 D L2 F2 D2 L2 U B F' L D U B' D2 R2 F' L R' (19f)
F2 L2 F2 D U B2 R2 F2 L R' B' F' L R' (14f*)
D2 B2 U B2 F2 U B' D' B R U L2 B' F R' U' L' F R' (19f)
L2 R2 D U' L2 R2 D U' (8f*)
L U2 B F' R2 U L2 R2 U' L2 B F' U2 R' (14f*)
B2 F2 L2 R2 D2 U2 (6f*)
L B2 F2 L' U2 B F' R2 D L2 B' F U2 R' (14f*)
F2 R2 F2 D' U' B2 R2 F2 L R' B' F' L R' (14f*)
D2 B2 U2 F U2 F D' U R' D2 F2 R' U2 B F D' L R' F' (19f)
B2 L2 F2 D U F2 L2 F2 L R' B' F' L R' (14f*)
U2 L D2 U2 L U' R' U F L B2 D U' F' L' B' D F' R2 (19f)
D F2 R2 F2 D' U R2 F2 R2 U' (10f*)
F' L2 R2 F' U2 B2 F2 L R' F2 D' B2 L R' U2 F' (16f*)
L2 F2 L2 R2 F2 R2 (6f*)
R' D2 B' F R2 U' L2 R2 U' R2 B F' L2 R2 U2 R' (16f*)
D' L' R D2 L2 U2 B F D2 R2 U2 L R' U' (14f*)
D2 R D2 R2 U2 R' D U' F' U2 R2 F' U2 L R U B F' R' (19f)
F2 L2 F2 D' U' F2 R2 F2 L' R B' F' L R' (14f*)
F' U2 L2 R2 F2 R' D L' B' R' D U' L2 B R U F' U' F' (19f)
D2 U2 (2f*)
L' U2 L2 B' F U L2 R2 D R2 D2 B F' R' (14f*)
D B2 F2 D U' L2 R2 U' (8f*)
D F U2 R' U R F' D U' R B' U' B U2 R' U' (16f*)
D' B2 L2 B2 L' R B F U2 R2 U2 L R' U' (14f*)
R' D2 B2 F2 R2 B D' F R B D' U F2 R' B' U' L U R' (19f)
B2 L2 F2 D' U' B2 L2 F2 L' R B' F' L R' (14f*)
D' B2 U' R2 D' B2 D' B F U2 L' B2 R2 F2 D' U F' U2 L' R' (20f)
L2 R2 D' U L2 R2 D U' (8f*)
L' D2 U2 L D2 B F' L2 U R2 B F' U2 R' (14f*)
B2 F2 L2 R2 (4f*)
R U2 B' F L2 D B2 F2 D U2 L2 B F' U2 R' (15f*)
L R' U2 L2 U2 B F D2 L2 U2 L R' D' U' (14f*)
D2 L2 D2 R D2 R D U' F' U2 R2 F' D2 L R U' B F' R' (19f)
L R D U B' F' L R D' U' B' F' (12f*)
D2 L D2 U2 L U' R' U F L B2 D U' F' L' B' D F' R2 (19f)
U2 L2 R2 D U' L2 R2 D' U' (9f*)
U2 L' D2 U2 L D2 B F' L2 U R2 B F' U2 R' U2 (16f*)
U2 B2 F2 L2 R2 U2 (6f*)
D2 L B2 F2 L' U2 B F' R2 D L2 B' F U2 R' U2 (16f*)
F2 L2 B2 L R' B F U2 R2 U2 L R' D' U' (14f*)
D2 F2 D L2 R2 D B' D' B R U L2 B' F R' U' L' F R' (19f)
B' F' D' U' L R B F D' U' L' R' (12f*)
U2 B2 U B2 F2 U B' D' B R U L2 B' F R' U' L' F R' (19f)
U' B F U2 R2 U2 R2 B' F' R2 U2 R2 U' (13f*)
U L2 D' B2 L2 F2 U' F2 U B' F' L F2 D U' R2 F' L' R' (19f)
U' B F U2 L2 D2 L2 B' F' R2 U2 R2 U' (13f*)
D2 F2 D' L2 R2 U F2 L2 B' F' D2 L' F2 D U' R2 F' L R' (19f)
D B2 L' R B F' D2 F2 L R U2 R2 U' (13f*)
B2 L' R D2 F' D' U' B2 L' B F' L' R F L R U' (17f)
U R2 D' U' B' F' L' R' B' F' R2 U' (12f*)
D2 B' F R F2 L B2 R' D U' F L2 U2 F L' R' U' (17f)
U' F2 D2 F2 L R F2 D2 F2 D2 L' R' U' (13f*)
B D2 F2 U' R' U2 L2 F2 L2 F2 R2 U2 R' U F2 U2 F' (17f)
U' B2 D2 B2 L R F2 U2 F2 D2 L' R' U' (13f*)
U2 B' F L2 D2 B2 L D U F L' R B' F R' B' F' U' F2 (19f)
U L2 D2 L R B F L R D U' R2 U' (13f*)
U' F2 D' R2 D B F' R' F2 U2 R' D U F' L R' (16f*)
D2 U' R2 B' F' L' R' B' F' D' U' R2 U' (13f*)
B F' L' F2 R' B2 L D' U F' R2 U2 F' L R U' (16f*)
L2 D2 L2 B' F' R2 U2 R2 D2 B F D L2 R2 B2 F2 U' (17f)
R2 B' F D2 L' D U F L' R B' F R' U2 B' F' U' (17f)
R2 D2 R2 B' F' R2 D2 R2 D2 B F D L2 R2 B2 F2 U' (17f)
F2 L' R U2 B2 F D U B2 R B F' L' R B' L' R' U' (18f)
F2 D' B2 F2 L2 R2 U' F2 D' U' L' R' B' F' L' R' (16f*)
B F' R2 U2 L' D' U B R2 B L2 R2 F' D2 B' L R' U' (18f)
U2 R2 D B2 F2 L2 R2 U R2 D U' L' R' B' F' L' R' (17f)
U B2 D L2 R2 U' R2 U' B F' L F2 L2 D' U F' L R' (18f)
B2 L' R' B U2 B2 L2 F2 U2 L2 F2 R2 F' L' R' (15f*)
L D2 L2 D B R2 B F2 L2 D2 L2 F' L2 F U' R2 U2 R' (18f)
L2 D' L2 B' R2 B2 F2 D2 U2 R2 F' R2 U' R2 (14f*)
L2 B2 L2 U2 L R' B' D U L B' F L R' F' L' R' U' (18f)
D2 B2 D2 B2 U L2 D2 L R' B' F' L R F2 U' F2 (16f*)
L R' U2 F' D U R B' F L' R F' U2 L' R' U' F2 (17f)
D2 B2 U2 F2 U R2 U2 L R' B' F' L R F2 U' F2 (16f*)
L R' U2 F' D U L' R2 B F' L R' B' U2 L' R' U' F2 (18f)
U' F2 U2 F2 L R F2 U2 F2 U2 L' R' U' (13f*)
D2 U2 B D2 F2 U' R' U2 L2 F2 L2 F2 R2 U2 R' U F2 U2 F' (19f)
U' B2 U2 B2 L R F2 D2 F2 U2 L' R' U' (13f*)
F' D2 B2 U' L' B2 L B2 D2 B2 R B2 R' U' F2 U2 F' (17f)
D B2 U2 B F L2 D2 L' R B F' R2 U' (13f*)
D2 U F2 D' R2 D B F' R' F2 U2 R' D U F' L R' (17f)
U R2 B' F' L' R' B' F' D' U' R2 U' (12f*)
L2 B F' D2 R' D' U' F' L R' B F' R U2 B F U' (17f)
U' B F D2 R2 D2 R2 B' F' R2 D2 R2 U' (13f*)
D2 B2 U' B2 F2 D F2 L2 B' F' D2 L' F2 D U' R2 F' L R' (19f)
U' B F D2 L2 U2 L2 B' F' R2 D2 R2 U' (13f*)
D B2 D' R2 B2 L2 U' L2 D B' F' L F2 D U' R2 F' L' R' (19f)
U L2 U2 L' R' B' F' L' R' D U' R2 U' (13f*)
U2 B' F L D2 L U2 L' D U' F L2 U2 F L' R' U' (17f*)
D2 U' R2 D' U' B' F' L' R' B' F' R2 U' (13f*)
R2 B F' U2 R' D U B L' R B F' R' U2 B' F' U' (17f*)
U' B2 U F2 R2 D2 B2 F2 L2 F2 U2 F2 R2 U' R2 U' (16f)
L2 B F U2 F2 R' B2 F2 L F2 L2 D U' B' U2 L R' F2 U' (19f)
U' B2 U B2 L2 D2 B2 F2 L2 F2 D2 F2 R2 U' R2 U' (16f*)
F' D2 F2 D R' D2 L2 B2 R2 F2 R2 U2 R' U F2 U2 F' (17f)
D B2 F2 L2 R2 U R2 D' U' B' F' L' R' B' F' R2 (16f*)
L' R U2 B' D U R B F' L' R B F2 U2 L' R' U' F2 (18f)
U2 L2 U2 R2 U B2 U2 B' F L' R' B F R2 U' R2 (16f*)
L R' D2 F' D' U' B2 L' B F' L' R F L R U' F2 (17f*)
L2 U2 L2 B' F' R2 D2 R2 U2 B F D L2 R2 B2 F2 U' (17f)
B2 L2 B2 U2 B' F L' D U F L' R B' F R' B' F' U' (18f)
R2 U2 R2 B' F' R2 U2 R2 U2 B F D L2 R2 B2 F2 U' (17f)
L2 B' F U2 L' D U R2 F L' R B' F R' B' F' U' (17f*)
F2 D' B2 F2 L2 R2 U' F2 D U L' R' B' F' L' R' (16f*)
U F2 U B2 F2 D' R2 U' B F' L F2 L2 D' U F' L R' (18f)
D2 R2 D B2 F2 L2 R2 U R2 D U' L' R' B' F' L' R' (17f)
B2 F2 D' F2 U' L2 U B F' L' F2 D2 L' D U F' L R' (18f)
» login or register to post comments

Solution of the odd pattern puzzle

Submitted by mdlazreg on Tue, 09/22/2009 - 08:44.
Michael Reid has calculated all minimal maneuvers of the above list.
It is what he calls X-symmetric positions in his site:

http://www.math.ucf.edu/~reid/Rubik/x_symmetric.html

The minimal maneuvers are as follow for the 128 positions: 

0q* I
4q* U2 D2
8q* F2 B2 R2 L2
12q* F2 B2 U D' F2 B2 U D'
12q* F2 B2 U D' F2 B2 U' D
12q* F2 B2 U D' R2 L2 U D'
12q* F2 B2 U D' R2 L2 U' D
12q* F2 R2 F2 B2 R2 B2
12q* F B U D R2 L2 U D F B
12q* F B U D R L F B U D R L
12q* F B U D R L F' B' U' D' R' L'
12q* F B U D R' L' F B U' D' R' L'
12q* F B U D R' L' F' B' U D R L
12q* U2 D2 F2 B2 R2 L2
12q* U2 F2 B2 R2 L2 D2
12q* U2 F2 B2 R2 L2 U2
14q* U D F2 B2 U D' F2 B2 D2
14q* U D F2 B2 U D' F2 B2 U2
14q* U F2 R L F B R L U D F2 U'
14q* U F2 R' L' F' B' R' L' U' D' F2 U'
14q* U F B R L F B R' L' F' B' R' L' U'
14q* U F B R' L' F B R' L' F B R' L' U'
14q* U F' B' R L F' B' R L F' B' R L U'
14q* U F' B' R' L' F' B' R L F B R L U'
14q* U F B R L U' D' F B U' D' F' B' U'
14q* U F B R' L' U D F' B' U D F' B' U'
16q* F2 R2 F2 B2 R2 B2 U2 D2
16q* F2 R L' D2 F2 D2 R' L F2 D2
16q* F B U D R L F B U D R L U2 D2
16q* F B U D R L F' B' U' D' R' L' U2 D2
16q* F B U D R' L' F B U' D' R' L' U2 D2
16q* F B U D R' L' F' B' U D R L U2 D2
16q* F B U D R' L' U2 F B U D R' L' D2
16q* F B U D R' L' U2 F' B' U' D' R L D2
16q* F B U D R' L' U2 F B U D R' L' U2
16q* F B U D R' L' U2 F' B' U' D' R L U2
16q* F R' B R' L U' R L' U B R L' D' B' L F'
16q* U F2 U D' F' B' R' L' F' B' D2 B2 U'
16q* U F2 U D' F B R L F B U2 B2 U'
16q* U F B R2 U D F B' U' D' R2 F' B' D'
16q* U F B R2 U D F' B U' D' R2 F' B' D'
16q* U F' B' R2 U' D' F B' U D R2 F B D'
16q* U F' B' R2 U' D' F' B U D R2 F B D'
18q* F B U2 F B R L' F B D2 R' L' F2 U' D'
18q* F B U D R L F B U2 F2 B2 U D' R' L'
18q* F B U D R L F B U D' R2 L2 D2 R' L'
18q* F R2 D F' U' R U2 D2 L' U B D' L2 B'
18q* F R2 U' R U F' U D' L U' F' U F2 L' U D'
18q* F R B D F U B R' L F' D' F B' R' B R2 D
18q* F R D R' F' U B' L U' D L' F D' B R U' R' B'
18q* F R' F' R U D' F' D' F' R' U' L' B' U L' F' D' L
18q* F R' U B2 L' F U D' L' B R2 U' F L' U' D
18q* F R U' D2 F' B R' B' R L' D B R L' U' L' F'
18q* F U' B' L' B' U F U D' L D R' B' R' D' L D2
18q* F U D F B' U2 R' L B' R' L F B' R' U' D' F'
18q* F U R' U L' U' L D R L U R D' R' D L' D B
18q* U F2 R' L F' B D2 B2 R' L' U2 R2 D'
18q* U F2 R L' F B' U2 B2 R L D2 R2 D'
18q* U F' R U L U' R F' U' R U R L' B' R' L' F' D
20q* B' D' L' F' D' F' B U F' B R2 L U D' F L U R D
20q* F2 R L' U2 B R' L' B2 D' R L' U' D R F B D
20q* F B R2 F B U' F B' D' L' U' B R' L' D' B L B D
20q* F B' R F2 L B2 R' U' D F L2 U2 F R' L' U
20q* F B R F2 U D' L2 F' U D L U' D R L' U' L2
20q* F B R F2 U' D R2 B' U' D' L' U D' R' L U R2
20q* F B R F B' R' L B' R2 U' D' L D2 F B' L2 U'
20q* F B R F B R L' F' B' R' L' U D F' B' L F B R2
20q* F B R F' B' R' L F B R L U D F B R F B L2
20q* F B' U2 L F' B' D' F' B U' D B U2 R L D L2
20q* F B' U2 L F B L2 U F B' U' D B' R' L' U R2
20q* F B' U2 R F B R2 U F' B U' D F' R' L' U R2
20q* F B' U R D B' U D' R D' F' D' R B2 U' D' R' L' U
20q* F R2 L2 F' U2 R' L B2 D F2 R L' U2 B'
20q* F R B L D F' B L' U' D F' B2 U D' B' D' R' B' U'
20q* F R' B L U B R U D L F D R F L' B R2 L2
20q* F R' F' B L' F U F B U2 F B U L' F R' L B L'
20q* F R' F' B L' F U' F B U2 F B U' R' B R L' F R'
20q* F R' F' B R' B' L' F B U R' L D B U L D L D' R'
20q* F R F D' F' B R F' U' B' R L' F U' D' F' B' R2 U
20q* F R F L D F' L' F B' R' L F' B R F U L' B' L F
20q* F R L B' R' L' B U' D' F' B' U' D' F' R' L' F R L B'
20q* F R L U B2 R2 U D' R' L' U D' R U' D' L2 F'
20q* F R' L' U' F B' R' L F2 U2 F B D' R L U2 B'
20q* F R' L' U' L2 B2 R L F' B R' L D' R L U2 F'
20q* F R L U R' D' F' B' U L F' B' R F' B' D' F R U R
20q* F R' U' D' R D' F' D' R U' D' L U' B' U' L U' D' L' B
20q* F U2 R' L B2 U F2 B2 U' F2 R' L U2 B'
20q* F U2 R' L F2 U' B2 R' L D2 B' U2 D2 B
20q* F U D R U' D R' L U F' B R2 F' B R' L U2 B'
20q* F U' F R' D F' D F' R L B' U B' U L' B D' B U D
20q* F U L U F' R' L' U B' L' F' U' D B' U' D' R2 U D
20q* F U L U F' R' L' U B' L' F' U' D B' U' D' R2 U' D'
20q* F U' R B R F B' U' F U' D L' D R L' B2 R' U F'
20q* U F B' U' R F' R' B R' U2 R' F R' B' R U' F' B U
20q* U F R L' F' B L' U' D' F D2 R L' F2 D R L U
20q* U F' U D' F' B D F B R' U2 F' B L2 D' R' L' U
22q* F2 U F B D2 F B R2 L2 D' B2 U' D' R2 U' D'
22q* F2 U R L' D2 F B R L' B2 R2 U' D' L2 D' B2
22q* F B R F2 B2 U2 R L B2 R L U2 L F B R2
22q* F B R F2 R' L' D2 F2 B2 R L B2 L F B L2
22q* F B R F B' R' L B' R2 U' D' R2 L U2 F B' R2 U
22q* F B R F B' R' L B' U' D' L F B' D2 B2 L2 B2 U'
22q* F B R F B' R' L B' U' D' L F B' D2 F2 L2 F2 U'
22q* F B R F B' R' L B' U' D' R' U2 B2 U2 R L F B' U
22q* F B R F B' R' L F L2 F B U' D' L D2 F B' L2 D
22q* F B R L F B R2 U' F2 B2 R2 L2 D' R2 U D
22q* F B R L F B R2 U' F2 B2 R2 L2 D' R2 U' D'
22q* F B R L F B R' L' F' B' R' L' U' F2 B2 R2 L2 D'
22q* F B R' L' F B U F2 B2 R2 L2 D R L F' B' R L
22q* F B' U2 R F B R2 D F B' U D' F2 B R' L' U R2
22q* F B' U2 R F B R2 U' D2 F B' U' D B' R' L' U L2
22q* F R2 U' D B2 L F' B' U' R L' U' D R' B2 R L U' D'
22q* F R2 U' D B2 L U' D' F B R2 B U D' F B' U R' L'
22q* F R2 U' D B2 L U' D' F B R2 F U' D F' B D R' L'
22q* F R' D' R F R' L2 U B U' R' U R' L' U' D' F' B' D F2
22q* F R' F R2 L' B' D R' U' B L F' R2 B2 L2 D' F2
22q* F R L' B R L' U2 R2 D' F2 R' L D2 F U D R F'
22q* F R L' U' R2 D B' L' B' D B' U' F D B' D R U R' U' D
22q* F R L U' R U2 B R' F L B' L' B L D' F B' U' F D' F'
22q* F U2 R' L F2 U R L F' B' D2 F' R' L F B' R' U D
22q* F U' B' D' F2 U' F' U' D2 F U2 F' D' F U' B' L2 D'
22q* F U D F B' U2 R' L B' R' L F B' R' U' D' F' U2 D2
22q* F U D' F U D' R2 U2 L' F2 U D' L2 F R L U B'
22q* F U' F L' F' D F' R' L U' D F R' L D R' D L' F' L U' L
22q* U F R U F' B2 R F D' R' F' L' F2 R D R L2 D2
24q* F B R L F B U D' F2 U' F2 B2 R2 L2 D' F2 D2
24q* R' U2 B L' F U' B D F U D' L D2 F' R B' D F' U' B' U D'
26q* U2 D2 L F2 U' D R2 B U' D' R L F2 R U D' R' L U F' B'


Using the above information we can deduce the following table: 

 d     number of odding positions       parity of positions
--     --------------------------       -------------------
 0                              1       odd
 1                              0       even 
 2                              0       even 
 3                              0       even 
 4                              1       odd
 5                              0       even 
 6                              0       even 
 7                              0       even  
 8                              1       odd
 9                              0       even 
10                              0       even 
11                              0       even 
12                             13       odd
13                              0       even 
14                             10       even 
15                              0       even 
16                             17       odd
17                              0       even 
18                             16       even 
19                              0       even 
20                             37       odd
21                              0       even 
22                             29       odd
23                              0       even 
24                              2       even 
25                              0       even 
26                              1       odd
27                              0       even 
28                              0       even 
29                              0       even


The odd pattern breaks at depth 22.

Ps: The table stops at 29 since we know it is the upper bound.
» login or register to post comments

Derivation of the term X-symmetric

Submitted by Jerry Bryan on Tue, 09/22/2009 - 21:13.

Michael Reid is using the term X-symmetric because he is using the Dan Hoey names for the symmetries of the cube rather than using Shoenflies symbols.  As Michael says on the referenced web page, there are three X-symmetry subgroups of M which Dan calls X1, X2, and X3.  The symmetry class is then referred to as X, with X={X1,X2,X3}.

The more modern preference is to use Shoenflies symbols for Rubik's cube symmetries.  That makes sense to me, except that I wonder about one thing.  If I understand the use of Shoenflies symbols in Cube Explorer, the symbols refer to a symmetry class such as X.  I don't know how to use Shoenflies symbols to refer to a specific subgroup such as X1, X2, or X3.

There is one more aspect of terms like X-symmetric that used to confuse me a bit.  There are exactly 124 cube positions for which we would say that the symmetry class is X, not 128.  But both figures are correct in their proper context.  As Michael's referenced Web page says, the difference is that the list of 128 X-symmetric positions includes 4 positions with additional symmetry.  So there are 128 X-symmetric positions for which the symmetry class is X for 124 positions and for which the symmetry class is M for the other 4 positions.

» login or register to post comments

What does the term "odding po

Submitted by rokicki on Mon, 09/21/2009 - 17:56.
What does the term "odding position" mean?
» login or register to post comments

odding position

Submitted by brac37 on Tue, 09/22/2009 - 05:46.
A position that makes the number of positions on a certain level odd. Such a position must have 32 or 96 of the 96 symmetries (48 symmetries + equality of inverse), because that makes the size of the symmetry class 96/32=3 or 96/96=1 respectively, i.e. an odd number.
» login or register to post comments

Very Nice Analysis

Submitted by Jerry Bryan on Tue, 09/22/2009 - 21:32.

That's a great analysis.  Let me say the same thing using slightly different terminology.  Let M be the set of 48 symmetries of the cube as usual from the old Cube-Lovers list.  Then for any cube position x the size of the equivalence class xM must divide 48.  The only possible sizes for xM are therefore 1, 2, 3, 4, 6, 8, 12, 16, 24, and 48.  The only odd numbers in the list are 1 and 3.  |xM|=1 corresponds to the 4 positions for which Symclass(x)=M.  |xM|=3 corresponds to the 124 positions for which Symclass(x)=X.  And the 4+124 positions collectively are the 128 X-symmetric positions.

The only other thing to verify is antisymmetry.  xM and (x-1)M are either equal or disjoint.  Fortunately for the analysis of odding positions, xM and (x-1)M are equal for all the T-symmetric positions.  That means that the equivalence class for each T-symmetric position under symmetry and antisymmetry is an odd number of positions, containing either 1 position or 3 positions.

» login or register to post comments

Odd number of positions in FTM

Submitted by kociemba on Sat, 09/26/2009 - 03:42.
Yes, the argument is really nice. But Jerry, I do not understand why we have to think about antisymmetry here at all.

For FTM, all the computations are already done and by looking at the distance tables for groups Oh and D4h (they are on my homepage) we get immediately the nice result, that exactly for depths 0,2,4,9,15,16,18 and 19 we have and odd number of positions in FTM.
» login or register to post comments

Antisymmetry and odd positions

Submitted by Jerry Bryan on Sat, 09/26/2009 - 15:57.

Of course you are correct that the computations are already done, so we don't need a symmetry argument at all.  But if the computations were not already done, then a symmetry argument would be available.  However, if one chooses to make a symmetry argument, then antisymmetry must be included in the argument.  That is to say, if |xM| is an odd number, then so too is |(x-1)M|.  If xM and (x-1)M are disjoint, then we must add together |xM| and |(x-1)M which results in an even number.  So if we want an odding position, we require xM and (x-1)M not to be disjoint.  And if they are not disjoint, then they must be equal.

» login or register to post comments

Very nice! I had not thought

Submitted by rokicki on Tue, 09/22/2009 - 12:06.
Very nice! I had not thought of this.

My argument that the pattern could not continue was simply that there are an even number of positions; we know that positions exist at levels 0, 4, 8, 12, 16, 20, and 24, so either there is a distance-28 position, or the pattern breaks somewhere. I think it's pretty unlikely that there is a distance-28 position (indeed, I assert there is only a single distance-26 position, the known one).

We now know the pattern breaks somewhere.
» login or register to post comments

The 128 positions

Submitted by mdlazreg on Mon, 09/21/2009 - 15:15.
How did you generate the above list? Thanks.
» login or register to post comments

With cube explorer. But 128 is a nice number.

Submitted by brac37 on Tue, 09/22/2009 - 05:53.
The list was generated with cube explorer, with symmetry D4h. But you can reason why there should be 128 positions:

Positions of corners: 4
Twists of corners: 1
Positions of UD-slice edges: 2
Flips of UD-slice edges: 2
Positions of other edges: 4
Flips of other edges: 2

And 4x1x2x2x4x2 = 128.
» login or register to post comments