OFFSET
0,5
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)
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^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<<!t; for(k=1, oo, n%2==t||return(k*2-t); (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
KEYWORD
easy,nonn
AUTHOR
Henry Bottomley, Apr 03 2001
STATUS
approved