Home »

Linear formula

Submitted by mdlazreg on Mon, 09/28/2009 - 08:13.
Let's assume that there is a linear formula that gives us P(n) using P(k) where 0 <= k <= n-1. P(n) is the number of positions at depth n.

We have then the following formula:

P(n) = sum(R(k)*P(n-k)) for 1 <= k <= n

Calculating R(k) using rokiki's results we deduce : 

 1 12                   = 12*1                   
 2 114                  = 12*12                  -30*1                   
 3 1068                 = 12*114                 -30*12                  +60*1                   
 4 10011                = 12*1068                -30*114                 +60*12                  -105*1                   
 5 93840                = 12*10011               -30*1068                +60*114                 -105*12                  +168*1                   
 6 878880               = 12*93840               -30*10011               +60*1068                -105*114                 +168*12                  -996*1                   
 7 8221632              = 12*878880              -30*93840               +60*10011               -105*1068                +168*114                 -996*12                  +-5448*1                   
 8 76843595             = 12*8221632             -30*878880              +60*93840               -105*10011               +168*1068                -996*114                 +-5448*12                  +-29338*1                   
 9 717789576            = 12*76843595            -30*8221632             +60*878880              -105*93840               +168*10011               -996*1068                +-5448*114                 +-29338*12                  +-209196*1                   
10 6701836858           = 12*717789576           -30*76843595            +60*8221632             -105*878880              +168*93840               -996*10011               +-5448*1068                +-29338*114                 +-209196*12                  +-1466540*1                   
11 62549615248          = 12*6701836858          -30*717789576           +60*76843595            -105*8221632             +168*878880              -996*93840               +-5448*10011               +-29338*1068                +-209196*114                 +-1466540*12                  +-12951572*1                   
12 583570100997         = 12*62549615248         -30*6701836858          +60*717789576           -105*76843595            +168*8221632             -996*878880              +-5448*93840               +-29338*10011               +-209196*1068                +-1466540*114                 +-12951572*12                  +-123874230*1                   
13 5442351625028        = 12*583570100997        -30*62549615248         +60*6701836858          -105*717789576           +168*76843595            -996*8221632             +-5448*878880              +-29338*93840               +-209196*10011               +-1466540*1068                +-12951572*114                 +-123874230*12                  +-1299701980*1                   
14 50729620202582       = 12*5442351625028       -30*583570100997        +60*62549615248         -105*6701836858          +168*717789576           -996*76843595            +-5448*8221632             +-29338*878880              +-209196*93840               +-1466540*10011               +-12951572*1068                +-123874230*114                 +-1299701980*12                  +-16393858750*1                   
15 472495678811004      = 12*50729620202582      -30*5442351625028       +60*583570100997        -105*62549615248         +168*6701836858          -996*717789576           +-5448*76843595            +-29338*8221632             +-209196*878880              +-1466540*93840               +-12951572*10011               +-123874230*1068                +-1299701980*114                 +-16393858750*12                  +-258524867460*1
One might ask what is the signification of R(k).
» 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.

correction

Submitted by mdlazreg on Mon, 09/28/2009 - 08:39.
Sorry there was a +- signs issue in the above table, here is the correct one: 

 1 12                   = 12*1                   
 2 114                  = 12*12                  -30*1                   
 3 1068                 = 12*114                 -30*12                  +60*1                   
 4 10011                = 12*1068                -30*114                 +60*12                  -105*1                   
 5 93840                = 12*10011               -30*1068                +60*114                 -105*12                  +168*1                   
 6 878880               = 12*93840               -30*10011               +60*1068                -105*114                 +168*12                  -996*1                   
 7 8221632              = 12*878880              -30*93840               +60*10011               -105*1068                +168*114                 -996*12                  -5448*1                   
 8 76843595             = 12*8221632             -30*878880              +60*93840               -105*10011               +168*1068                -996*114                 -5448*12                  -29338*1                   
 9 717789576            = 12*76843595            -30*8221632             +60*878880              -105*93840               +168*10011               -996*1068                -5448*114                 -29338*12                  -209196*1                   
10 6701836858           = 12*717789576           -30*76843595            +60*8221632             -105*878880              +168*93840               -996*10011               -5448*1068                -29338*114                 -209196*12                  -1466540*1                   
11 62549615248          = 12*6701836858          -30*717789576           +60*76843595            -105*8221632             +168*878880              -996*93840               -5448*10011               -29338*1068                -209196*114                 -1466540*12                  -12951572*1                   
12 583570100997         = 12*62549615248         -30*6701836858          +60*717789576           -105*76843595            +168*8221632             -996*878880              -5448*93840               -29338*10011               -209196*1068                -1466540*114                 -12951572*12                  -123874230*1                   
13 5442351625028        = 12*583570100997        -30*62549615248         +60*6701836858          -105*717789576           +168*76843595            -996*8221632             -5448*878880              -29338*93840               -209196*10011               -1466540*1068                -12951572*114                 -123874230*12                  -1299701980*1                   
14 50729620202582       = 12*5442351625028       -30*583570100997        +60*62549615248         -105*6701836858          +168*717789576           -996*76843595            -5448*8221632             -29338*878880              -209196*93840               -1466540*10011               -12951572*1068                -123874230*114                 -1299701980*12                  -16393858750*1                   
15 472495678811004      = 12*50729620202582      -30*5442351625028       +60*583570100997        -105*62549615248         +168*6701836858          -996*717789576           -5448*76843595            -29338*8221632             -209196*878880              -1466540*93840               -12951572*10011               -123874230*1068                -1299701980*114                 -16393858750*12                  -258524867460*1
» login or register to post comments

Just a stupid question

Submitted by brac37 on Wed, 10/07/2009 - 18:55.
Just a stupid question. For the 2x2x2-cube, does there exist a linear formula with say, less than 1000 terms.
Of course, there exists a linear formula with infinitely many terms, but that is not a real linear formula, is it?
» login or register to post comments

Linear formula for 2x2x2

Submitted by mdlazreg on Thu, 10/08/2009 - 04:49.
For the 2x2x2 cube we can come up with this : 
 1 6                    = 6*1                   
 2 27                   = 6*6                   -9*1                   
 3 120                  = 6*27                  -9*6                   +12*1                   
 4 534                  = 6*120                 -9*27                  +12*6                   -15*1                   
 5 2256                 = 6*534                 -9*120                 +12*27                  -15*6                   -102*1                   
 6 8969                 = 6*2256                -9*534                 +12*120                 -15*27                  -102*6                   -184*1                   
 7 33058                = 6*8969                -9*2256                +12*534                 -15*120                 -102*27                  -184*6                   -1202*1                   
 8 114149               = 6*33058               -9*8969                +12*2256                -15*534                 -102*120                 -184*27                  -1202*6                   +1880*1                   
 9 360508               = 6*114149              -9*33058               +12*8969                -15*2256                -102*534                 -184*120                 -1202*27                  +1880*6                   -2930*1                   
10 930588               = 6*360508              -9*114149              +12*33058               -15*8969                -102*2256                -184*534                 -1202*120                 +1880*27                  -2930*6                   -27852*1                   
11 1350852              = 6*930588              -9*360508              +12*114149              -15*33058               -102*8969                -184*2256                -1202*534                 +1880*120                 -2930*27                  -27852*6                   +130410*1                   
12 782536               = 6*1350852             -9*930588              +12*360508              -15*114149              -102*33058               -184*8969                -1202*2256                +1880*534                 -2930*120                 -27852*27                  +130410*6                   +5490003*1                   
13 90280                = 6*782536              -9*1350852             +12*930588              -15*360508              -102*114149              -184*33058               -1202*8969                +1880*2256                -2930*534                 -27852*120                 +130410*27                  +5490003*6                   -5495604*1                   
14 276                  = 6*90280               -9*782536              +12*1350852             -15*930588              -102*360508              -184*114149              -1202*33058               +1880*8969                -2930*2256                -27852*534                 +130410*120                 +5490003*27                  -5495604*6                   -24523365*1


The terms R(k) actually counts the number of duplicate positions at
depth k. For example at depth 2 R(2)=-9 because 9 positions are
missing, for R(3)=12 which is the sum of duplicate positions that are
due to 2q identities only and duplicate positions that are due to 3q
identities only, in my syllable notation that would be sum of the
following two categories:
3
2-1 2
while the -9 is the sum of the category:
2
In general a linear formula can be found with a number of terms that
is less than the diameter, for the 2x2x2 cube it is 14.

We can however reduce the number of terms if we find a relationship
between R(k). This can only be possible if at some depth there are no
new non trivial identities.

I think I will try to study the 2x2x2 cube using identities only. For
the real cube I think it is going to be very difficult because I have
a hunch that they are non trivial identities going all the way to the
diameter...

» login or register to post comments

R(k) and Duplicate Positions

Submitted by Jerry Bryan on Thu, 10/08/2009 - 12:13.
I'm not sure I agree that R(k) represents duplicate positions. For example (and referring back to the full cube rather than the 2x2x2), we have R(2) = -30.  But 30 is not the number of duplicate positions of length 2q for the full cube.

I guess we have to agree on how we count duplicate positions.  Let's say for the sake of the argument that for FF=F'F', we have two maneuvers for one duplicate position.  In general, a duplicate position can have more than two maneuvers.  With this understanding, we have the following for the full cube for length 2q. 

     maneuvers    positions

        96           96      non-duplicate positions with one maneuver
        36           18      duplicate positions with two maneuvers
      ----         ----
Total  132          114
The number -30 in your formula is the difference between 144 and 114.  144 is 122, which is the number of sequences containing 2 quarter turns, irrespective of whether those 2 quarter turns yield a position of length 2q or not.  So the -30 figure is a combination of two quarter turn maneuvers that yield duplicate positions of length 2q and two quarter turn maneuvers that yield a position of length less than 2q.
» login or register to post comments

R(k) is duplicate maneuvers

Submitted by mdlazreg on Thu, 10/08/2009 - 17:17.
Correct. R(k) counts all duplicate maneuvers not positions.

So 30 = 18 + 12 where 18 is coming from duplicate positions at level 2 while 12 is coming from duplicate maneuvers:

MM'

where M is one of the 12 moves.

The next term at level 3 which is 60 is coming from:

60 = 66 - 6

where 66 is the number of patterns of the form 2-1 2 and 6 is the number of patterns of the form 3.

One advantage of calculating the number of positions this way is that you do not need to store positions at level n to calculate positions at level n+1, all you need is to store the duplicate maneuvers which are a much smaller number and see how many positions they will remove at each depth. For example a duplicate position is UD=DU, you can take UD to be the duplicate maneuver and count all maneuvers at all levels that have the UD pattern so that to exclude them from the legitimate positions...

I have a working computer program that is counting positions this way... I use Herbert's QTM solver to generate the duplicate maneuvers but I have an issue with it as it does not generate all of them... For example if you give it an input of UU' it will generate 12q identities but will not generate 4q identities like FFFF. While I was able to deal with this at lower levels, I am stuck at higher levels because I am missing many duplicate maneuvers..
» login or register to post comments

No I mean the whole table

Submitted by brac37 on Thu, 10/08/2009 - 10:27.
I mean the whole infinite table, so

15 0 = 6*276 -9*90280 ...

16 0 = 6*0 -9*275 ...

17 0 = 6*0 -9*0 ...

...

Will the linear formula end, i.e. will there be only zero coefficients from some point?
» login or register to post comments

No, it will continue as follo

Submitted by mdlazreg on Thu, 10/08/2009 - 11:13.
No, it will continue as follow: 
 1 6                    = 6*1                   
 2 27                   = 6*6                   -9*1                   
 3 120                  = 6*27                  -9*6                   +12*1                   
 4 534                  = 6*120                 -9*27                  +12*6                   -15*1                   
 5 2256                 = 6*534                 -9*120                 +12*27                  -15*6                   -102*1                   
 6 8969                 = 6*2256                -9*534                 +12*120                 -15*27                  -102*6                   -184*1                   
 7 33058                = 6*8969                -9*2256                +12*534                 -15*120                 -102*27                  -184*6                   -1202*1                   
 8 114149               = 6*33058               -9*8969                +12*2256                -15*534                 -102*120                 -184*27                  -1202*6                   +1880*1                   
 9 360508               = 6*114149              -9*33058               +12*8969                -15*2256                -102*534                 -184*120                 -1202*27                  +1880*6                   -2930*1                   
10 930588               = 6*360508              -9*114149              +12*33058               -15*8969                -102*2256                -184*534                 -1202*120                 +1880*27                  -2930*6                   -27852*1                   
11 1350852              = 6*930588              -9*360508              +12*114149              -15*33058               -102*8969                -184*2256                -1202*534                 +1880*120                 -2930*27                  -27852*6                   +130410*1                   
12 782536               = 6*1350852             -9*930588              +12*360508              -15*114149              -102*33058               -184*8969                -1202*2256                +1880*534                 -2930*120                 -27852*27                  +130410*6                   +5490003*1                   
13 90280                = 6*782536              -9*1350852             +12*930588              -15*360508              -102*114149              -184*33058               -1202*8969                +1880*2256                -2930*534                 -27852*120                 +130410*27                  +5490003*6                   -5495604*1                   
14 276                  = 6*90280               -9*782536              +12*1350852             -15*930588              -102*360508              -184*114149              -1202*33058               +1880*8969                -2930*2256                -27852*534                 +130410*120                 +5490003*27                  -5495604*6                   -24523365*1                   
15 0                    = 6*276                 -9*90280               +12*782536              -15*1350852             -102*930588              -184*360508              -1202*114149              +1880*33058               -2930*8969                -27852*2256                +130410*534                 +5490003*120                 -5495604*27                  -24523365*6                   -95809802*1                   
16 0                    = 6*0                   -9*276                 +12*90280               -15*782536              -102*1350852             -184*930588              -1202*360508              +1880*114149              -2930*33058               -27852*8969                +130410*2256                +5490003*534                 -5495604*120                 -24523365*27                  -95809802*6                   -444337131*1                   
17 0                    = 6*0                   -9*0                   +12*276                 -15*90280               -102*782536              -184*1350852             -1202*930588              +1880*360508              -2930*114149              -27852*33058               +130410*8969                +5490003*2256                -5495604*534                 -24523365*120                 -95809802*27                  -444337131*6                   -399024232*1                   
18 0                    = 6*0                   -9*0                   +12*0                   -15*276                 -102*90280               -184*782536              -1202*1350852             +1880*930588              -2930*360508              -27852*114149              +130410*33058               +5490003*8969                -5495604*2256                -24523365*534                 -95809802*120                 -444337131*27                  -399024232*6                   +2094037392*1                   
19 0                    = 6*0                   -9*0                   +12*0                   -15*0                   -102*276                 -184*90280               -1202*782536              +1880*1350852             -2930*930588              -27852*360508              +130410*114149              +5490003*33058               -5495604*8969                -24523365*2256                -95809802*534                 -444337131*120                 -399024232*27                  +2094037392*6                   +22117551192*1                   
20 0                    = 6*0                   -9*0                   +12*0                   -15*0                   -102*0                   -184*276                 -1202*90280               +1880*782536              -2930*1350852             -27852*930588              +130410*360508              +5490003*114149              -5495604*33058               -24523365*8969                -95809802*2256                -444337131*534                 -399024232*120                 +2094037392*27                  +22117551192*6                   +68507202360*1                   
21 0                    = 6*0                   -9*0                   +12*0                   -15*0                   -102*0                   -184*0                   -1202*276                 +1880*90280               -2930*782536              -27852*1350852             +130410*930588              +5490003*360508              -5495604*114149              -24523365*33058               -95809802*8969                -444337131*2256                -399024232*534                 +2094037392*120                 +22117551192*27                  +68507202360*6                   +192530522476*1                   
22 0                    = 6*0                   -9*0                   +12*0                   -15*0                   -102*0                   -184*0                   -1202*0                   +1880*276                 -2930*90280               -27852*782536              +130410*1350852             +5490003*930588              -5495604*360508              -24523365*114149              -95809802*33058               -444337131*8969                -399024232*2256                +2094037392*534                 +22117551192*120                 +68507202360*27                  +192530522476*6                   +793029592228*1                   
23 0                    = 6*0                   -9*0                   +12*0                   -15*0                   -102*0                   -184*0                   -1202*0                   +1880*0                   -2930*276                 -27852*90280               +130410*782536              +5490003*1350852             -5495604*930588              -24523365*360508              -95809802*114149              -444337131*33058               -399024232*8969                +2094037392*2256                +22117551192*534                 +68507202360*120                 +192530522476*27                  +793029592228*6                   +931347305100*1                   
24 0                    = 6*0                   -9*0                   +12*0                   -15*0                   -102*0                   -184*0                   -1202*0                   +1880*0                   -2930*0                   -27852*276                 +130410*90280               +5490003*782536              -5495604*1350852             -24523365*930588              -95809802*360508              -444337131*114149              -399024232*33058               +2094037392*8969                +22117551192*2256                +68507202360*534                 +192530522476*120                 +793029592228*27                  +931347305100*6                   -30976219980753*1
» login or register to post comments