cubernya
Premium Member
Thanks...was wondering why the link wasn't working
"Suppose someone takes a solved 20x20x20 Rubik's cube and makes five moves - can you figure out [from that scrambled state] what those five moves were?" he asks. In other words, can you solve it in five moves? He suspects that you cannot, but has yet to prove it. "We don't know."
You're ignoring the Θ and thus the constant factors. See here for a definition/explanation:
http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations
It's not a formula where you can just plug in a number and get an output number. That's not what this is about. No, it tells you that God's numbers have a lower bound of (n^2/log n)*k1 and an upper bound of (n^2/log n)*k2, for some positive constants k1 and k2. This isn't particularly useful to get God's number for a specific n, this is all about the *general* case of nxnxn.
In the metric, where a move is defined by turning a single slice by 90 or 180 degrees there are surely less than (3n)^k different maneuvers of length k. So there are at most ((3n)^(k+1)-1)/(3n-1) maneuvers of length <=k (geometric summation formula). If you take Chris Hardwicks formula pos(n) for the number of positions of the nxnxn cube and solve for a k so that ((3n)^(k+1)-1)/(3n-1) >= pos(n) for large n you get something like
k is appoximately (0.25Log(24!)-1.5Log(4!))n^2/Log(n) for very large n (so you should not take n=3 here)
which is about 8.9291 N^2/Log[n].
A more carefull analysis does not change the situation, see
http://cubezzz.dyndns.org/drupal/?q=node/view/236 (h-s metric)
and
http://cubezzz.dyndns.org/drupal/?q=node/view/239
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}
Quotient[n^2-2n,4]
Quotient[(n-2)^2,4]
Of course I cannot prove this, but I am pretty sure that God's number for the nxnxn cube is
C(n)*n^2/Log(n) with
C(n)->0.25Log(24!)-1.5Log(4!) for n->Infinity
I don't know if this would affect your analysis, and it is very likely that I am speaking out of ignorance here, but in the second link you have a line that reads:
This formula will only calculate the number of positions to an even n x n x n cube, if I interpret your input correctly.
I've had that idea too. Here's the big problem: suppose we do this for the 4x4x4, which has 7.4 * 10^45 positions. To even keep track of the bare minimum (which positions have been solved so far) we need at least one bit for each position, or 9.2 * 10^44 bytes. This is about 8.4 * 10^32 terabytes. You can currently buy space for about $40 a terabyte. I think you can see where this is headed.
(For comparison, the 3x3x3 is "only" 4.8 million terabytes. Hence the coset approach.)
You'd probably save a factor of about 24*2*2 (for rotations + mirrors + inverses), at most. Since that's about 10^2, you would still have to store 8.4 * 10^30 terabytes. I think you can see that this doesn't help much.
How do you think I overestimated? If you think you can get a factor of 10^20 or more using symmetry, please, let me know how.
How many symmetrically unique positions are possible for the 1st turn (4x4x4)?
block turns (half-turns allowed)
moves positions cumulative positions cumulative pos.
positions mod M mod M
0 1 1 1 1
1 54 55 8 9
2 2070 2125 87 96
3 78649 80774 2052 2148
4 2973289 3054063 66299 68447
5 111963451 115017514 2376654 2445101
6 4212573974 4327591488 88205742 90650843
7 158458718464 162786309952 3305688035 3396338878
I believe on the 3x3 there are 1,090,175,792,696,524,800 non-symetric positions which is about 1/40 of the original number. Now the non-symetric positions can be stored in 60 bits per position times the # of positions which equals 65,410,547,561,791,488,000 bits or 8,176,318,445,223,936,000 bytes or ~8,176,318.4 terabytes.
2 or 3, depending on what type of turns are allowed. You still haven't explained what you mean (i.e. whether I overestimated the rough amount of symmetric positions, or the ending number of bits) and why you think it would significantly change my numbers or my conclusion.How many symmetrically unique positions are possible for the 1st turn (4x4x4)?