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).
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
Offset: 0
Examples
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, ...
Crossrefs
Programs
-
PARI
A060574_upto(n, p=[[]|n<-[1..3]])={p[1]=[1..n]; vector(2^n-1, 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^n-1 ! - M. F. Hasler, Mar 28 2022 apply( {A060574(n,t=n%3>0)=n\=3<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
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^m-1)/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 base-4 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^m-1)/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 base-4 digit in 2*k), or c(k) = 0 if this never happens <=> n is in 12*A000695 + {0, 3} <=> a(n) = 0. (End)