← 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