On The Optimal General Solution To The Multi-Peg Tower of Hanoi

2025/05/19 by Menon, Abhiram
Engineering · #05A20 (Primary) 68Q25 #68R05 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #G.2 #I.5 #Soil, Finite Element Methods #Structural Analysis and Optimization #Vibration and Dynamic Analysis

paper · pdf · doi:10.48550/arxiv.2505.12941

openalex publication_date 2025/05/19 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/30

Abstract

We derive a unified closed-form expression for the Frame-Stewart algorithm in the multi-peg Tower of Hanoi: M(p,n) = 2^(i(p,n)+1)*n - sum_k=0^i(p,n) 2^k * C(p+k-2, k), where i(p,n) = min j >= 0 : n <= C(p-1+j, j+1) . and prove it satisfies the Frame-Stewart recurrence for all (p,n) via double induction using discrete slope analysis with simplex boundaries. It shows that M(p,n) grows linearly within each regime, with slopes doubling at successive boundaries. We also prove Frame-Stewart optimality for the first two regimes indexed by i: for p-1 < n <= C(p,2), M(p,n) = 4n - 2p + 1; for C(p,2) < n <= C(p+1,3), M(p,n) = 8n - 2p² + 1. These results give optimality proofs for infinitely many (p,n) pairs beyond trivial cases, settling the conjecture up to n <= C(p+1,3).

Related

• On the Footsteps to Generalized Tower of Hanoi Strategy
• Solutions to the generalized Towers of Hanoi problem
• The Tower of Hanoi: Optimality Proofs, Multi-Peg Bounds, and Computational Frontiers
• What is the least number of moves needed to solve the k-peg Towers of Hanoi problem?
• On the Frame-Stewart Conjecture