Search: id:A007664
Results 1-1 of 1 results found.

%I A007664 M2449
%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 formulae for 
               a(n) as partial sums of A137688.
%C A007664 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.
%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
%D A007664 J.-P. Allouche, Note on the cyclic towers of Hanoi, Theoret. Comput. 
               Sci., 123 (1994), 3-7.
%D A007664 A. Brousseau, Tower of Hanoi with more pegs, J. Recreational Math., 8 
               (1972), 169-176.
%D A007664 J. S. Frame, Solution to Problem 3918, Amer. Math. Monthly, 48 (1941), 
               216-217.
%D A007664 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A007664 B. M. Stewart, Advanced Problem 3918, Amer. Math. Monthly, 46 (1939), 
               363.
%D A007664 B. M. Stewart, Solution to Problem 3918, Amer. Math. Monthly, 48 (1941), 
               217-219.
%D A007664 D. Wood, Towers of Brahma and Hanoi revisited, J. Recreational Math., 
               14 (1981), 17-24.
%H A007664 M. F. Hasler, <a href="b007664.txt">Table of n, a(n) for n=0,...,1000</
               a>.
%H A007664 S. Alejandre, <a href="http://www.rialto.k12.ca.us/frisbie/mathfair/hanoilegend.html">
               Legend of Towers of Hanoi</a>
%H A007664 A. M. Hinz, <a href="http://www.springerlink.com/content/72x2t287k5132744/
               ">An iterative algorithm for the Tower of Hanoi with four pegs</a>
%H A007664 B. Houston and H. Masum, <a href="http://www.scs.carleton.ca/research/
               tech_reports/2004/TR-04-10.pdf">Explorations in 4-peg Tower of Hanoi</
               a> [Ppaper]
%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="http://citeseer.ist.psu.edu/732083.html">
               Hanoi graphs and some classical numbers</a>
%H A007664 S. Klavzar and U. Milutinovic, <a href="http://citeseer.ist.psu.edu/440698.html">
               Simple explicit formulas for the Frame-Stewart's numbers</a>
%H A007664 S. Klavzar, U. Milutinovic and C. Petr, <a href="http://citeseer.ist.psu.edu/
               442900.html">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 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 Wikipedia, <a href="http://en.wikipedia.org/wiki/Reve%27s_puzzle#Four_pegs_and_beyond">
               Four pegs and beyond</a> [Has further references]
%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(2^A003056(i), i=0..n-1) - Daniele Parisse (daniele.parisse(AT)m.eads.net), 
               May 09 2003
%F A007664 A007664(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
%F A007664 a(n) = 1 + (n - 1 - A003056(n)*(A003056(n) - 1)/2)*2^A003056(n) - Daniele 
               Parisse (daniele.parisse(AT)t-online.de), 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
%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
%Y A007664 Cf. A007665, A003056, A000225 (analogue for 3 pegs), A137688 (first differences).
%Y A007664 Sequence in context: A061571 A049690 A080075 this_sequence A114395 A075314 
               A152737
%Y A007664 Adjacent sequences: A007661 A007662 A007663 this_sequence A007665 A007666 
               A007667
%K A007664 nonn,nice
%O A007664 0,3
%A A007664 N. J. A. Sloane (njas(AT)research.att.com), Mira Bernstein and Robert 
               G. Wilson v (rgwv(AT)rgwv.com)
%E A007664 Edited, corrected and extended by M. F. Hasler (Maximilian.Hasler(AT)gmail.com), 
               Feb 06 2008
%E A007664 Further edits by N. J. A. Sloane (njas(AT)research.att.com), Feb 08 2008
%E A007664 Upper bound updated with a reference by Max Alekseyev (maxale(AT)gmail.com), 
               Nov 23 2008

Search completed in 0.002 seconds