|
Search: id:A137695
|
|
|
| A137695 |
|
Tower of Hanoi with p pegs: Number of moves needed for n disks, using Frame's or Stewart's algorithm (formatted as upper right triangle). |
|
+0
1
|
|
| 1, 3, 3, 7, 5, 5, 15, 9, 7, 7, 31, 13, 11, 9, 9, 63, 17, 15, 13, 11, 11, 127, 25, 19, 17, 15, 13, 13, 255, 33, 23, 21, 19, 17, 15, 15, 511, 41, 27, 25, 23, 21, 19, 17, 17, 1023, 49, 31, 29, 27, 25, 23, 21, 19, 19, 2047, 65, 39, 33, 31, 29, 27, 25, 23, 21, 21, 4095, 81, 47, 37, 35
(list; table; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
In the cited paper by Klavzar et al. it is proved that Frame's algorithm and Stewart's algorithm, as well as several variations, all yield the same number of minimal moves for the n disk, p peg problem, given by the formula for X(n,p).
This sequence lists the elements of the upper right triangle of the matrix having as rows the number of moves required, depending on the number of disks, for a given number of pegs. (The 1st row refers to 3 pegs, etc.) The lower left triangle of the matrix is uninteresting, since all elements below a given diagonal element are equal to that element, namely 2n-1. (For p>n, each disk can be moved to a separate peg.)
|
|
LINKS
|
S. Klavzar et al., On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem, Discrete Applied Mathematics 120 (2002) 141-15 and references therein.
|
|
FORMULA
|
X(n,p) = sum( t=0,s-1, 2^t*binomial(p-3+t,p-3))+2^s*(n-binomial(p-3+s,p-2)) where s = max { k in Z | n > binomial(p-3+k,p-2) }
|
|
EXAMPLE
|
The complete matrix would read
(1st row: 3 pegs, A000225; 2nd row: 4 pegs, A007664; 3rd row: 5 pegs, A007665.)
[1 3 7 15 31 63 127 255 511 1023 ...]
[1 3 5 9 13 17 25 33 41 49 ...]
[1 3 5 7 11 15 19 23 27 31 ...]
[1 3 5 7 9 13 17 21 25 29 ...]
[1 3 5 7 9 11 15 19 23 27 ...]
[1 3 5 7 9 11 13 17 21 25 ...]
[1 3 5 7 9 11 13 15 19 23 ...]
[1 3 5 7 9 11 13 15 17 21 ...]
[1 3 5 7 9 11 13 15 17 19 ...]
|
|
PROGRAM
|
(PARI) X(n, p)={local(s=1, t=0); while( n>binomial(p-2+t++, p-2), s+=2^t*binomial(p-3+t, p-3)); s+2^t*(n-binomial(p-3+t, p-2))}
A137695(n)=X(t=1+sqrtint(2*n-2-sqrtint(2*n-2)), 2+n-t*(t-1)/2)
|
|
CROSSREFS
|
Cf. A000225, A007664, A007665.
Sequence in context: A085870 A096633 A118362 this_sequence A086799 A161427 A098688
Adjacent sequences: A137692 A137693 A137694 this_sequence A137696 A137697 A137698
|
|
KEYWORD
|
easy,nice,nonn,tabl
|
|
AUTHOR
|
M. F. Hasler (Maximilian.Hasler(AT)gmail.com), Feb 09 2008, revised Feb 10 2008
|
|
|
Search completed in 0.002 seconds
|
