A080602 -id:A080602 - cp's OEIS frontend

A080601 Number of positions of the Rubik's cube at a distance of n moves from the solved state, in the half-turn metric.

1, 18, 243, 3240, 43239, 574908, 7618438, 100803036, 1332343288, 17596479795, 232248063316, 3063288809012, 40374425656248, 531653418284628, 6989320578825358, 91365146187124313

Offset: 0

N. J. A. Sloane, Feb 25 2003

The half-turn metric counts both quarter-turns and half-turns as 1 move.
This is the number of positions that can be reached in n moves from the start, but which cannot be reached in fewer than n moves.
The total number of positions is (8!*12!/2)*(2^12/2)*(3^8/3) = 43252003274489856000. - Jerry Bryan, Mar 03 2003
Relationship with A080583: 243 = 262 - 18 - 1, 3240 = 3502 - 262, 43239 = 46741 - 3502, ...

Robert G. Bryan (Jerry Bryan), posting to Cube Lovers List, Jul 10, 1998.
Rokicki, Tomas. Thirty years of computer cubing: The search for God's number. 2014. Reprinted in "Barrycades and Septoku: Papers in Honor of Martin Gardner and Tom Rogers", ed. Thane Plambeck and Tomas Rokicki, MAA Press, 2020, pp. 79-98. See Table 9.4.
Rokicki, T., Kociemba, H., Davidson, M., & Dethridge, J. (2014). The diameter of the rubik's cube group is twenty. SIAM REVIEW, 56(4), 645-670. See Table 5.1.

Alan Bawden, Cube Lovers Archive, Part 25
Jerry Bryan, God's Algorithm...
David Dijon, The insanely large number of Rubik's cube permutations | MegaFavNumbers, video (2020)
Mark Longridge, God's Algorithm Calculations for Rubik's Cube...
Tomas Rokicki, God's Algorithm out to 13f*
Tomas Rokicki, God's Number is 20
T. Rokicki, Twenty-two moves suffice for Rubik's Cube, Math. Intell. 32 (1) (2010) 33-40.
T. Rokicki, 15f* in the Face Turn Metric.
T. Rokicki, God's Algorithm out to 14f*
Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge, The Diameter Of The Rubik's Cube Group Is Twenty, SIAM J. of Discrete Math, Vol. 27, No. 2 (2013), pp. 1082-1105.

Cf. A080638, A005452, A080602.

a(11) (from Jerry Bryan, 2006) and a(12) (from Tom Rokicki, 2009) added by Herbert Kociemba, Jun 24 2009
a(13) added by Tomas Rokicki, Jul 25 2009
a(14) (from Thomas Scheunemann) and a(15) (from Morley Davidson, John Dethridge, Herbert Kociemba, and Tomas Rokicki) added by Tomas Rokicki, Jul 29 2010
Name edited by Charles R Greathouse IV, Jan 19 2016
Name edited by Ben Whitmore, Jul 31 2024

A075152 Number of possible permutations of a Rubik cube of size n X n X n.

Original entry on oeis.org

1, 3674160, 43252003274489856000, 7401196841564901869874093974498574336000000000, 282870942277741856536180333107150328293127731985672134721536000000000000000

Offset: 1

Warren Power, Sep 05 2002

nonn

More precisely, order of group of n X n X n Rubik cube, under assumptions not-s, not-m, not-i.
The three possible assumptions considered here are the following:
s (for n odd) indicates that we are working in the "supergroup" and so take account of twists of the face centers.
m (for n > 3) indicates that the pieces are marked so that we take account of the permutation of the identically-colored pieces on a face.
i (for n > 3) indicates that we are working in the theoretical invisible group and solve the pieces on the interior of the cube as well as the exterior. It is assumed that the M and S traits apply to the interior pieces as if they were on the exterior of a smaller cube.

Dan Hoey, posting to Cube Lovers List, Jun 24, 1987.
Rowley, Chris, The group of the Hungarian magic cube, in Algebraic structures and applications (Nedlands, 1980), pp. 33-43, Lecture Notes in Pure and Appl. Math., 74, Dekker, New York, 1982.

Robert Munafo, Table of n, a(n) for n = 1..27 (first 10 terms from Robert G. Wilson v)
Answers.com, Rubik's Cube.
Isaiah Bowers, How To Solve A Rubik's Cube.
Richard Carr, The Number of Possible Positions of an N x N x N Rubik Cube
Cube Lovers, Discussions on the mathematics of the cube
Cube Lovers Archive, Mailing List
Cube20.org, God's Number is 20
Christophe Goudey, Information
David Joyner, Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys, 2008. See Example 4.5.1. p. 73.
Naren Ramesh, Generalising the configurations of an N X N X N Rubik's Cube, Parabola (2023) Vol. 59, Issue 3. See p. 22.
Jaap Scherphuis, Puzzle Pages
Eric Weisstein's World of Mathematics, Rubik's Cube
WikiHow, How to Solve a Rubik's Cube with the Layer Method
Wikipedia, Rubik's Cube
Wikipedia, Professor's Cube

See A007458, A054434, A074914, A080656-A080662 for other versions.

Cf. A079761, A079762, A152169 (sums give a(2)), A080601, A080602 (sums give a(3)).

f := proc(n) local A,B,C,D,E,F,G; if n mod 2 = 1 then A := (n-1)/2; F := 0; B := 1; C := 1; D := 0; E := (n+1)*(n-3)/4; G := (n-1)*(n-3)/4; else A := n/2; F := 1; B := 1; C := 0; D := 0; E := n*(n-2)/4; G := (n-2)^2/4; fi; (2^A*((8!/2)*3^7)^B*((12!/2)*2^11)^C*((4^6)/2)^D*(24!/2)^E)/(24^F*((24^6)/2)^G); end;

f[n_] := Block[{a, b, c, d, e, f, g}, If[OddQ@ n, a = (n - 1)/2; b = c = 1; d = f = 0; e = (n + 1) (n - 3)/4; g = (n - 1) (n - 3)/4, a = n/2; b = f = 1; c = d = 0; e = n (n - 2)/4; g = (n - 2)^2/4]; Ceiling[(2^a*((8!/2)*3^7)^b*((12!/2)*2^11)^c*((4^6)/2)^d*(24!/2)^e)/(24^f*((24^6)/2)^g)]]; Array[f, 10] (* Robert G. Wilson v, May 23 2009 *)
f[1]=1; f[2]=7!3^6; f[3]=8!3^7 12!2^10;f[n_]:=f[n-2]*24^6*(24!/24^6)^(n-2);Table[f[n],{n,1,10}] (* Herbert Kociemba, Dec 08 2016 *)
f[1]=1;f[n_]:=7!3^6(6*24!!)^(s=Mod[n,2])24!^(r=(n-s)/2-1)(24!/4!^6)^(r(r+s)); Array[f,5] (* Herbert Kociemba, Jul 03 2022 *)

A075152(n) := block( if n = 1 then return (1), [a:1,b:1,c:1,d:1,e:1,f:1,g:1], if mod(n, 2) = 1 then (  a : (n-1)/2,  f : 0,  b : 1,  c : 1,  d : 0,  e : (n+1)*(n-3)/4,  g : (n-1)*(n-3)/4 ) else (  a : n/2,  f : 1,   b : 1,   c : 0,   d : 0,   e : n*(n-2)/4, g : (n-2)^2/4  ), return ( (2^a * ((factorial(8)/2)*3^7)^b * ((factorial(12)/2)*2^11)^c * ((4^6)/2)^d * (factorial(24)/2)^e) / (24^f * ((24^6)/2)^g) ) )$ for i:1 thru 27 step 1 do ( sprint(i, A075152(i)), newline() )$ /* Robert Munafo, Nov 12 2014 */

A075152(n)=ceil(3674160*(11771943321600)^(n%2)*620448401733239439360000^floor((n-2)/2)*(3246670537110000)^floor(((n-2)/2)^2)) \\ Davis Smith, Mar 20 2020

a(1)=1; a(2)=7!*3^6; a(3)=8!*3^7*12!*2^10; a(n)=a(n-2)*24^6*(24!/24^6)^(n-2). - Herbert Kociemba, Dec 08 2016

a(n) = ceiling(3674160*11771943321600^(n mod 2)*620448401733239439360000^floor((n - 2)/2)*3246670537110000^floor(((n - 2)/2)^2)). - Davis Smith, Mar 20 2020

Entry revised by N. J. A. Sloane, Apr 01 2006

Offset changed to 1 by N. J. A. Sloane, Sep 02 2009

A005452 Number of positions that the 3 X 3 X 3 Rubik cube puzzle can be in after exactly n moves, up to equivalence under the full group of order 48 of the cube and with a half-turn is considered to be 2 moves.

Original entry on oeis.org

1, 1, 5, 25, 219, 1978, 18395, 171529, 1601725, 14956266, 139629194, 1303138445, 12157779067, 113382522382, 1056867697737, 9843661720634, 91532722388023, 846837132071729, 7668156860181597

Offset: 0

N. J. A. Sloane, Feb 25 2003

This is the number of positions that can be reached in n moves from the start, but which cannot be reached in fewer than n moves.

The total number of inequivalent positions is 901083404981813616. - Jerry Bryan, Mar 03 2003

Robert G. Bryan (Jerry Bryan), postings to Cube Lovers List, Feb 04, 1995 and Oct 26, 1998.

Alan Bawden, Cube Lovers Archive, Part 15
Alan Bawden, Cube Lovers Archive, Part 16
Alan Bawden, Cube Lovers Archive, Part 26
Tomas Rokicki, God's Number in the Quarter-Turn Metric
Tomas Rokicki, Symmetrical Positions

This is A080602 reduced by action of group of order 48. Cf. A080583, A080601, A080638.

Added a(13)-a(18). This is based on a great deal of work by a large number of people; full links and credit are on cube20.org/qtm. The numbers were calculated by combining the God's number counts on the main page with the symmetric solution counts on the symmetry page. - Tomas Rokicki, Sep 01 2014

A080583 Number of positions that the 3 X 3 X 3 Rubik cube puzzle can be in after exactly n moves.

Original entry on oeis.org

1, 18, 262, 3502, 46741, 621649, 8240087, 109043123, 1441386411, 19037866206, 251285929522, 3314574738534, 43689000394782, 575342418679410

Offset: 0

Alexander D. Healy, Feb 21 2003

This is different from the sequence giving the number of positions that can be reached in n moves from the start, but which cannot be reached in fewer than n moves (A080601).
A half-turn is considered to be a single move (rather than two moves).
The total number of positions is 901083404981813616.
Relationship with A080601: 243 = 262 - 18 - 1, 3240 = 3502 - 262, 43239 = 46741 - 3502, ...

Mark Longridge, God's Algorithm Calculations for Rubik's Cube...
Rokicki, Tomas; God's Algorithm out to 13f*

Cf. A080601, A080602.

Added a(13). Tomas Rokicki, Jul 25 2009

A080638 Number of positions that the 3 X 3 X 3 Rubik cube puzzle can be in after exactly n moves, up to equivalence under the full group of order 48 of the cube and with a half-turn is considered to be 1 move.

Original entry on oeis.org

1, 2, 9, 75, 934, 12077, 159131, 2101575, 27762103, 366611212, 4838564147, 63818720716, 841134600018, 11076115427897

Offset: 0

N. J. A. Sloane, Feb 28 2003

This is the number of positions that can be reached in n moves from the start, but which cannot be reached in fewer than n moves.

The total number of inequivalent positions is 901083404981813616. - Jerry Bryan, Mar 03 2003

Robert G. Bryan (Jerry Bryan), posting to Cube Lovers List, Jul 10, 1998.

Alan Bawden, Cube Lovers Archive, Part 25
Rokicki, Tomas; God's Algorithm out to 13f*

This is A080601 reduced by action of group of order 48. Cf. A005452, A080602.

Added a(11)-a(13) Tomas Rokicki, Jul 25 2009

A257401 God's number for a Rubik's cube of size n X n X n (using the half turn metric).

Original entry on oeis.org

0, 11, 20

Offset: 1

Peter Woodward, Apr 21 2015

"God's Number" is the maximum number of turns required to solve any scrambled cube. The "Half turn metric" considers a 90- or 180-degree turn of any side to be a single turn. The number is not known for cubes of size larger than 3 X 3 X 3.

God's number has been proved using a brute-force attack for the 2 X 2 X 2 and 3 X 3 X 3 cubes. For the 4 X 4 X 4 cube, it has been proved only that the lower bound is 31, while the most probable value is considered to be 32; solving this by brute force would require checking all the A075152(4) possible permutations of the "Master Cube". - Marco Ripà, Aug 05 2015

Jerry Bryan, God's Algorithm for the 2x2x2 Pocket Cube.
Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow, Algorithms for Solving Rubik's Cubes, in: C. Demetrescu and M. M. Halldórsson (eds.), Algorithms - ESA 2011, 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011, Proceedings, Lecture Notes in Computer Science, Vol. 6942, Springer, Berlin, Heidelberg, 2011, pp. 689-700; arXiv preprint, arXiv:1106.5736 [cs.DS], 2011.
Joseph L. Flatley, Rubik's Cube solved in twenty moves, 35 years of CPU time.
Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge, The Diameter Of The Rubik's Cube Group Is Twenty, SIAM J. of Discrete Math, Vol. 27, No. 2 (2013), pp. 1082-1105.
Jaap Scherphuis, Mini Cube, the 2×2×2 Rubik's Cube.
Speedsolving.com, Rubik's Cube Fact sheet.
Wikipedia, Optimal solutions for Rubik's Cube.

Cf. A256573 (quarter turn metric), A054434 (possible positions), A075152 (possible permutations).

Cf. A079761, A079762, A080601, A080602.

From Ben Whitmore, May 31 2021: (Start)
a(n) = Theta(n^2/log(n)) [Demaine et al.].
Conjecture: a(n) ~ (1/4)*log(24!/4!^6) * n^2/log(n).
(End)

A060010 Number of 2n-move sequences on the 3 X 3 X 3 Rubik's Cube (only quarter-twists count as moves) that leave the cube unchanged.

Original entry on oeis.org

1, 12, 312, 10464, 398208, 16323072, 702465024

Offset: 0

Alexander D. Healy, Mar 15 2001

I.e., closed walks of length 2n from a fixed vertex on the Cayley graph of the cube with {F, F^(-1), R, R^(-1), B, B^(-1), L, L^(-1) U, U^(-1), D, D^(-1)} as the set of generators. Alternatively, the n-th term is equal to the sum of the n-th powers of the eigenvalues of this Cayley graph divided by the order of the Rubik's cube group, ~4.3*10^19 (see A054434).

			There are 12 closed walks of length 2: F*F^(-1), F^(-1)*F, R*R^(-1), R^(-1)*R, ..., D*D^(-1), D^(-1)*D.

Cf. A054434, A061713, A080602.

A333298 Number of canonical sequences of moves of length n for the Rubik cube puzzle using the half-turn metric.

Original entry on oeis.org

1, 18, 243, 3240, 43254, 577368, 7706988, 102876480, 1373243544, 18330699168, 244686773808, 3266193870720, 43598688377184, 581975750199168, 7768485393179328, 103697388221736960, 1384201395738071424, 18476969736848122368, 246639261965462754048, 3292256598848819251200

Offset: 0

N. J. A. Sloane, Mar 23 2020

nonn

Rokicki, Tomas. Thirty years of computer cubing: The search for God's number. 2014. Reprinted in "Barrycades and Septoku: Papers in Honor of Martin Gardner and Tom Rogers", ed. Thane Plambeck and Tomas Rokicki, MAA Press, 2020, pp. 79-98.
Rokicki, T., Kociemba, H., Davidson, M., & Dethridge, J. (2014). The diameter of the rubik's cube group is twenty. SIAM REVIEW, 56(4), 645-670. Table 5.1 gives terms 0 through 20.

Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge, The Diameter Of The Rubik's Cube Group Is Twenty, SIAM J. of Discrete Math, Vol. 27, No. 2 (2013), pp. 1082-1105.

Cf. A080601, A080602, A333299.

From Colin Barker, Mar 23 2020: (Start)
G.f.: (1 + 3*x)^2 / (1 - 12*x - 18*x^2).
a(n) = 12*a(n-1) + 18*a(n-2) for n>2.
a(n) = (-(6-3*sqrt(6))^n*(-3+sqrt(6)) + (3*(2+sqrt(6)))^n*(3+sqrt(6))) / 4 for n>0.
(End)

A333299 Number of canonical sequences of moves of length n for the Rubik's cube puzzle using the quarter-turn metric.

Original entry on oeis.org

1, 12, 114, 1068, 10011, 93840, 879624, 8245296, 77288598, 724477008, 6791000856, 63656530320, 596694646092, 5593212493440, 52428869944896, 491450379709824, 4606688566257048, 43181530471120320, 404768967341615520, 3794166513675844032, 35565225338407615152

Offset: 0

N. J. A. Sloane, Mar 23 2020

Rokicki, Tomas. Thirty years of computer cubing: The search for God's number. 2014. Reprinted in "Barrycades and Septoku: Papers in Honor of Martin Gardner and Tom Rogers", ed. Thane Plambeck and Tomas Rokicki, MAA Press, 2020, pp. 79-98. Table 9.5 gives terms 0 through 18.

Cf. A080601, A080602, A333298.

CoefficientList[Series[1 + 3a/(1 - 2a) /. a -> (1 + x)^4 - 1, {x, 0, 100}], x] (* Ben Whitmore, Dec 30 2024 *)

Conjectures from Colin Barker, Mar 23 2020: (Start)
G.f.: (1 + x)^4 / (1 - 8*x - 12*x^2 - 8*x^3 - 2*x^4).
a(n) = 8*a(n-1) + 12*a(n-2) + 8*a(n-3) + 2*a(n-4) for n>4.
(End)
The above conjectured formulas are true. - Ben Whitmore, Dec 30 2024

More terms from Ben Whitmore, Dec 30 2024

cp's OEIS Frontend

A080601 Number of positions of the Rubik's cube at a distance of n moves from the solved state, in the half-turn metric.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A075152 Number of possible permutations of a Rubik cube of size n X n X n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A005452 Number of positions that the 3 X 3 X 3 Rubik cube puzzle can be in after exactly n moves, up to equivalence under the full group of order 48 of the cube and with a half-turn is considered to be 2 moves.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A080583 Number of positions that the 3 X 3 X 3 Rubik cube puzzle can be in after exactly n moves.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A080638 Number of positions that the 3 X 3 X 3 Rubik cube puzzle can be in after exactly n moves, up to equivalence under the full group of order 48 of the cube and with a half-turn is considered to be 1 move.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A257401 God's number for a Rubik's cube of size n X n X n (using the half turn metric).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A060010 Number of 2n-move sequences on the 3 X 3 X 3 Rubik's Cube (only quarter-twists count as moves) that leave the cube unchanged.

Views

Author

Keywords

Comments

Examples

Crossrefs

A333298 Number of canonical sequences of moves of length n for the Rubik cube puzzle using the half-turn metric.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A333299 Number of canonical sequences of moves of length n for the Rubik's cube puzzle using the quarter-turn metric.

Views

Author

Keywords

References

Crossrefs