|
%I #35 Apr 07 2022 10:56:26
%S 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,
%T 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,
%U 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
%N 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).
%H <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F From _M. F. Hasler_, Mar 29 2022: (Start)
%F 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.
%F (Here and below, m is any integer > log_4(k).)
%F 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)
%e 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, ...
%o (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
%o 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: */
%o 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])
%o \\ _M. F. Hasler_, Mar 29 2022
%Y Cf. A060573 (smallest on peg 0), A060575 (smallest on peg 2), A055662 (whole configuration).
%Y Cf. A001511, A060571, A060572.
%K easy,nonn
%O 0,5
%A _Henry Bottomley_, Apr 03 2001
|
