# God's number is...

#### Tim Reynolds

$$\Theta(n^2/\log n)$$ (for an n x n x n Rubik's Cube)

http://arxiv.org/abs/1106.5736

Haven't read the paper yet, probably will tonight.

THIS IS AN ASYMPTOTIC BOUND, NOT AN EXACT NUMBER. DON'T JUST PLUG IN n=3 AND EXPECT TO GET 20.

Last edited:

#### d4m4s74

##### Member
my math is off, what's god's number on the 3x3x3 according to this?

I mean, if I take Θ(n^2/log n), change the n into 3 (I assume that's correct because they're talking about nxnxn puzzles) I get Θ(3^2/log 3) which according to wolphram alpha equals 1. that can't be it...

Last edited:

#### Owen

##### Member
This cannot possibly work...

I can't wait for one of our mathematicians to come in here and explain it.

#### Goosly

##### Member
I'm curious for a simplified summary of the paper I don't like reading theoretical things like this anymore, especially since my exams ended only 2 days ago.

#### Stefan

##### Member
my math is off, what's god's number on the 3x3x3 according to this?

I mean, if I take Θ(n^2/log n), change the n into 3 (I assume that's correct because they're talking about nxnxn puzzles) I get Θ(3^2/log 3) which according to wolphram alpha equals 1. that can't be it...
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.

It's similar to saying that "bacteria colonies grow exponentially" or "your hair grows linearly". You don't get exact numbers, but it does tell you the "kind" of growth speed.

Last edited:

#### Owen

##### Member
Because the way the previous posters interpreted it, it made no sense that you could just plug a number into this simple formula, and get god's number.
This was later confirmed by Stefan Pochmann.

#### aronpm

##### Member
Because the way the previous posters interpreted it, it made no sense that you could just plug a number into this simple formula, and get god's number.
This was later confirmed by Stefan Pochmann.
Previous posters... a 12 year old and someone who copy+pasted it to W|A? Learn what the big theta notation means before you say "it's not possible"

#### MTGjumper

##### Member
Well, saying "this cannot possibly work" implies that you disagree what was originally posted.

#### d4m4s74

##### Member
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.

It's similar to saying that "bacteria colonies grow exponentially" or "your hair grows linearly". You don't get exact numbers, but it does tell you the "kind" of growth speed.
Thanks for the clarification, I should have read more then just the abstract.

Damn, ever since I dropped out I started forgetting a lot, I learned about and used the big O less then a year ago.

#### Stefan

##### Member
Seems to be a nice article (except I disagree with the opening paragraph claiming the 20-moves-team didn't evaluate all positions).

#### Stefan

##### Member
Seems to be a nice article (except I disagree with the opening paragraph claiming the 20-moves-team didn't evaluate all positions).
I just realized that they don't properly report about the lower bound, so I don't like that, either. The New Scientist article is worse in some respects, good in others.

#### qqwref

##### Member
I looked at the paper, and it was impressive, but not as amazing as it sounded. I have a mixed reaction to the God's Number result; on one hand, it's cool that they established a better upper bound (i.e. a better general solution), but on the other hand establishing something is Θ(n^2/log n) is only useful for computability theorists. It's an interesting-sounding result, but doesn't really have much practical use IMO, because saying that some sequence follows a particular pattern of growth as it goes to infinity doesn't tell us anything about individual values, and we only have two values of the series calculated anyway (11, 20, ...) with a third being very far off.

The "optimal solution of a*b*n can be found in polynomial time on n" result is similar; it sounds interesting, but it's only useful in a mathematical sense to establish a bound for the infinite series, and doesn't really make it easier to actually do the solving. The technique used in the proof relies on brute force, and while it is polynomial in n (it looks to be O(n) but I'm not sure) it involves extremely large constants and thus has no real practical use.

#### Jorghi

##### Member
Well the programs that say "20 moves or less" simply just use bruteforcing methods to solve the cube. Though we don't really know how optimal the moves are and because it could take a long time to find a better solution.

Unless there is pure mathematical proof xD ;P

#### qqwref

##### Member
Though we don't really know how optimal the moves are and because it could take a long time to find a better solution.
Of course we know an optimal solution's optimal. The techniques for finding them are quite foolproof.

#### kprox1994

##### Member
Scientists Develop an Algorithim to Solve Cubes of any Size.

Found this browsing engadget, pretty interesting. http://www.engadget.com/2011/07/01/scientists-develop-algorithm-to-solve-rubiks-cubes-of-any-size/&category=classic&altPost=alt&icid=eng_latest_art Can someone link this? It's too hard to do on my phone.

Last edited: