A101607 a(2n) = 7 - a(n), a(2n+1) = (n-1 mod 3) + 1.

1, 6, 2, 1, 3, 5, 1, 6, 2, 4, 3, 2, 1, 6, 2, 1, 3, 5, 1, 3, 2, 4, 3, 5, 1, 6, 2, 1, 3, 5, 1, 6, 2, 4, 3, 2, 1, 6, 2, 4, 3, 5, 1, 3, 2, 4, 3, 2, 1, 6, 2, 1, 3, 5, 1, 6, 2, 4, 3, 2, 1, 6, 2, 1, 3, 5, 1, 3, 2, 4, 3, 5, 1, 6, 2, 1, 3, 5, 1, 3, 2, 4, 3, 2, 1, 6, 2, 4, 3, 5, 1, 3, 2, 4, 3, 5, 1, 6, 2, 1, 3, 5

Offset: 1

Author

Ralf Stephan, Dec 09 2004

Keywords

• nonn
• easy

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

Examples

			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).
		

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.
• Index entries for sequences that are fixed points of mappings
• Index entries for sequences related to Towers of Hanoi

Crossrefs

See A101608 for the move pairs. Cf. A000225.

Programs

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]

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].