JOURNAL OF THE INDIAN ACADEMY OF MATHEMATICS

(Published by Indian Academy of Mathematics since 1978)

Promoting Research in Pure and Applied Mathematics

ISSN 0970-5120


HomeArchiveContents
← Back to Volume 47, Issue 2 Contents

STUDY OF FRAME STEWART NUMBERS OF THE MULTI-PEG TOWER OF HANOI PROBLEM

Pramod Shinde, Aditi S. Phadke, Samina Boxwala
Department of Mathematics, Nowrosjee Wadia College, Pune
Volume: 47Issue: 2Pages: 464–469Year: 2025ISSN: 0970-5120
⬇ Download Full PDF

Abstract

In this paper we have studied the set of best known solutions (called Frame Stewart Numbers) obtained so far, for the multi-peg Tower of Hanoi problem for $r$ rings, $r \ge 1$ and $p$ pegs, $p \ge 3$. These solutions obtained using the Frame Stewart algorithm are denoted by $T(r,p)$. Some interesting observations of the set $T = \{T(r,p) \mid r \ge 1, p \ge 3\}$ have been made. In this study we have proved that the set of all odd natural numbers and the set $T$ are equal. For a fixed $p$, we define $T_{p} = \{T(r,p) \mid r \ge 1\}$. We have proved that $T_{p} \not\subset T_{p+1}$. A combinatorial identity for a specific value of $r$ depending on $p$ has been proved. Three conjectures about the set $T_{p}$ have been made.
Keywords: Multi-peg Tower of Hanoi Problem, Frame Stewart Algorithm, Frame Stewart Numbers
MSC 2020: 05A10, 05A19

How to Cite

Pramod Shinde, Aditi S. Phadke, Samina Boxwala, STUDY OF FRAME STEWART NUMBERS OF THE MULTI-PEG TOWER OF HANOI PROBLEM, Journal of the Indian Academy of Mathematics, 47(2) (2025), 464–469.

References

  • Lucas, E., Recreations Mathematiques, Vol. III, Gauthier-Villars, Paris.
  • Stewart, B. M., Problem 3918, American Mathematical Monthly, 46 (1939), 363.
  • Houston, Ben, and Hassan Masum, comps., Explorations in 4-Peg Tower of Hanoi, 29 Nov. 2004, Carleton University, School of Computer Science, http://www.scs.carleton.ca/research/techreports/2004/TR-0410.pdf.
  • Hinz, A. M., Pascal's Triangle and the Tower of Hanoi, American Mathematical Monthly, 99 (1992), 538–544.
  • Hinz, A. M., An iterative algorithm for the Tower of Hanoi with four pegs, Computing, 42 (1989), 133–180.
  • Wood, D., The Towers of Brahma and Hanoi Revisited, J. Recreat. Math., 14 (1981), 17–24.
  • Frame, J. S., Solution to AMM Problem 3918, American Mathematical Monthly, 48 (1941), 216–219.
  • Sandi Klavžar and Uroš Milutinović, Simple Explicit Formulas for the Frame-Stewart Numbers, Annals of Combinatorics, 6 (2002), 157–167.
  • Sandi Klavžar, Uroš Milutinović, Ciril Petr, On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem, Discrete Applied Mathematics, 120 (2002), 141–157.
  • Shinde P. N. and Phadke A. S., Explorations of the Multi-peg Tower of Hanoi Problem, Proceedings of the International Conference on Perspectives of Computer Confluence with Sciences 2012, (2012), 122–126.

© Journal of the Indian Academy of Mathematics