Okay, yeah, so here's how the bigcubes maths works (or at least where I got 73 and 95 from). We don't know the length of God's Algorithm, but we can find an easy lower bound by calculating the number of moves it would take to have a greater number of possible scrambles than the number of positions on the puzzle. The number of positions is well-known and easy to calculate, but the number of positions for each scramble (if you want it exactly) follows a rather complicated recurrence relation. But anyway, for a 3x3x3 (for example) it takes 17 moves' worth of scrambling to get at least 4.3 * 10^19 possible scrambles, so thus any scrambling algorithm under 17 moves cannot possibly reach every position and is unacceptable. This also means that there will be optimal solutions of at least 17 moves for a 3x3x3. But you can do this with pretty much any puzzle if you are willing to work on the relation. (By the way I think it was my idea to do this for bigcubes and other weird puzzles first XD)
Anyway, the same calculations for 3x3 through 7x7 give minimum required move-counts of 17, 31, 50, 73, and 95. Note that these are the same numbers whether we use slice or multislice, since the number of possible scrambles are the same. Incidentally the number of moves for megaminx is 43 and the number for gigaminx is approximately 135 (perhaps slightly higher, since I used an approximate number-of-scrambles formula for this one because the recurrence relation was too complicated). Using the new megaminx scrambles would require a mind-boggling 226 moves (including cube rotations), by the way.
That is indeed the theory I thought it would be. However it amazes me that the number of moves needed grows in this way. 14 -> 19 -> 23 -> 22. So let me get this straight:
For a 3x3x3 there are 6 possible moves (RLUDFB) and for every move there are 3 variations (normal, half and back). I am assuming that slices turns are not allowed. This could be simplified to:
3-axis (RUF)
2 moves for every axe (RL, UD, FB or more generally: 1R 2R, 1U, 2U, 1F 2F)
3 variations (1, 2, 3)
All these possibilities are independent from each other so they give 3x2x3=18 possibilities for the n=1 moves.
For n=2 moves there would be 18^2 possibilites, but because of the relation you mentioned it will be less (1R1 + 1R2 = 1R3, 1U1 + 2U2 = 2U2 + 1U1, 2F2 + 2F2 = 1R1 + 1R3, etc)
I wonder if you have a generic way to determine the relation and if I am correct in assuming that for a 7x7x7 there would be:
3-axis, (7-1 = 6) moves for every axe, 3 variations = 3*6*3 = 54 possibilities for the first move and 54^95 (-relation) after 95 moves.
I always assumed that the number of possibilities formula (3*(n-1)*3)^n (minus relation) would grow so fast that something like this could be true
Count(godsAlgorithmForCubeN) = 10*(N-1) (+1 for even N's)
So 0 for 1x1x1, 11 for 2x2x2, 20 for 3x3x3, 31 for 4x4x4, 40 for 5x5x5, etc.
