OFFSET
1,2
COMMENTS
Fixed point of morphism 1->16, 2->35, 3->42, 4->13, 5->32, 6->21.
Solution to the Towers of Hanoi puzzle encoded by replacing the moves (1,2), (2,3), (3,1), (2,1), (3,2), (1,3) with the numbers 1, 2, 3, 4, 5, 6. The first 2^{k-1} moves of the sequence transfer the top k disks from peg 1 to peg 2 if k is odd, and from peg 1 to 3 if k is even.
Another way to generate this sequence is as a Toeplitz word (see the reference to Allouche and Bacher below), as follows. First take the periodic sequence 1, ?, 2, ?, 3, ?, 1, ?, 2, ?, ... over the alphabet {1, 2, 3, ?} where ? is a new symbol called a "gap". Next fill the gaps by the f-image of the sequence itself, where f is a bijection on the set of moves defined by f(1) = 6, f(2) = 5, f(3) = 4. Then we obtain 1, f(1), 2, f(f(1)), 3, f(2), 1, f(f(f(1))), 2, f(3), ... = 1, 6, 2, 1, 3, 5, 6, 2, 4, ... . The explanation is as follows: Starting from the first move every second move the smallest disk is transferred, in a clockwise fashion (imagining the pegs to be positioned triangularly, 1 - 2 - 3 clockwise).
Thus the odd positions of the sequence are terms 1, 2, 3, 1, 2, ... . At the even positions we find the 'twin' of the sequence, that is, the sequence with the roles of pegs 2 and 3 interchanged. This is exactly what the function f as defined above does. - Dimitri Hendriks, Jul 19 2010
LINKS
Jean-Paul Allouche and Roland Bacher, Toeplitz Sequences, Paperfolding, Towers of Hanoi, and Progression-Free Sequences of Integers, L'Enseignement Mathématique, volume 38, pages 315-327, 1992.
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]
Dimitri Hendriks, Frits G. W. Dannenberg, Jorg Endrullis, Mark Dow and Jan Willem Klop, Arithmetic Self-Similarity of Infinite Sequences, arXiv preprint 1201.3786 [math.CO], 2012.
FORMULA
a(n) = 3 - (3/2)[(-1)^A007814(n)-1] - (n+1 mod 3).
G.f.: -7 + Sum[k>=0, (3t^5 + 7t^4 + 2t^3 + 7t^2 + t + 7)/(1-t), t=x^2^k].
EXAMPLE
The morphism gives 1 -> 16 -> 1621 -> 16213516. The first 2^3-1 numbers are 1, 6, 2, 1, 3, 5, 1, so the solution to the 3-disk puzzle is (1,2), (1,3), (2,3), (1,2), (3,1), (3,2), (1,2).
PROG
(PARI) a(n)=3-3/2*((-1)^valuation(n, 2)-1)-((n+1)%3)
(PARI) a(n)=if(n<2, n>0, if(n%2, (((n-1)/2)%3)+1, 7-a(n/2)))
(PARI) a(n)=local(s1, s2, m); m=[1, 6; 3, 5; 2, 4; 1, 3; 3, 2; 2, 1]; s1=[1]; for(n=1, 10, s2=vector(2*#s1); for(k=1, #s1, s2[2*k-1]=m[s1[k], 1]; s2[2*k]=m[s1[k], 2]); s1=s2); s2[n]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ralf Stephan, Dec 09 2004
STATUS
approved