Home »

Number of canonical move sequences for nxnxn Rubik's cube in q-w metric

Submitted by kociemba on Mon, 12/26/2011 - 12:22.
Quarter turn metric is more difficult to handle than h-w metric, because the 180 degree turn has to be counted as two moves, which gives some issues with an recursive approach. I did not believe it was possible to get a simple formula here. I was very surprised, that the result was a simple generating function for the number of canonical sequences in q-w-metric. It is

gfq[n_,x_]:=3/(6-4(x+1)^(2(n-1)))-1/2

and looks very similar to the generating function in h-w metric which is

gfh[n_,x_]:= 3/(6-4(3x+1)^(n-1))-1/2

For n=3 we have for example

Series[gfq[3,x],{x,0,10}] 1+12 x+114 x^2+1068 x^3+10011 x^4+93840 x^5+879624 x^6+8245296 x^7+77288598 x^8+724477008 x^9+6791000856 x^10+O[x]^11

From the generating function it is possible to get an explicit formula for the number of canonical move sequences with length k, but I yet have to work this out, because the double zeros of the denominator make things a bit more complicated.

The inverse of the smallest zero of the denominator is the asymptotic branching factor, which is

1/(-1+(3/2)^(1/(2 (-1+n))))

» 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.

Non recursive formula

Submitted by kociemba on Wed, 12/28/2011 - 17:44.
Hmm, there are no double zeros at all, so the derivation of the non recursive formula was straightforward. We have with

bq[n_,j_]:=1/((3/2)^(1/(2n))*E^(I*j*PI)/n)-1)

that

countQW[n_,k_]:=Sum[(1+bq[n,j])/(4n) bq[n,j]^k,{j,0,2n-1}]

gives the number of q-w canonical sequences for the (n+1)x(n+1)x(n+1) cube. A very good approximation is

countQWApprox[n_,k_]:=( 1+bq[n,0] )/(4n) bq[n,0]^k

because Abs[bq[n,j]]<< Abs[bq[n,0]] for 1<=j<2n

Using this terminology, for the number of h-w canonical sequences we have

bh[n_,j_]:=3/((3/2)^(1/n) E^(2*I*j*PI/n)-1)
countHW[n_,k_]:=Sum[(3+bh[n,j])/(6n) bh[n,j]^k,{j,0,n-1}]
countHWApprox[n_,k_]:=( 3+bh[n,0] )/(6n) bh[n,0]^k

» login or register to post comments

This is amazing! Can you plea

Submitted by mdlazreg on Thu, 02/09/2012 - 07:30.
This is amazing! Can you please post the count table using this non recursive formula similar to what you did for HTM? What is QTM God's number according to this formula?
» login or register to post comments