

A007664


Reve's puzzle: number of moves needed to solve the Towers of Hanoi puzzle with 4 pegs and n disks, according to the FrameStewart 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 FrameStewart 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 nk disks to the destination peg without touching the k smallest disks (requiring 2^(nk)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.
It is conjectured that the algorithm always gives the optimal solution; for n<=30 this is confirmed by exhaustive search, but no proof is known for the general case.
"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 FrameStewart 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 (1972), 169176.
Cull, Paul; Ecklund, E. F. 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), 229238. 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), 1724.


LINKS

M. F. Hasler and Gheorghe Coserea, Table of n, a(n) for n = 0..10012 (first 1001 terms from M. F. Hasler)
S. Alejandre, Legend of Towers of Hanoi
J.P. Allouche, Note on the cyclic towers of Hanoi, Theoret. Comput. Sci., 123 (1994), 37.
T. Bousch, La quatrième tour de Hanoi, Bull. Belg. Math. Soc. Simon Stevin 21 (2014) 895912.
A. M. Hinz, An iterative algorithm for the Tower of Hanoi with four pegs, Computing, June 1989, Volume 42, Issue 23, pp 133140.
A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi  Myths and Maths, Birkhäuser 2013.
B. Houston and H. Masum, Explorations in 4peg Tower of Hanoi [Paper]
B. Houston and H. Masum, Explorations in 4peg Tower of Hanoi [Web site]
S. Klavzar et al., Hanoi graphs and some classical numbers
S. Klavzar and U. Milutinovic, Simple explicit formulas for the FrameStewart's numbers
S. Klavzar, U. Milutinovic and C. Petr, On the FrameStewart algorithm for the multipeg Tower of Hanoi problem, Discrete Appl. Math. 120, 13 (2002), 141  157.
Mathnet at U. Toronto, Generalizing the Towers of Hanoi Problem
Richard E. Korf and Ariel Felner. Recent Progress in Heuristic Search: a Case Study of the FourPeg Towers of Hanoi Problem. IJCAI 2007: 23242329.
B. M. Stewart, Advanced Problem 3918, Amer. Math. Monthly, 46 (1939), 363.
B. M. Stewart & J. S. Frame, Solution to Problem 3918, Amer. Math. Monthly, 48 (1941), 217219.
P. Stockmeyer, Variations on the FourPost Tower of Hanoi Puzzle, CONGRESSUS NUMERANTIUM 102 (1994), pp. 312. [Has extensive bibliography]
Eric Weisstein's World of Mathematics, Towers of Hanoi
Janez Žerovnik, Self Similarities of the Tower of Hanoi Graphs and a proof of the FrameStewart Conjecture, arXiv:1601.04298 [math.CO], 2016.


FORMULA

a(n) = min{ 2 a(k) + 2^(nk)  1 ; k < n}, which is always odd.  M. F. Hasler, Feb 06 2008
a(n) = sum(2^A003056(i), i=0..n1).  Daniele Parisse (daniele.parisse(AT)m.eads.net), May 09 2003
a(n) = 1 + (n + A003056(n)  1  A003056(n)*(A003056(n) + 1)/2)*2^A003056(n).  Daniele Parisse (daniele.parisse(AT)m.dasa.de), Feb 06 2001
a(n) = 1 + (n  1  A003056(n)*(A003056(n)  1)/2)*2^A003056(n).  Daniele Parisse (daniele.parisse(AT)tonline.de), Jul 07 2007


MAPLE

A007664:=proc(n) option remember; min(seq(2*A007664(k)+2^(nk)1, k=0..n1)) end; A007664(0):=0; # M. F. Hasler, Feb 06 2008
A007664 := n > 1 + (n  1  A003056(n)*(A003056(n)  1)/2)*2^A003056(n); A003056 := n > round(sqrt(2*n+2))1; # M. F. Hasler, Feb 06 2008


MATHEMATICA

a[n_] := a[n] = Min[ Table[ 2*a[k] + 2^(nk)  1, {k, 0, n1}]]; a[0] = 0; Table[a[n], {n, 0, 48}] (* JeanFrançois Alcover, Dec 06 2011, after M. F. Hasler *)


PROG

(PARI) A007664(n) = (n  1  (n=A003056(n))*(n1)/2)*2^n +1
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


CROSSREFS

Cf. A007665, A182058, A003056, A000225 (analog for 3 pegs), A137688 (first differences).
Sequence in context: A061571 A049690 A080075 * A215812 A114395 A075314
Adjacent sequences: A007661 A007662 A007663 * A007665 A007666 A007667


KEYWORD

nonn,nice,changed


AUTHOR

N. J. A. Sloane, Mira Bernstein and Robert G. Wilson v


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



