A007665 -id:A007665 - cp's OEIS frontend

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.

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

Offset: 0

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

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

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.

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), 3-7.
T. Bousch, La quatrième tour de Hanoi, Bull. Belg. Math. Soc. Simon Stevin 21 (2014) 895-912.
A. Brousseau, Tower of Hanoi with more pegs, J. Recreational Math 8.3 (1975-6), 169-176. (Annotated scanned copy)
A. M. Hinz, An iterative algorithm for the Tower of Hanoi with four pegs, Computing, June 1989, Volume 42, Issue 2-3, pp. 133-140.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013.
B. Houston and H. Masum, Explorations in 4-peg Tower of Hanoi. [Paper]
B. Houston and H. Masum, Explorations in 4-peg 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 Frame-Stewart's numbers.
S. Klavzar, U. Milutinovic and C. Petr, On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem, Discrete Appl. Math. 120, 1-3 (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 Four-Peg Towers of Hanoi Problem. IJCAI 2007: 2324-2329.
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), 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, Towers 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.
Index entries for sequences related to Towers of Hanoi

Cf. A007665, A182058, A003056, A000225 (analog for 3 pegs), A137688 (first differences).

a007664 = sum . map (a000079 . a003056) . enumFromTo 0 . subtract 1
-- Reinhard Zumkeller, Feb 17 2013

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
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

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 *)

A007664(n) = (n - 1 - (n=A003056(n))*(n-1)/2)*2^n +1
A003056(n) = (sqrt(2*n+2)-.5)\1 \\ M. F. Hasler, Feb 06 2008

print_7664(n,s=0,t=1,c=1,d=1)=while(n-->=0,print1(s+=t,",");c--&next;c=d++;t<<=1)

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

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

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
a(n) = 1 + (n - 1 - A003056(n)*(A003056(n) - 1)/2)*2^A003056(n). - Daniele Parisse, Jul 07 2007

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

A005665 Minimal number of moves for the cyclic variant of the Towers of Hanoi for 3 pegs and n disks, with the final peg one step away.

Original entry on oeis.org

0, 1, 5, 15, 43, 119, 327, 895, 2447, 6687, 18271, 49919, 136383, 372607, 1017983, 2781183, 7598335, 20759039, 56714751, 154947583, 423324671, 1156544511, 3159738367, 8632565759, 23584608255, 64434348031, 176037912575, 480944521215, 1313964867583, 3589818777599, 9807567290367

Offset: 0

N. J. A. Sloane

Original name was: Tower of Hanoi with 3 pegs and cyclic moves only (clockwise). - Jianing Song, Nov 01 2024

This looks like sequence A(0,1;2,2;3) of the family of sequences [a,b:c,d:k] considered by Gary Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 18.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
S. Alejandre, Legend of Towers of Hanoi
J.-P. Allouche, Note on the cyclic towers of Hanoi, Theoret. Comput. Sci., 123 (1994), 3-7.
M. D. Atkinson, The Cyclic Towers of Hanoi, Info. Proc. Letters, 13 (1981), 118-119.
R. K. Guy, Letter to N. J. A. Sloane, 1976
A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 249. Book's website
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
D. G. Poole, The towers and triangles of Professor Claus (or, Pascal knows Hanoi), Math. Mag., 67 (1994), 323-344.
Index entries for linear recurrences with constant coefficients, signature (3,0,-2).
Index entries for sequences related to Towers of Hanoi

Cf. A005666, A007664, A007665, A026150 (first differences).

Cf. A338024, A292764, A338089 (4 pegs).

a005665 n = a005665_list !! (n-1)
a005665_list = 0 : 1 : 5 : zipWith (-)
               (map (* 3) $ drop 2 a005665_list) (map (* 2) a005665_list)
-- Reinhard Zumkeller, May 01 2013

[Floor(((Sqrt(3)+1)^(n+1)+(Sqrt(3)-1)^(n+1)*(-1)^n)*Sqrt(3)/6-1): n in [0..30] ]; // Vincenzo Librandi, Aug 19 2011

a[n_] := Simplify[ ((1 + Sqrt[3])^(n+1) - (1 - Sqrt[3])^(n+1))*Sqrt[3]/6 - 1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 14 2011, after Paul Barry *)
LinearRecurrence[{3,0,-2},{0,1,5},40] (* Harvey P. Dale, Mar 30 2015 *)

a(n)=([0,1,0; 0,0,1; -2,0,3]^n*[0;1;5])[1,1] \\ Charles R Greathouse IV, Jun 15 2015

G.f.: x*(1+2*x)/((1-x)*(1-2*x-2*x^2)). - Simon Plouffe in his 1992 dissertation
From Paul Barry, Sep 05 2006: (Start)
a(n) = ((sqrt(3)+1)^(n+1) + (sqrt(3)-1)^(n+1)*(-1)^n)*sqrt(3)/6 - 1. (End)
a(n) = 2*a(n-1) + 2*a(n-2) + 3. - John W. Layman
a(n) = (1/(2*s3))*((1+s3)^(n+1) - (1-s3)^(n+1)) - 1 where s3 = sqrt(3).
a(n) = 3*a(n-1) - 2*a(n-3), a(0)=0, a(1)=1, a(2)=5 (from the given o.g.f.). Observed by Gary Detlefs. See the W. Lang link. - Wolfdieter Lang, Oct 18 2010
a(n) = 2*A005666(n-1) + 1. - Michel Marcus, Nov 02 2012
a(n) = Sum_{k=1..n} A026150(k). - Ivan N. Ianakiev, Nov 22 2019
E.g.f.: (1/3)*exp(x)*(-3 + 3*cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x)). - Stefano Spezia, Nov 22 2019

More terms from Vincenzo Librandi, Aug 19 2011
Name clarified by Paul Zimmermann, Feb 21 2018
New name based on the name of A338024, A292764, and A338089 by Jianing Song, Nov 01 2024

A182058 Number of moves needed to solve the Towers of Hanoi puzzle with 6 pegs and n disks.

Original entry on oeis.org

1, 3, 5, 7, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 57, 65, 73, 81, 89

Offset: 1

N. J. A. Sloane, Apr 08 2012

See A007664 for further references etc.

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).

Index entries for sequences related to Towers of Hanoi

Cf. A007664 (4 pegs), A007665 (5 pegs).

A137695 Tower of Hanoi with p pegs: A(p,n) = number of moves needed for n disks, using Frame's or Stewart's algorithm, read by columns of the upper right triangle of rows p >= 3, columns n >= p-2.

Original entry on oeis.org

1, 3, 3, 7, 5, 5, 15, 9, 7, 7, 31, 13, 11, 9, 9, 63, 17, 15, 13, 11, 11, 127, 25, 19, 17, 15, 13, 13, 255, 33, 23, 21, 19, 17, 15, 15, 511, 41, 27, 25, 23, 21, 19, 17, 17, 1023, 49, 31, 29, 27, 25, 23, 21, 19, 19, 2047, 65, 39, 33, 31, 29, 27, 25, 23, 21, 21, 4095, 81, 47, 37, 35

Offset: 1

M. F. Hasler, Feb 09 2008, revised Feb 10 2008

In the cited paper by Klavzar et al. it is proved that Frame's algorithm and Stewart's algorithm, as well as several variations, all yield the same number of moves needed for the n disk, p peg problem, given by the formula for A(p,n).
This sequence lists the elements of the upper right triangle of the matrix having as rows the number of moves required, depending on the number of disks, for a given number of pegs. (The first row refers to 3 pegs, etc.) The lower left triangle of the matrix is uninteresting, since all elements below a given diagonal element are equal to that element, namely 2n-1. (For p>n, each disk can be moved to a separate peg.)
However, the article by Klavžar and Milutinović, "Simple explicit formulas for the Frame-Stewart numbers", points out that there is (at least as of 2002) no proof that this algorithm is optimal. - N. J. A. Sloane, Sep 10 2018

			The complete matrix would read (starting with row p = 3, column n = 1):
  1_  3   7  15  31   63  127  255  511 1023 ...
  1 \_3_  5   9  13   17   25   33   41   49 ...
  1   3 \_5_  7  11   15   19   23   27   31 ...
  1   3   5 \_7_  9   13   17   21   25   29 ...
  1   3   5   7 \_9_  11   15   19   23   27 ...
  1   3   5   7   9 \_11_  13   17   21   25 ...
  1   3   5   7   9   11 \_13_  15   19   23 ...
  1   3   5   7   9   11   13 \_15_  17   21 ...
  1   3   5   7   9   11   13   15 \_17_  19 ...                     _
(Since the columns become constant below the diagonal (symbolized by  \_), we list only the part above it.)
First row: 3 pegs, equals A000225; 2nd row: 4 pegs, cf. A007664; 3rd row: 5 pegs, cf. A007665.

Sandi Klavžar and Uroš Milutinović. "Simple explicit formulas for the Frame-Stewart numbers." Annals of Combinatorics 6.2 (2002): 157-167; 0218-0006/02/020157-11. [This is an 11-page article. There is a free article on the web with the same authors and title, but which is only two pages long. - N. J. A. Sloane, Sep 10 2018]

M. F. Hasler, Table of n, a(n) for n = 1..1000, Apr 08 2025
S. Klavzar et al., On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem, Discrete Applied Mathematics 120 (2002) 141-15 and references therein.

Cf. A000225, A007664, A007665.

s[n_, p_] := (k = 0; While[ n > Binomial[p - 3 + k++, p - 2] ] ; k - 2); x[n_, p_] := (snp = s[n, p]; Sum[2^t*Binomial[p - 3 + t, p - 3], {t, 0, snp - 1}] + 2^snp*(n - Binomial[p - 3 + snp, p - 2])); Flatten[Table[x[n, p], {n, 1, 12}, {p, 3, n + 2}] ] (* Jean-François Alcover, Jun 01 2011 *)

A137695(p, n=0/* if n=0, give p-th term of the "flat" sequence */)={n || p = 2+p+(1-n=1+sqrtint(2*p-2-sqrtint(2*p-2)))*n\2; if(p>n+1, 2*n-1, p==3, 2^n-1, my(s=1, t=0); while( n>binomial(p-2+t++,p-2), s+=2^t*binomial(p-3+t, p-3)); s+2^t*(n-binomial(p-3+t,p-2)))} \\ Edited by M. F. Hasler, Apr 08 2025

A(p,n) = Sum_{t=0..s-1} 2^t*binomial(p-3+t, p-3) + 2^s*(n-binomial(p-3+s, p-2)) where s = max { k in Z | n > binomial(p-3+k,p-2) }.

A(p,n) = 2n-1 if n > p+1, else 2^n-1 if p = 3, else see above. - M. F. Hasler, Apr 08 2025

A122124 Numbers n such that 25 divides Sum[ Prime[k]^n, {k,1,n}].

Original entry on oeis.org

3, 5, 7, 11, 15, 19, 23, 25, 27, 31, 35, 39, 43, 45, 47, 51, 55, 59, 63, 65, 67, 71, 75, 79, 83, 85, 87, 91, 95, 99, 103, 105, 107, 111, 115, 119, 123, 125, 127, 131, 135, 139, 143, 145, 147, 151, 155, 159, 163, 165, 167, 171, 175, 179, 183, 185, 187, 191, 195, 199

Offset: 1

Alexander Adamchuk, Aug 21 2006, Sep 18 2006, Sep 21 2006

nonn

a(n) up to a(7) = 23 coincides with A007665[n+1] = Tower of Hanoi with 5 pegs. It appears that a(n) includes all A007665[n] = {1, 3, 5, 7, 11, 15, 19, 23, 27, 31, 39, 47, 55, 63, 71, 79, 87, 95, 103, 111, 127, 143, 159, 175, 191, 207, 223, 239, 255, 271, 287, 303, 319, 335, 351, 383, 415, 447, 479, 511, 543, 575, 607, 639, 671, 703, 735, 767, 799, ...} except A007665[1] = 1.

Primes in this sequence include 5 and all primes of the form 4k+3, A002145[n]. Terms include all numbers of the form 10k+5 (with nonnegative k), A017329[n].

			There are 25 primes p < 100, p(n) = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}.
a(1) = because 25 divides Sum[p(n)^3,{n,1,25}] = 2^3 + 3^3 + ... + 89^3 + 97^3 = A098999[25] and does not divide Sum[p(n)^1,{n,1,25}] = A007504[25] and Sum[p(n)^2,{n,1,25}] = A024450[25].
The next a(2) = 5 because 25 divides Sum[p(n)^5,{n,1,25}] = A122103[25] and does not divide Sum[p(n)^4,{n,1,25}] = A122102[25].

Cf. A007504, A024450, A098999, A122102, A122103, A007665.

Cf. A002144, A002145, A017329.

Select[Range[300],IntegerQ[Sum[ Prime[k]^#1, {k,1,25}]/25]&]

for(n=1,100,if(sum(k=1,25,prime(k)^n)%25==0,print1(n,",")));
print;print("Alternative method not using primes:");
for(n=1,100,m=(n-1)%6;print1((n-m)*3+(n-m+if(m>1,(m-1)*12-1,m*6-1))/3,",")) \\ K. Spage, Oct 23 2009

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A005665 Minimal number of moves for the cyclic variant of the Towers of Hanoi for 3 pegs and n disks, with the final peg one step away.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Formula

Extensions

A182058 Number of moves needed to solve the Towers of Hanoi puzzle with 6 pegs and n disks.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A137695 Tower of Hanoi with p pegs: A(p,n) = number of moves needed for n disks, using Frame's or Stewart's algorithm, read by columns of the upper right triangle of rows p >= 3, columns n >= p-2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A122124 Numbers n such that 25 divides Sum[ Prime[k]^n, {k,1,n}].

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI