login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A137695 Tower of Hanoi with p pegs: Number of moves needed for n disks, using Frame's or Stewart's algorithm (formatted as upper right triangle). 1
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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 X(n,p).

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 that this algorithm is optimal. - N. J. A. Sloane, Sep 10 2018

REFERENCES

Klavžar, Sandi, 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]

LINKS

Table of n, a(n) for n=1..71.

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.

FORMULA

X(n,p) = 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) }.

EXAMPLE

The complete matrix would read:

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

(first row: 3 pegs, A000225; 2nd row: 4 pegs, A007664; 3rd row: 5 pegs, A007665).

MATHEMATICA

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

PROG

(PARI) X(n, p)={local(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))}

A137695(n)=X(t=1+sqrtint(2*n-2-sqrtint(2*n-2)), 2+n-t*(t-1)/2)

CROSSREFS

Cf. A000225, A007664, A007665.

Sequence in context: A118362 A258273 A205680 * A318456 A209085 A086799

Adjacent sequences:  A137692 A137693 A137694 * A137696 A137697 A137698

KEYWORD

easy,nice,nonn,tabl

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 16:41 EDT 2018. Contains 316367 sequences. (Running on oeis4.)