# God's Number for 5x5x5?



## nalralz (Jul 10, 2015)

I know there is a thread for God's number for 4x4x4 but but what is God's number for 5x5x5? Is it less than 60? The WCA scramble count is 60.


----------



## guysensei1 (Jul 10, 2015)

It's greater than 20. That I can say for sure.


----------



## josh42732 (Jul 10, 2015)

And greater than 21 definitely.


----------



## cubernya (Jul 10, 2015)

Has anybody done the calculation for the number of turns it even takes to reach all positioms? I know this has been done for 3x3 (18) and 4x4 (32?)


----------



## guysensei1 (Jul 10, 2015)

theZcuber said:


> Has anybody done the calculation for the number of turns it even takes to reach all positioms? I know this has been done for 3x3 (18) and 4x4 (32?)



Isn't the 3x3 one supposed to be 20?


----------



## cashis (Jul 10, 2015)

yeah I'm pretty sure God's # for 333 is 20.


----------



## theROUXbiksCube (Jul 10, 2015)

cashis said:


> yeah I'm pretty sure God's # for 333 is 20.



someone got an 18 in the weekly FMC solves a while back i believe


----------



## qqwref (Jul 10, 2015)

I'm pretty sure this is not something we'll know or even have a good shot at answering for a very, very long time. Do some FMC if you want - 103 sounds really good - but keep in mind that the 4x4x4 FMC contest that just concluded had winning averages of 36 for computer and 76 for human. So you are probably going to have to use a computer to get anywhere near optimal.


----------



## cashis (Jul 10, 2015)

theROUXbiksCube said:


> someone got an 18 in the weekly FMC solves a while back i believe



I'm not sure I'm seeing your point. 
Every cube state can be solved with a maximum of 20 moves.


----------



## theROUXbiksCube (Jul 10, 2015)

cashis said:


> I'm not sure I'm seeing your point.
> Every cube state can be solved with a maximum of 20 moves.



Maybe they confused the two


----------



## shadowslice e (Jul 10, 2015)

theZcuber said:


> Has anybody done the calculation for the number of turns it even takes to reach all positioms? I know this has been done for 3x3 (18) and 4x4 (32?)



God's number for 3x3x3 is definately 20. 18 was established as a lower bound for the number of moves that a cube could be solved in a while back. 

However, this was not created using a supercomputer to all solutions but rather by working out how many possible combinations of 18 moves one could make on a cube and does not account for cubes that are isometric. 

As it turns out the total number of unique positions a cube could be in (while assembled correctly) was less than the number of combinations of 18 turns one could make on a cube.

However, many, if not most cubes that could be created with the 18 turn movesets would be identical.

If i remember correctly, there are actually still a stupidly large number of 20-depth cubes possible (something like ~490,000,000)

In addition, as far as I'm aware, no one has actually proven that God's number for 3x3x3 is 20 mathematically- only via brute force methods.


----------



## StachuK1992 (Jul 10, 2015)

http://cube20.org/


There are about 490,000,000 20-depth cubes.


----------



## tseitsei (Jul 10, 2015)

StachuK1992 said:


> http://cube20.org/
> 
> 
> There are about 490,000,000 20-depth cubes.



Yep and even if it sounds amazingly large number at first it really is VERY VERY small compared to total number of positions which is ~43*10^18

So that means that only (49*10^7)/(43*10^18) = 1.4*10^-11 = 1.4*10^-9 % of all positions are 20 move optimal. So ridiculously few


----------



## NewCuber000 (Jul 10, 2015)

theROUXbiksCube said:


> someone got an 18 in the weekly FMC solves a while back i believe





Yes, of course theres going to be possible solutions to some scrambles under 20 moves. But what they're saying is that the most moves it will ever take to solve a rubiks cube will be 20 moves or less.


----------



## TDM (Jul 10, 2015)

guysensei1 said:


> Isn't the 3x3 one supposed to be 20?


Not God's number. He means there are over 43 quintillion possible combinations of 18 moves or less (which is how the lower bound of 18 was found for 3x3 before we found superflip to be 20 moves optimal).


----------



## cubernya (Jul 10, 2015)

shadowslice e said:


> God's number for 3x3x3 is definately 20. 18 was established as a lower bound for the number of moves that a cube could be solved in a while back.
> 
> However, this was not created using a supercomputer to all solutions but rather by working out how many possible combinations of 18 moves one could make on a cube and does not account for cubes that are isometric.
> 
> ...



This is what I was getting at. I _think_ I've seen calculations done like this for up to 7x7, but I have no idea where they are


----------



## Christopher Mowla (Jul 10, 2015)

theZcuber said:


> This is what I was getting at. I _think_ I've seen calculations done like this for up to 7x7, but I have no idea where they are


Are you thinking of this or this?


----------



## nalralz (Jul 11, 2015)

But what is it for 5x5?


----------



## shadowslice e (Jul 12, 2015)

Total number of possible permutations for a 5x5x5= 282 870 942 277 741 856 536 180 333 107 150 328 293 127 731 985 672 134 721 536 000 000 000 000 000 =~2.83x10^74 (from Wikipedia)

Number of permutations possible for WCA scrambling= 15^60= 3.67x10^70

Doesn't this mean that at least 99.9% of scrambles on a professor are not reachable from a WCA scramble?

Actual number of moves needed to equalise the number of possible permutations= 64 (15^64=~1.86x10^74).

Considering many of these states would be identical or at least isomorphic, I would say that the WCA should employ a 70 move scramble.

However, the question at this point is: is it worth it? When a speedcuber begins to solve they will likely add to the number of moves required to reach each state rather than reduce it (at least for a few moves at the start)


----------



## Lucas Garron (Jul 12, 2015)

shadowslice e said:


> Considering many of these states would be identical or at least isomorphic, I would say that the WCA should employ a 70 move scramble.
> 
> However, the question at this point is: is it worth it? When a speedcuber begins to solve they will likely add to the number of moves required to reach each state rather than reduce it (at least for a few moves at the start)



It doesn't matter, as long as the states are indistinguishable from random by a human. 10^74 states are good enough, as long as they are sufficiently well distributed.

It's a separate question to ask if they're well-distributed enough, one that probably hasn't had enough attention. But mostly unrelated to the "can we reach every state" calculation.

(The fraction of Megaminx scrambles we can generate is also very low.)


----------



## Stefan (Jul 12, 2015)

shadowslice e said:


> When a speedcuber begins to solve they will likely add to the number of moves required to reach each state rather than reduce it (at least for a few moves at the start)



Hmm, I'm not 100% sure what you mean, but you just made me think of something.

God's 5x5x5 number might be higher than God's 5x5x5 number for a random state. In other words, God might be able to save moves by pulling a Steven Brundage.

Consider this one-dimensional 2x2 puzzle with its six states. You have moves U, D, L and R. The top and bottom states have average distance 1.2 moves to all other states. The other four states have average distance 1.6 moves. So on average you can save moves if you declare one of those "mixed" states to be the goal, instead of one of those "nonmixed" states. The maximum distance, i.e., God's number, is the same here for all states (it's two moves), but I can imagine other puzzles (including 5x5x5) having different God's numbers for different goal states.


----------



## unsolved (Jul 12, 2015)

nalralz said:


> I know there is a thread for God's number for 4x4x4 but but what is God's number for 5x5x5?



I did a count of possible unique moves made from the solved state as a function of depth and compared that to the number of possible piece arrangements on a Wikipedia page. I can't remember the exact number but I'm sure it was under 60. Here are some numbers from my own 5x5x5 brute force solver:


----------



## qqwref (Jul 12, 2015)

shadowslice e said:


> Number of permutations possible for WCA scrambling= 15^60= 3.67x10^70


Wrong. There are not 18 possible turns, but 36. (And the calculation is quite a bit more complicated than that anyway, because of turns on the same axis.)



Lucas Garron said:


> (The fraction of Megaminx scrambles we can generate is also very low.)


Megaminx scrambling is actually hilariously bad (we can reach less than the *cube root* of the total number of positions), but unfortunately there's probably not much we can do about that... Every better scrambling algorithm takes longer or is harder to do.



Stefan said:


> Hmm, I'm not 100% sure what you mean, but you just made me think of something.
> 
> God's 5x5x5 number might be higher than God's 5x5x5 number for a random state. In other words, God might be able to save moves by pulling a Steven Brundage.


Perhaps, perhaps. If so this would have to be because bigcubes do not form groups (due to their indistinguishable pieces). Someone should test this idea on a simpler puzzle with indistinguishable pieces, like the three-color 3x3x3.


----------



## shadowslice e (Jul 12, 2015)

qqwref said:


> Wrong. There are not 18 possible turns, but 36. (And the calculation is quite a bit more complicated than that anyway, because of turns on the same axis


How do you get 18/36 possible turns?


----------



## spyr0th3dr4g0n (Jul 12, 2015)

Stefan said:


> Hmm, I'm not 100% sure what you mean, but you just made me think of something.
> 
> God's 5x5x5 number might be higher than God's 5x5x5 number for a random state. In other words, God might be able to save moves by pulling a Steven Brundage.
> 
> ...



Would it be fair then to define God's number as the maximum distance between any two states?


----------



## Stefan (Jul 12, 2015)

spyr0th3dr4g0n said:


> Would it be fair then to define God's number as the maximum distance between any two states?



That's already called diameter. And I think "God's number" already is defined as the maximum number of moves needed to "solve" (to a specific "solved state").

Here's another puzzle, one with different average distances and different longest distances. (I hope I did that correctly...)






In this case, the "nonmixed" state is among those with smallest longest distance, though. And the "fully mixed" one is among those with largest longest distance, and is the one with largest average distance. Hrmpfh.


----------



## qqwref (Jul 12, 2015)

shadowslice e said:


> How do you get 18/36 possible turns?


18 is the 3x3x3 number: 6 faces (URFLDB) * 3 possible angles (R R' R2). For 5x5x5 there are two types of turns per face (R Rw). The 15^n computation is applicable to 3x3x3 only, because it's computing how many sequences you get if you don't use the same turn twice in a row (so each turn has 5 possible faces instead of 6, hence 5*3). Please understand the math before you use it


----------



## shadowslice e (Jul 12, 2015)

qqwref said:


> 18 is the 3x3x3 number: 6 faces (URFLDB) * 3 possible angles (R R' R2). For 5x5x5 there are two types of turns per face (R Rw). The 15^n computation is applicable to 3x3x3 only, because it's computing how many sequences you get if you don't use the same turn twice in a row (so each turn has 5 possible faces instead of 6, hence 5*3). Please understand the math before you use it



Ok, I'll admit I made a few small (ok, huge) mistakes when making my calculations.
1) I forgot to factor in the different angles of turns (so multiply my answer by 3)
2) I miscounted what turns could be made for each face- 5 as opposed to 4 (I counted 5 as I thought w1, w2, w3, w4, w5 and discounted the opposite face which gave my calculation as 5+5+5 possible turns).
3) I didn't factor in discounting the double moves on the same face.

So I do understand the maths (although i made a couple of small, ok, huge, mistakes. But hey, what is peer review for? ) and didn't just copy the 3x3x3 calculation.
 However, you also missed one thing- the calculation to perform the number of possible sequences would be 18x15^(n-1) as there would be no restrictions on what the first move would be.

So by extention could I not just redo the same calculation as 36x33^(n-1)?

If so then, we would need only 49 turns for the number of sequences to equal the number of possible permutations so thus I would reconclude that 60 is probably sufficient for a scramble.


----------



## qqwref (Jul 12, 2015)

shadowslice e said:


> However, you also missed one thing- the calculation to perform the number of possible sequences would be 16x15^(n-1) as there would be no restrictions on what the first move would be.


I didn't bring that up as I assumed you had also ignored it and were copying the 15^n from somewhere. The correct (but naive) computation is 18 * 15^(n-1) - or 36 * 33^(n-1) for 5x5x5. As I said, though, you have to take same-axis turns into account (you don't want to do R L R or R Rw R) and then it becomes a somewhat more complicated recursion, and the above numbers are just approximations.


----------



## shadowslice e (Jul 12, 2015)

qqwref said:


> As I said, though, you have to take same-axis turns into account (you don't want to do R L R or R Rw R) and then it becomes a somewhat more complicated recursion, and the above numbers are just approximations.



Well, we haven't even really done (as far as I'm aware) this calculation for 3x3x3 so, as far as I'm concerned until we crack 3x3x3 (other than by brute force) there's not much point trying to work out 5x5x5 (heck, we haven't (insofar as I have read) even done the brute force stuff for 4x4x4.)


----------



## unsolved (Jul 12, 2015)

shadowslice e said:


> Well, we haven't even really done (as far as I'm aware) this calculation for 3x3x3 so, as far as I'm concerned until we crack 3x3x3 (other than by brute force) there's not much point trying to work out 5x5x5 (heck, we haven't (insofar as I have read) even done the brute force stuff for 4x4x4.)



I've counted all 4x4x4 arrangements possible from the solved state through 32 moves. That's the first depth at which the unique move sequence count becomes greater than the total possible piece arrangemts, so it is naturally a lower bound for the 4x4x4 God's Number.

For the 5x5x5 I have the counts through move 50-something. I believe at 53 the number is bigger than the total combinations, so that would be the lower bound for the 5x5x5 if I am remembering correctly.


----------



## qqwref (Jul 12, 2015)

shadowslice e said:


> Well, we haven't even really done (as far as I'm aware) this calculation for 3x3x3 so, as far as I'm concerned until we crack 3x3x3 (other than by brute force) there's not much point trying to work out 5x5x5 (heck, we haven't (insofar as I have read) even done the brute force stuff for 4x4x4.)


I'm not sure what you're trying to say here. Obviously we are not going to actually figure out God's Number - I think I said this already.

The kind of calculation you posted is something which there is a lot of knowledge about, so I don't want someone to see your back-of-the-envelope wrong numbers and think they are the best known. The idea has been done many times (not just recently, but several years ago) and do actually provide decent lower bounds - that is, by calculating the number of positions you can get to with each number of moves, you can declare that God's Number has to be at least some number. I don't remember the exact numbers that come out of it (and it's slightly different for each possible way of counting moves), but it has been done and is probably a pretty good estimate.


----------



## Stefan (Jul 12, 2015)

If I didn't make a mistake, here are lower bounds for OBTM for cubes from 2x2x2 to 17x17x17. That uses the usual counting of scrambles by syllables.


```
n  moves  factor
-----------------
 2     9     6.00
 3    18    13.35
 4    35    20.73
 5    52    28.12
 6    75    35.51
 7    99    42.91
 8   128    50.31
 9   158    57.70
10   193    65.10
11   229    72.50
12   270    79.90
13   312    87.30
14   359    94.69
15   406   102.09
16   458   109.49
17   511   116.89
```

The "factor" is the branching factor of the last step.



Spoiler: Program





```
from math import factorial as f

def nCk(n, k):
    return f(n) // f(k) // f(n-k)

print(' n  moves  factor')
print('-----------------')
for n in range(2, 18):

    # Compute the number of states
    states = (24 * f(12) * 2**10)**(n%2) * f(7) * 3**6 * f(24)**((n**2-2*n)//4) // f(4)**(6*((n-2)**2//4))

    # Compute the number of scrambles, scrambles[m] := number of scrambles with m moves
    scrambles = [1]
    while sum(scrambles) < states:
        moves = len(scrambles)
        scrambles += sum((2 + (k == moves)) * nCk(n-1, k) * 3**k * scrambles[-k]
                         for k in range(1, min(n, moves+1))),

    print('%2d  %4d  %7.2f' % (n, moves, scrambles[-1] / scrambles[-2]))
```
The states-formula is [post=618528]from Chris[/post].


----------



## shadowslice e (Jul 13, 2015)

qqwref said:


> I'm not sure what you're trying to say here. Obviously we are not going to actually figure out God's Number - I think I said this already.


I'm saying that no one has ever written a paper based on mathematical concepts (such as vectors, group theory etc) that proves conclusively god's number for 3x3x3 is 20. The only reason we know that it is 20 is because we just crunched through every possible cube state and found a 20 move solution for all of them.



qqwref said:


> The kind of calculation you posted is something which there is a lot of knowledge about, so I don't want someone to see your back-of-the-envelope wrong numbers and think they are the best known.



I never claimed that it was the best we had- I was merely answering the question posed at the start of the thread- how many moves do we have to make before the total number of sequences of moves is greater than the number of possible permutations for a 5x5x5? (This was why it was stated that we established the lower bound for 3x3x3 as 18 and 4x4x4 as 32)


----------



## Stefan (Jul 13, 2015)

shadowslice e said:


> no one has ever written a paper based on mathematical concepts (such as vectors, group theory etc) that proves conclusively god's number for 3x3x3 is 20. The only reason we know that it is 20 is because we just crunched through every possible cube state and found a 20 move solution for all of them.



Here's a paper: http://tomas.rokicki.com/rubik20.pdf

And quite a bit of mathematical concepts went into it, especially group theory. Given that you recently didn't even know what commutators are, I suspect that you don't even understand the math that you just downplayed.


----------



## shadowslice e (Jul 13, 2015)

Stefan said:


> Here's a paper: http://tomas.rokicki.com/rubik20.pdf
> 
> And quite a bit of mathematical concepts went into it, especially group theory. Given that you recently didn't even know what commutators are, I suspect that you don't even understand the math that you just downplayed.



Did it sound like I was downplaying the maths? I definately didn't mean to. I know that a huge amount of effort and maths was placed into finding god's number but my point was that they still did have to crunch some numbers eventually- no matter all the amazing maths and insight they put into reducing and partitioning the cube space and number of cosets/subgroups they had to solve.

While I in no way mean to downplay what they did (I consider it to be one hell of an achievement), my point is that there is no purely mathematical paper that proves god's number without having to crunch through a few (albeit greatly reduced) cube states eventually (and, to be honest, I'm not entirely convinced this is possible and what these people achieved is likely the best we might ever had)

Thanks for the paper by the way, I was wondering where the 20-move proof was!


----------



## Renslay (Jul 13, 2015)

Stefan said:


> That's already called diameter. And I think "God's number" already is defined as the maximum number of moves needed to "solve" (to a specific "solved state").
> 
> Here's another puzzle, one with different average distances and different longest distances. (I hope I did that correctly...)
> 
> In this case, the "nonmixed" state is among those with smallest longest distance, though. And the "fully mixed" one is among those with largest longest distance, and is the one with largest average distance. Hrmpfh.



A stickerless Square-1 is something similar.

http://www.jaapsch.net/puzzles/images/square1/shapes.gif

Although this graph is not the full graph, I think here the average distances and the longest distances also differ.


----------



## Stefan (Jul 13, 2015)

Renslay said:


> A stickerless Square-1 is something similar.
> 
> http://www.jaapsch.net/puzzles/images/square1/shapes.gif
> 
> Although this graph is not the full graph, I think here the average distances and the longest distances also differ.



Average is clear, since the average distance of the double-square state is clearly larger than that of its only neighbor.


----------



## Herbert Kociemba (Jul 13, 2015)

Stefan said:


> If I didn't make a mistake, here are lower bounds for OBTM and SSTM for cubes from 2x2x2 to 17x17x17. That uses the usual counting of scrambles by syllables.
> 
> 
> ```
> ...



This is OBTM, for SSTM the bounds are smaller, see http://cubezzz.dyndns.org/drupal/?q=node/view/236.
The asymptotic branching factor for OBTM is btw. 3/(1.5^(1/(-1+n))-1) which is more or less the factor of the last step.


----------



## Stefan (Jul 13, 2015)

Herbert Kociemba said:


> This is OBTM, for SSTM the bounds are smaller, see http://cubezzz.dyndns.org/drupal/?q=node/view/236.



Thanks. I took out the "and SSTM". Oh well, good to see that at least my OBTM seems correct 



Herbert Kociemba said:


> The asymptotic branching factor for OBTM is btw. 3/(1.5^(1/(-1+n))-1) which is more or less the factor of the last step.



Wow, how did you get that?


----------



## Herbert Kociemba (Jul 14, 2015)

Stefan said:


> Wow, how did you get that?



I derived this several years ago and I can't remember the details any more. The recursion for the number of positions in k moves can be written as (A^k)*x with some matrix A and some vector x and the largest eigenvalue of A then is the asymptotic branching factor. In OBTM and QTM instead of HTM, the asymtptotic branching factor is 1/(1.5^(1/(2(n-1)))-1).


----------



## Stefan (Jul 14, 2015)

Herbert Kociemba said:


> I derived this several years ago and I can't remember the details any more. The recursion for the number of positions in k moves can be written as (A^k)*x with some matrix A and some vector x and the largest eigenvalue of A then is the asymptotic branching factor. In OBTM and QTM instead of HTM, the asymtptotic branching factor is 1/(1.5^(1/(2(n-1)))-1).



Cool, thanks. I wouldn't be able to do it (at least not now), but I think I understand the rough idea. At least it's not something trivial that I just missed


----------



## Herbert Kociemba (Jul 14, 2015)

I also found a closed formula for the number of maneuvers on the the (n+1)*(n+1)*(n+1) cube in OBTM which is not very handy as you might imagine.

With 

bh[n_,j_]:=3/((3/2)^(1/n) e^((2 i j Pi)/n)-1), where e, i and Pi are the well known mathematical constants, we have for the count in k moves: 

countHW[n_,k_]:=Sum[(3+bh[n,j])/(6n) bh[n,j]^k,{j,0,n-1}]

In QTM it is

bq[n_,j_]:=1/((3/2)^(1/(2n)) e^(( i j Pi)/n)-1)

countQW[n_,k_]:=Sum[(1+bq[n,j])/(4n) bq[n,j]^k,{j,0,2n-1}]

The asymptotic branching factors just are bh[n,0] and bq[n,0].

EDIT: If you ignore all terms with j>0 in the sums above you still get very good approximations with lim approxvalue/truevalue =1 for k->infinity.
This means

approxcount(n,k):=(2^(-((1 + n)/n)) 3^(k + 1/n) (1/(-1 + 1.5^(1/n)))^(1 + k))/n

is a good approximation for the number of maneuvers of length k for the (n+1)*(n+1)*(n+1) cube in OBTM.


----------



## TheGermanCuber (Aug 24, 2015)

Does anybody know how to calculate a god's number ?


----------



## unsolved (Sep 6, 2015)

TheGermanCuber said:


> Does anybody know how to calculate a god's number ?



The easiest way to get the exact number is also the least likely way.

Just say something like: "Hey, God, what's your number for the 5x5x5?" and wait for an answer.


----------

