login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A257401 God's number for a Rubik's cube of size n X n X n (using the half turn metric). 2
0, 11, 20 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
"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
LINKS
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.
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.
Speedsolving.com, Rubik's Cube Fact sheet.
FORMULA
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)
CROSSREFS
Cf. A256573 (quarter turn metric), A054434 (possible positions), A075152 (possible permutations).
Sequence in context: A129909 A174976 A003284 * A283903 A063589 A102815
KEYWORD
nonn,hard,more,bref
AUTHOR
Peter Woodward, Apr 21 2015
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:34 EDT 2024. Contains 371254 sequences. (Running on oeis4.)