|
| |
|
|
A007664
|
|
Reve's puzzle: number of moves needed to solve the Towers of Hanoi puzzle with 4 pegs and n disks, according to the Frame-Stewart algorithm.
(Formerly M2449)
|
|
13
|
|
|
|
0, 1, 3, 5, 9, 13, 17, 25, 33, 41, 49, 65, 81, 97, 113, 129, 161, 193, 225, 257, 289, 321, 385, 449, 513, 577, 641, 705, 769, 897, 1025, 1153, 1281, 1409, 1537, 1665, 1793, 2049, 2305, 2561, 2817, 3073, 3329, 3585, 3841, 4097, 4609, 5121, 5633
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
The Frame-Stewart algorithm minimizes the number of moves a(n) needed to first move k disks to an intermediate peg (requiring a(k) moves), then moving the remaining n-k disks to the destination peg without touching the k smallest disks (requiring 2^(n-k)-1 moves) and finally moving the k smaller disks to the destination.
This leads to the given recursive formula a(n) = min{...}. It follows that the sequence of first differences is A137688 = (1,2,2,4,4,4,...) = 2^A003056(n), which in turn gives the explicit formulas for a(n) as partial sums of A137688.
"Numerous others have rediscovered this algorithm over the years [several references omitted]; many of these failed to derive the correct value for the parameter i, most mistakenly thought that they had actually proved optimality and almost none contributed anything new to what was done by Frame and Stewart". [Stockmeyer]
Numbers of the form 2^k+1 appear for n = 2, 3, 4, 6, 8, 11, 15, 15+4 = 19, 19+5 = 24, 24+6 = 30, 30+7 = 37, 37+8 = 45, ... - Max Alekseyev, Feb 06 2008
The Frame-Stewart algorithm indeed gives the optimal solution, i.e., the minimal possible number of moves for the case of four pegs [Bousch, 2014]. - Andrey Zabolotskiy, Sep 18 2017
|
|
|
REFERENCES
|
A. Brousseau, Tower of Hanoi with more pegs, J. Recreational Math., 8 (1975-1976), 169-176.
Paul Cull and E. F. Ecklund, On the Towers of Hanoi and generalized Towers of Hanoi problems. Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982). Congr. Numer. 35 (1982), 229-238. MR0725883(85a:68059).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
D. Wood, Towers of Brahma and Hanoi revisited, J. Recreational Math., 14 (1981), 17-24.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = min{ 2 a(k) + 2^(n-k) - 1; k < n}, which is always odd. - M. F. Hasler, Feb 06 2008
|
|
|
MAPLE
|
|
|
|
MATHEMATICA
|
Join[{0}, Accumulate[2^Flatten[Table[PadRight[{}, n+1, n], {n, 0, 12}]]]] (* Harvey P. Dale, Jul 03 2021 *)
|
|
|
PROG
|
(PARI) print_7664(n, s=0, t=1, c=1, d=1)=while(n-->=0, print1(s+=t, ", "); c--&next; c=d++; t<<=1)
(PARI) A007664(n, c=1, d=1, t=1)=sum(i=c, n, i>c&(t<<=1)&c+=d++; t) \\ M. F. Hasler, Feb 06 2008
(Haskell)
a007664 = sum . map (a000079 . a003056) . enumFromTo 0 . subtract 1
(Python)
from math import isqrt
def A007664(n): return (1<<(r:=(k:=isqrt(m:=n+1<<1))+int(m>=k*(k+1)+1)-1))*(n-1-(r*(r-1)>>1))+1 # Chai Wah Wu, Oct 17 2022
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Upper bound updated with a reference by Max Alekseyev, Nov 23 2008
|
|
|
STATUS
|
approved
|
| |
|
|
