# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a007664
Showing 1-1 of 1

%I A007664 M2449 #103 Dec 01 2023 05:23:42
%S A007664 0,1,3,5,9,13,17,25,33,41,49,65,81,97,113,129,161,193,225,257,289,321,
%T A007664 385,449,513,577,641,705,769,897,1025,1153,1281,1409,1537,1665,1793,
%U A007664 2049,2305,2561,2817,3073,3329,3585,3841,4097,4609,5121,5633
%N 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.
%C A007664 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.
%C A007664 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.
%C A007664 "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]
%C A007664 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
%C A007664 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
%D A007664 A. Brousseau, Tower of Hanoi with more pegs, J. Recreational Math., 8 (1975-1976), 169-176.
%D A007664 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).
%D A007664 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A007664 D. Wood, Towers of Brahma and Hanoi revisited, J. Recreational Math., 14 (1981), 17-24.
%H A007664 Gheorghe Coserea, <a href="/A007664/b007664.txt">Table of n, a(n) for n = 0..10012</a> (first 1001 terms from M. F. Hasler)
%H A007664 S. Alejandre, <a href="http://web.archive.org/web/20040314132214/http://www.rialto.k12.ca.us/frisbie/mathfair/hanoilegend.html">Legend of Towers of Hanoi</a>.
%H A007664 J.-P. Allouche, <a href="http://dx.doi.org/10.1016/0304-3975(94)90064-7">Note on the cyclic towers of Hanoi</a>, Theoret. Comput. Sci., 123 (1994), 3-7.
%H A007664 T. Bousch, <a href="https://doi.org/10.36045/bbms/1420071861">La quatrième tour de Hanoi</a>, Bull. Belg. Math. Soc. Simon Stevin 21 (2014) 895-912.
%H A007664 A. Brousseau, <a href="/A007664/a007664.pdf">Tower of Hanoi with more pegs</a>, J. Recreational Math 8.3 (1975-6), 169-176. (Annotated scanned copy)
%H A007664 A. M. Hinz, <a href="https://doi.org/10.1007/BF02239743">An iterative algorithm for the Tower of Hanoi with four pegs</a>, Computing, June 1989, Volume 42, Issue 2-3, pp. 133-140.
%H A007664 A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, <a href="http://tohbook.info">The Tower of Hanoi - Myths and Maths</a>, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">Birkhäuser</a> 2013.
%H A007664 B. Houston and H. Masum, <a href="https://pdfs.semanticscholar.org/072a/c5bd021bec39eaaa9a776e26b460e4191e42.pdf">Explorations in 4-peg Tower of Hanoi</a>. [Paper]
%H A007664 B. Houston and H. Masum, <a href="http://www.exocortex.org/toh/">Explorations in 4-peg Tower of Hanoi</a>. [Web site]
%H A007664 S. Klavzar et al., <a href="https://doi.org/10.1016/j.exmath.2005.05.003">Hanoi graphs and some classical numbers</a>.
%H A007664 S. Klavzar and U. Milutinovic, <a href="https://pdfs.semanticscholar.org/ee65/d3ca949092f51485a5d2f7cddba192d9db99.pdf">Simple explicit formulas for the Frame-Stewart's numbers</a>.
%H A007664 S. Klavzar, U. Milutinovic and C. Petr, <a href="https://doi.org/10.1016/S0166-218X(01)00287-6">On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem</a>, Discrete Appl. Math. 120, 1-3 (2002), 141 - 157.
%H A007664 Mathnet at U. Toronto, <a href="http://www.math.toronto.edu/mathnet/questionCorner/genhanoi.html">Generalizing the Towers of Hanoi Problem</a>.
%H A007664 Richard E. Korf and Ariel Felner, <a href="http://www.ijcai.org/papers07/Papers/IJCAI07-374.pdf">Recent Progress in Heuristic Search: a Case Study of the Four-Peg Towers of Hanoi Problem</a>. IJCAI 2007: 2324-2329.
%H A007664 B. M. Stewart, <a href="http://www.jstor.org/stable/2302907">Advanced Problem 3918</a>, Amer. Math. Monthly, 46 (1939), 363.
%H A007664 B. M. Stewart & J. S. Frame, <a href="http://www.jstor.org/stable/2304268">Solution to Problem 3918</a>, Amer. Math. Monthly, 48 (1941), 217-219.
%H A007664 P. Stockmeyer, <a href="http://www.cs.wm.edu/~pkstoc/boca.ps">Variations on the Four-Post Tower of Hanoi Puzzle</a>, Congressus Numerantium 102 (1994), pp. 3-12. [Has extensive bibliography]
%H A007664 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TowersofHanoi.html">Towers of Hanoi</a>.
%H A007664 Janez Žerovnik, <a href="http://arxiv.org/abs/1601.04298">Self Similarities of the Tower of Hanoi Graphs and a proof of the Frame-Stewart Conjecture</a>, arXiv:1601.04298 [math.CO], 2016.
%H A007664 <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F A007664 a(n) = min{ 2 a(k) + 2^(n-k) - 1; k < n}, which is always odd. - _M. F. Hasler_, Feb 06 2008
%F A007664 a(n) = Sum_{i=0..n-1} 2^A003056(i). - _Daniele Parisse_, May 09 2003
%F A007664 a(n) = 1 + (n + A003056(n) - 1 - A003056(n)*(A003056(n) + 1)/2)*2^A003056(n). - _Daniele Parisse_, Feb 06 2001
%F A007664 a(n) = 1 + (n - 1 - A003056(n)*(A003056(n) - 1)/2)*2^A003056(n). - _Daniele Parisse_, Jul 07 2007
%p A007664 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
%p A007664 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
%t A007664 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_ *)
%t A007664 Join[{0},Accumulate[2^Flatten[Table[PadRight[{},n+1,n],{n,0,12}]]]] (* _Harvey P. Dale_, Jul 03 2021 *)
%o A007664 (PARI) A007664(n) = (n - 1 - (n=A003056(n))*(n-1)/2)*2^n +1
%o A007664 A003056(n) = (sqrt(2*n+2)-.5)\1 \\ _M. F. Hasler_, Feb 06 2008
%o A007664 (PARI) print_7664(n,s=0,t=1,c=1,d=1)=while(n-->=0,print1(s+=t,",");c--&next;c=d++;t<<=1)
%o A007664 (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
%o A007664 (Haskell)
%o A007664 a007664 = sum . map (a000079 . a003056) . enumFromTo 0 . subtract 1
%o A007664 -- _Reinhard Zumkeller_, Feb 17 2013
%o A007664 (Python)
%o A007664 from math import isqrt
%o A007664 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
%Y A007664 Cf. A007665, A182058, A003056, A000225 (analog for 3 pegs), A137688 (first differences).
%K A007664 nonn,nice
%O A007664 0,3
%A A007664 _N. J. A. Sloane_, _Mira Bernstein_ and _Robert G. Wilson v_
%E A007664 Edited, corrected and extended by _M. F. Hasler_, Feb 06 2008
%E A007664 Further edits by _N. J. A. Sloane_, Feb 08 2008
%E A007664 Upper bound updated with a reference by _Max Alekseyev_, Nov 23 2008

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE