Rubik cube sequence?

[Alex Healy]

Just to clarify, the sequence I computed is the number of positions that
*can be reached* in n moves, and not just those that *require* n moves.  To
get the latter, you can take the difference successive terms (after the
first couple), on account of the 3-cycle that I noted in my previous
message.  This sequence is the most natural to output because I'm
essentially solving a big dynamic programming problem, so the lists that are
floating around are all of length a(n), where a(.) is this sequence.

Alex 

> -----Original Message-----
> From: Brian L. Galebach [mailto:briang at SEGmail.com] 
> Sent: Friday, February 21, 2003 5:33 PM
> To: seqfan at ext.jussieu.fr
> Cc: briang at ProbabilitySports.com
> Subject: RE: Rubik cube sequence?
> 
> 
> Hello,
> 
> I can't tell by quick inspection of the terms given so far, 
> but I just wanted to make sure you were calculating the same 
> thing as in A079761.  That sequence gives the number of 
> positions that are n moves away from being solved.  
> Translated another way would be "positions reachable in at 
> most n moves".  Therefore, the 100th term of the sequence, 
> for example, would be 0, whereas "reachable in n moves" or 
> "reachable within n moves" would give the total number of 
> combinations in the cube.
> 
> Brian
> 
> -----Original Message-----
> From: Alex Healy [mailto:ahealy at fas.harvard.edu]
> Sent: Friday, February 21, 2003 5:13 PM
> To: seqfan at ext.jussieu.fr
> Cc: njas at research.att.com
> Subject: RE: Rubik cube sequence?
> 
> 
> As promised, here is the (beginning of the) sequence for the 
> 3x3x3 cube. Again, half-twists count as a move, so there are 
> 18 positions reachable in 1 move, etc.  The distinction 
> between positions reachable "in n moves" and positions 
> reachable "within n moves" vanishes after 2 moves because 
> there is a cycle of length 3, e.g. (R, R^2, R).  Here's the sequence:
> 
> 1, 18, 262, 3502, 46741, 621649, 8240087
> 
> I was having trouble with memory usage, but maybe with a 
> little tweaking I'll be able to get another term or so.  This 
> is it for now, though.
> 
> Alex
> 
> 
> > -----Original Message-----
> > From: N. J. A. Sloane [mailto:njas at research.att.com]
> > Sent: Friday, February 21, 2003 1:50 PM
> > To: seqfan at ext.jussieu.fr
> > Subject: Rubik cube sequence?
> >
> >
> > Inspired by Jaap Scherphuis's excellent web site
> > on generalizations of Rubik's cube,
> > i've added several sequences to the OEIS giving the number
> > of positions that are n moves away from the start in
> > these puzzles.  For example:
> >
> > %I A079761
> > %S A079761 
> > 1,9,54,321,1847,9992,50136,227536,870072,1887748,623800,2644
> > %N A079761 Number of positions that are n moves from the starting 
> > position in the 2 X 2 X 2 Rubik cube puzzle. %C A079761 A puzzle in 
> > the Rubik cube family. The total number of distinct positions is 
> > 3674160. A half-turn is considered to be one move.
> > %D A079761 D. R. Hofstadter, Metamagical Themas, Basic Books,
> > NY, 1985, p. 359.
> > %H A079761 Jaap Scherphuis, <a
> > href="http://www.geocities.com/jaapsch/puzzles/">Puzzle Pages</a>
> > %K A079761 nonn,fini,full,new
> > %O A079761 0,2
> > %A A079761 njas, Feb 20 2003
> >
> > Does anyone know the analogous sequence for the 3 X 3 X 3 cube, or 
> > even the beginning of that sequence?
> >
> > NJAS
> >
>