1,2

Fixed point of morphism 1->16, 2->35, 3->42, 4->13, 5->32, 6->21.

Solution to Tower 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. For a tower of k disks use the first 2^k-1 numbers. The disks are moved from peg 1 to 2.

J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences.. In F. Axel and D. Gratias, editors, Beyond Quasicrystals, pages 293-367. Les \'Editions de Physique/Springer, 1995.

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

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

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

See A101608 for the move pairs. Cf. A000225.

Sequence in context: A021621 A120002 A021165 this_sequence A039508 A002247 A124913

Adjacent sequences: A101604 A101605 A101606 this_sequence A101608 A101609 A101610

nonn,easy

Ralf Stephan, Dec 09 2004