login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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
Cf. A060573 (smallest on peg 0), A060575 (smallest on peg 2), A055662 (whole configuration).
Sequence in context: A065744 A016455 A278702 * A283987 A286443 A075522
KEYWORD
easy,nonn
AUTHOR
Henry Bottomley, Apr 03 2001
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 09:28 EDT 2024. Contains 371268 sequences. (Running on oeis4.)