cp's OEIS Frontend

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

%I A101607 #36 May 02 2021 10:53:51
%S A101607 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,
%T A101607 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,
%U A101607 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
%N A101607 a(2n) = 7 - a(n), a(2n+1) = (n-1 mod 3) + 1.
%C A101607 Fixed point of morphism 1->16, 2->35, 3->42, 4->13, 5->32, 6->21.
%C A101607 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.
%C A101607 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).
%C A101607 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
%H A101607 Jean-Paul Allouche and Roland Bacher, <a href="http://dx.doi.org/10.5169/seals-59494">Toeplitz Sequences, Paperfolding, Towers of Hanoi, and Progression-Free Sequences of Integers</a>, L'Enseignement Mathématique, volume 38, pages 315-327, 1992.
%H A101607 J.-P. Allouche and M. Mendes France, <a href="https://webusers.imj-prg.fr/~jean-paul.allouche/allmendeshouches.pdf">Automata and Automatic Sequences</a>, 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.
%H A101607 J.-P. Allouche and M. Mendes France, <a href="/A003842/a003842.pdf">Automata and Automatic Sequences</a>, 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]
%H A101607 Dimitri Hendriks, Frits G. W. Dannenberg, Jorg Endrullis, Mark Dow and Jan Willem Klop, <a href="http://arxiv.org/abs/1201.3786">Arithmetic Self-Similarity of Infinite Sequences</a>, arXiv preprint 1201.3786 [math.CO], 2012.
%H A101607 <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>
%H A101607 <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F A101607 a(n) = 3 - (3/2)[(-1)^A007814(n)-1] - (n+1 mod 3).
%F A101607 G.f.: -7 + Sum[k>=0, (3t^5 + 7t^4 + 2t^3 + 7t^2 + t + 7)/(1-t), t=x^2^k].
%e A101607 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).
%o A101607 (PARI) a(n)=3-3/2*((-1)^valuation(n,2)-1)-((n+1)%3)
%o A101607 (PARI) a(n)=if(n<2,n>0,if(n%2,(((n-1)/2)%3)+1,7-a(n/2)))
%o A101607 (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]
%Y A101607 See A101608 for the move pairs. Cf. A000225.
%K A101607 nonn,easy
%O A101607 1,2
%A A101607 _Ralf Stephan_, Dec 09 2004