

A060574


Tower of Hanoi: using the optimal way to move an even number of disks from peg 0 to peg 2 or an odd number from peg 0 to peg 1, a(n) is the smallest disk on peg 1 after n moves (or 0 if there are no disks on peg 1).


5



0, 1, 1, 0, 3, 3, 2, 1, 1, 2, 3, 3, 0, 1, 1, 0, 5, 5, 2, 1, 1, 2, 5, 5, 4, 1, 1, 4, 3, 3, 2, 1, 1, 2, 3, 3, 4, 1, 1, 4, 5, 5, 2, 1, 1, 2, 5, 5, 0, 1, 1, 0, 3, 3, 2, 1, 1, 2, 3, 3, 0, 1, 1, 0, 7, 7, 2, 1, 1, 2, 7, 7, 4, 1, 1, 4, 3, 3, 2, 1, 1, 2, 3, 3, 4, 1, 1, 4, 7, 7, 2, 1, 1, 2, 7, 7, 6, 1, 1, 6, 3, 3, 2, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


LINKS

Table of n, a(n) for n=0..104.
Index entries for sequences related to Towers of Hanoi


FORMULA

From M. F. Hasler, Mar 29 2022: (Start)
a(3k+1) = a(3k+2) = 2*b(k) + 1, where b(k) = valuation_4((k OR 2*(4^m1)/3)+1) is the number of times k must be divided by 4 (discarding a remainder) until the result is even, i.e., the position of the rightmost even base4 digit of k.
(Here and below, m is any integer > log_4(k).)
a(6k) = a(6k+3) = 2*c(k), where c(k) = 1 + valuation_4(k AND (4^m1)/3) is the number of times 2*k must be divided by 4 (discarding a remainder) until the result is odd (i.e., the position of the rightmost odd base4 digit in 2*k), or c(k) = 0 if this never happens <=> n is in 12*A000695 + {0, 3} <=> a(n) = 0. (End)


EXAMPLE

Start by moving first disk from peg 0 to peg 1, second disk from peg 0 to peg 2, first disk from peg 1 to peg 2, etc. so sequence starts 0, 1, 1, 0, ...


PROG

(PARI) A060574_upto(n, p=[[]n<[1..3]])={p[1]=[1..n]; vector(2^n1, n, my(a = n\2%3+1, b = a%3+1); bittest(n, 0)  if( !p[a = b%3+1]  (#p[b] && p[b][1] < p[a][1]), [a, b] = [b, a]); p[b] = concat(p[a][1], p[b]); p[a] = p[a][^1]; if(p[2], p[2][1]))} \\ This produces the sequence for n pegs, i.e., of length 2^n1 !  M. F. Hasler, Mar 28 2022
apply( {A060574(n, t=n%3>0)=n\=3<<!t; for(k=1, oo, n%2==treturn(k*2t); (n\=4)  t  break)}, [0..99]) /* or alternate code, illustrating the formula: */
apply( {A060574(n)= if ( n%3, 1+2*valuation(1+bitor(n\3, 4^exponent(n)\6), 4), n && n = bitand(n\6, 4^exponent(n)\3), 2*valuation(n, 4)+2, 0)}, [0..99])
\\ M. F. Hasler, Mar 29 2022


CROSSREFS

Cf. A060573 (smallest on peg 0), A060575 (smallest on peg 2), A055662 (whole configuration).
Cf. A001511, A060571, A060572.
Sequence in context: A065744 A016455 A278702 * A283987 A286443 A075522
Adjacent sequences: A060571 A060572 A060573 * A060575 A060576 A060577


KEYWORD

easy,nonn


AUTHOR

Henry Bottomley, Apr 03 2001


STATUS

approved



