|
| |
|
|
A101607
|
|
a(2n) = 7 - a(n), a(2n+1) = (n-1 mod 3) + 1.
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
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]
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
