|
| |
|
|
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
|
|
|
|
FORMULA
|
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])
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
