It would be awfully hard to prove that a given pattern always requires as many moves as possible. Sure, if we somehow did it it would help, but I'm not seeing any way it could be done, or any obvious patterns that would fit the bill.

This is exactly how people compute lower bounds for God's Algorithm.

Yes. And here is a generating function I developed some times ago for the number of "canonical sequences" (where commutating moves and cancellations like U U' etc. are taken into account) in OBTM for all NxNxN cubes.

This means, the Taylor expansion of this functions gives the number of maneuvers with a certain length.

Mathematica Code:

gfh[n_,x_]:= 3/(6-4(3x+1)^(n-1))-1/2

In[12]:= Series[gfh[4,x],{x,0,7}]

Out[12]= 1+27 x+567 x^2+11745 x^3+243486 x^4+5047596 x^5+104639202 x^6+2169224064 x^7+O[x]^8

This means, on the 4x4x4 there are for example 567 maneuvers with length 2

The corresponding generating function for the summed up maneuver length is gfh[n,x]/(1-x)

In[13]:= Series[gfh[4,x]/(1-x),{x,0,7}]

Out[13]= 1+28 x+595 x^2+12340 x^3+255826 x^4+5303422 x^5+109942624 x^6+2279166688 x^7+O[x]^8

This means there are for example 595 maneuvers on the 4x4x4 with length at most 2 in OBTM.

Together with Chris Hardwick's(?) formula for the number of positions on the NxNxN it is now easy to get lower bounds.

Starting with 2x2x2 the lower bounds are

{9,18,35,52,75,99,128,158,193,229,270,312,359,406,458,511,568,626,690....}

Of course I cannot prove this (except for 2x2x2 and 3x3x3

), but I am sure, that God's number is only 2 or 3 moves away from these lower bounds, so for 4x4x4 I assume 37 or 38.