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
Gheorghe Coserea, Table of n, a(n) for n = 0..10012 (first 1001 terms from M. F. Hasler)
Suzanne Alejandre, The Legend of the Towers of Hanoi.
Jean-Paul Allouche, Note on the cyclic towers of Hanoi, Theoret. Comput. Sci., 123 (1994), 3-7.
Thierry Bousch, La quatrième tour de Hanoï, Bull. Belg. Math. Soc. Simon Stevin 21 (2014) 895-912.
Alfred Brousseau, Tower of Hanoi with more pegs, J. Recreational Math 8.3 (1975-6), 169-176. (Annotated scanned copy)
Andreas M. Hinz, An iterative algorithm for the Tower of Hanoi with four pegs, Computing (June 1989) Vol. 42, Issue 2-3, 133-140.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser (2013). See also the book website.
Ben Houston and Hassan Masum, Explorations in 4-peg Tower of Hanoi. [Paper]
Ben Houston and Hassan Masum, Explorations in 4-peg Tower of Hanoi. [Website]
Qi Junyi, The Tower of Hanoi: Optimality Proofs, Multi-Peg Bounds, and Computational Frontiers, arXiv:2511.07501 [math.CO], 2025. See pp. 5, 7.
Sandi Klavžar, Uroš Milutinović, and Ciril Petr, Hanoi graphs and some classical numbers.
Sandi Klavžar and Uroš Milutinović, Simple explicit formulas for the Frame-Stewart numbers, Ann. Comb. (2002) Vol. 6, 157-167. Alternative Link.
Sandi Klavžar, Uroš Milutinović, and Ciril Petr, On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem, Discrete Appl. Math. 120, 1-3 (2002), 141-157.
Richard E. Korf and Ariel Felner, Recent Progress in Heuristic Search: a Case Study of the Four-Peg Towers of Hanoi Problem, IJCAI 2007: 2324-2329.
Mathnet at U. Toronto, Generalizing the Towers of Hanoi Problem.
B. M. Stewart, Advanced Problem 3918, Amer. Math. Monthly, 46 (1939), 363.
B. M. Stewart and J. S. Frame, Solution to Problem 3918, Amer. Math. Monthly, 48 (1941), 217-219.
P. Stockmeyer, Variations on the Four-Post Tower of Hanoi Puzzle, Congressus Numerantium 102 (1994), pp. 3-12. [Has extensive bibliography]
Eric Weisstein's World of Mathematics, Tower of Hanoi.
Janez Žerovnik, Self Similarities of the Tower of Hanoi Graphs and a proof of the Frame-Stewart Conjecture, arXiv:1601.04298 [math.CO], 2016.
FORMULA
a(n) = min{ 2 a(k) + 2^(n-k) - 1; k < n}, which is always odd. - M. F. Hasler, Feb 06 2008
a(n) = Sum_{i=0..n-1} 2^A003056(i). - Daniele Parisse, May 09 2003
a(n) = 1 + (n + A003056(n) - 1 - A003056(n)*(A003056(n) + 1)/2)*2^A003056(n). - Daniele Parisse, Feb 06 2001
MAPLE
A007664:=proc(n) option remember; min(seq(2*A007664(k)+2^(n-k)-1, k=0..n-1)) end; A007664(0):=0; # M. F. Hasler, Feb 06 2008
# Alternative:
MATHEMATICA
a[n_] := a[n] = Min[ Table[ 2*a[k] + 2^(n-k) - 1, {k, 0, n-1}]]; a[0] = 0; Table[a[n], {n, 0, 48}] (* Jean-François Alcover, Dec 06 2011, after M. F. Hasler *)
Join[{0}, Accumulate[2^Flatten[Table[PadRight[{}, n+1, n], {n, 0, 12}]]]] (* Harvey P. Dale, Jul 03 2021 *)
PROG
A003056(n) = (sqrt(2*n+2)-.5)\1 \\ M. F. Hasler, Feb 06 2008
(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
-- Reinhard Zumkeller, Feb 17 2013
(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
Edited, corrected and extended by M. F. Hasler, Feb 06 2008
Further edits by N. J. A. Sloane, Feb 08 2008
Upper bound updated with a reference by Max Alekseyev, Nov 23 2008
STATUS
approved