Home »

Approximation formula for the lower bounds of nxnxn cube in slice turn metric

Submitted by kociemba on Wed, 08/03/2011 - 17:40.
I tried to derive some analytic approximation formula for the lower bound in h-s metric, that is half-turm metric with slice moves for large n. There are 9n possible slice moves for an nxnxn cube, and without using any other relations where would be (9n)^k move sequences of length k. In my simplified model I only used the relations that the 3n slice moves of one axis commute and that there are never two successive moves with the same slice (the latter does not hold in quarter turn metric).

I did not take into account, that k>=n/2 successive slice moves on the same axis might be equivalent to <=n/2 different slice moves on this axis. So the number of sequences of length k in this model will be greater than the number Tom derives with a full syllable analysis. But for large n the relative difference will get negligible because from a probabilistic point of view there are "almost no" sequences with this property. The advantage of this simplified model is, that it can be handled by methods of Linear Algebra. Especially the number of sequences with length k can be derived from the k-th power of some nxn matrix A.

I got the following results:

1. There are 9N sequences of length 1 and 9n(7.5n-1.5) sequences of length 2.

2. The greatest eigenvalue of A and thus the asymptotic branching factor is bf[n]=3/(1.5^(1/n)-1)

From this we get the approximation formula

countApprox[n] = 9n(7.5n-1.5) bf[n]^(k-2)

for the number of sequences of length k. For the number of sequences of length <= k we then get

countSumApprox[n] = 9n(7.5n-1.5) (bf[n]^(k-1)-1)/(bf[n]-1)

I implemented Chris Hardwicks formula for the number of positions of an nxnxn cube as

pos[n_]:=(24*2^10*12!)^(Mod[n,2])*7!*3^6*24!^Quotient[n^2-2n,4]/4!^(6 Quotient[(n-2)^2,4])

Searching the first n that countSumApprox[n]>=pos[n] gives for 2<=n<=30

{6,15,32,48,72,95,124,153,189,224,265,306,353,400,452,504,562,620,682,746,814,882,956,1029,1108,1187,1270,1354,1443}

The consistency with Tom's h-s result for n<= 20 is perfect for k>=6. If we only take even n the formula for pos[n] gets simpler.
By solving countSumApprox[n]=pos[n] for k and doing further simplification under the assumption of large n we finally get for an approximation of the lower bound:

approxLowerBoundEven[n_]:=Ceiling[(Log[7!*3^6]+(n^2-2n)/4*Log[24!]-3/2(n-2)^2*Log[4!])/Log[bf[n]]]

For the even 2<=n<=30 we get {6,32,72,124,189,265,353,452,562,683,814,956,1108,1270,1443} which still gives remarkably good values for small n.

For n=100 we get 13394 also in perfect accordance with Tom's result. For n=1000, 10000 and 100000 we get 1001335, 79633836 and 6607110479. Maybe Tom can supply his values occasionally.

Because there is no strict estimation for the error approxLowerBoundEven will not give a true lower bound for the number of moves. But still it is interesting that such a simple formula gives a very good approximation. Even if you plug odd n into the formula the results are quite accurate.
» 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.

What about face turn metric?

Submitted by brac37 on Wed, 11/16/2011 - 18:37.
What about face turn metric? Of course, when a face is turned, one may take the adjacent slice and subsequent slices with this turn as well, for otherwise you will not go beyond 3x3x3.

Notice that STM distances are no longer necessarily smaller than FTM distances (except if one allows to take an adjacent slice and subsequent slices as well in STM).
» login or register to post comments

Approximation for Face Turn Metric

Submitted by kociemba on Fri, 11/18/2011 - 17:33.
Using the naming convention of http://cubezzz.dyndns.org/drupal/?q=node/view/236, where Tom gives lower bounds in 6 different metrics, what you talk about is h-w metric. h-w diameter lower bound is always greater than h-s lower bound (for n>2) because in h-s, with the nxnxn cube we have 3*n different moves on one axis, while in h-w, we only have 3*(n-1) different moves. So we just substitute n-1 for n in the formulas used above (except in pos[n_]) and get with

pos[n_]:=(24*2^10*12!)^(Mod[n,2])*7!*3^6*24!^Quotient[n^2-2n,4]/4!^(6 Quotient[(n-2)^2,4])
and
bf[n]=3/(1.5^(1/n)-1)

instead of the expression for h-s metric

approxMinHS[n_]:= Ceiling[Log[pos[n] (bf[n]-1)/(9n(-1.5+7.5n))+1]/Log[bf[n]]]+1

now for h-w metric

approxMinHW[n_]:=Ceiling[Log[pos[n] (bf[n-1]-1)/(9(n-1)(-1.5+7.5(n-1)))+1]/Log[bf[n-1]]]+1

For 2<=n<=30 we get for approxMinHW[n_]

{9,18,35,52,75,99,128,158,193,229,270,312,359,406,458,511,568,626,690,753,821,890,964,1037,1116,1195,1279,1363,1452}

in perfect accordance with all n provided by Tom.

So the approximation in h-w is even better as in h-s, because in h-w we get Tom's values for n>=2 while in h-s the values are the same for n>=6.

The reason that the approximation is almost perfect is that my matrix approach gives the true number of canonical sequences in the h-w case.
With Mathematica Code we have the definitions:

m[n_]:=Table[If[i>j,3,2],{i,1,n-1},{j,1,n-1}]

and

v[n_]:=Table[9,{i,1,n-1}]

and the number of canonical sequences of length k

countHW[n_,k_]:=Total[MatrixPower[3m[n],k-1].v[n]]

So we also have the nice result, that

bf[n_]:=3/(1.5^(1/(n-1))-1)

is the exact value for the asymptotic branching factor for the number of canonical sequences in h-w.

For n=4 we get for example 20.7305, which also is very close to the branching factors of the true number of 4x4x4 positions given in http://cubezzz.dyndns.org/drupal/?q=node/view/235

It also can be shown, that we have for the number of canonical sequences countHW[4,k] for 4x4x4 the approximation

(3/(a-1))^k (1+a+a^2)a/3

with a =1.5^(1/3) and the relative error converging to 0 quickly.

» login or register to post comments