The Weighted Tower of Hanoi: Algebraic Structure, Phase Transitions, and Integer Sequences

Andreas M. Hinz; El-Mehdi Mehiri

arxiv: 2605.16956 · v3 · pith:MY4V5WNAnew · submitted 2026-05-16 · 🧮 math.CO · cs.DM

The Weighted Tower of Hanoi: Algebraic Structure, Phase Transitions, and Integer Sequences

Andreas M. Hinz , El-Mehdi Mehiri This is my paper

Pith reviewed 2026-05-22 09:54 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords Tower of Hanoiweighted graphsinteger sequencesrecurrence relationsphase transitionsJacobsthal sequencesLichtenberg sequencesoptimal paths

0 comments

The pith

The weighted Tower of Hanoi with arbitrary nonnegative move costs admits explicit closed-form minimal-cost solutions via two competing strategies.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a unified algebraic treatment of the Tower of Hanoi when each move between pegs carries a weight that depends on both the disc being moved and the source-target peg pair. It begins from a general optimality recurrence and shows that the minimal total cost is always realized by one of two patterns: moving the largest disc once or moving it twice. These patterns yield matrix recurrences whose solutions give closed forms for broad families of weights, including polynomial, geometric, and sequence-based costs. The one-largest-disc-move regime produces a linear operator whose spectrum links directly to the Jacobsthal and Lichtenberg sequences, while the two-move regime grows purely exponentially. This framework also uncovers phase transitions in models with forbidden moves, where the optimal pattern switches from two largest-disc moves for small discs to one largest-disc move beyond a threshold.

Core claim

For arbitrary nonnegative symmetric move costs, the minimal transfer cost of the weighted Tower of Hanoi satisfies a recurrence governed by exactly two competing strategies—one largest-disc move versus two largest-disc moves—each of which admits a complete matrix formulation and explicit closed-form solution; the spectral decomposition of the one-LDM operator produces a direct connection with the Jacobsthal and Lichtenberg sequences, and classical integer sequences chosen as disc weights generate new derived sequences with explicit formulas.

What carries the argument

The general optimality recurrence comparing one-largest-disc-move (one-LDM) and two-largest-disc-move (two-LDM) strategies, which is turned into matrix recurrences whose eigenvalues and eigenvectors yield the closed forms and sequence connections.

If this is right

Exact closed forms exist for peg-symmetric, disc-symmetric, polynomial, geometric, arithmetic, and sequence-induced cost models.
Choosing Fibonacci, Lucas, Pell, or Euler numbers as disc weights produces new integer sequences with explicit recurrences.
Models with forbidden moves exhibit a sharp phase transition: optimal strategy switches from two-LDM to one-LDM at a finite disc-size threshold.
The algebraic structure supplies a sequence-generating transform that maps classical sequences into new derived sequences.
The framework extends to move-type-dependent weights while preserving the matrix-solution method.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same recurrence-plus-matrix approach may apply to other recursive transfer problems whose state graphs admit similar largest-item moves.
Numerical verification for small numbers of discs could confirm whether the closed forms match brute-force shortest paths for non-sequence weights.
The phase-transition threshold might be computed explicitly as a function of the forbidden-move parameters.
The connection to Jacobsthal and Lichtenberg sequences suggests that weighted Hanoi could serve as a combinatorial interpretation for those sequences.

Load-bearing premise

That the minimal-cost solution is always captured exactly by one of the two largest-disc-move patterns and that no other sequence of moves can produce a lower total cost for any choice of nonnegative symmetric weights.

What would settle it

A concrete set of nonnegative symmetric move costs for which the shortest path in the configuration graph requires a sequence of largest-disc moves that cannot be reduced to the one-LDM or two-LDM recurrence.

read the original abstract

We develop a unified algebraic theory of the weighted Tower of Hanoi with arbitrary nonnegative symmetric move costs depending on both disc index and pegs. Starting from a general optimality recurrence with two competing strategies -- one largest-disc move (one-LDM) and two largest-disc moves (two-LDM) -- we derive complete matrix formulations for both regimes and obtain explicit closed forms for the minimal transfer cost. The one-LDM dynamics is governed by a nontrivial linear operator whose spectral decomposition reveals a fundamental connection with the Jacobsthal and Lichtenberg sequences, while the two-LDM dynamics exhibits pure exponential growth. This framework yields exact solutions for broad classes of weight models, including peg-symmetric, disc-symmetric, polynomial, geometric, arithmetic, and sequence-induced costs. In particular, choosing classical integer sequences (Fibonacci, Lucas, Jacobsthal, Pell, Euler, etc.) as disc weights produces new derived sequences with explicit formulas and recurrences, establishing the Tower of Hanoi as a sequence-generating transform. We further introduce and analyze models with forbidden moves and move-type-dependent weights, uncovering a phase transition phenomenon in which the optimal strategy switches from two-LDM behavior for small discs to one-LDM behavior beyond a finite threshold. Our results provide a comprehensive algebraic and combinatorial understanding of weighted Hanoi dynamics and expose deep connections between optimal solutions and classical integer sequences.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper sets up matrix models for weighted Hanoi costs under a two-strategy recurrence and links them to known sequences, but the claim that these strategies always give the true minimum for arbitrary weights is not yet shown to hold.

read the letter

The central contribution is a matrix formulation for the weighted Tower of Hanoi under nonnegative symmetric costs. Starting from a recurrence that pits a single largest-disc move against two such moves, the authors derive closed forms for the minimal cost in several weight families and connect the spectral properties of the one-LDM operator to the Jacobsthal and Lichtenberg sequences. They also treat forbidden-move variants and note a phase transition in optimal behavior as disc size grows. For specific choices such as geometric or sequence-based weights, the framework produces explicit formulas and new derived sequences, which is a clean way to turn the puzzle into a sequence generator. That part is useful and reproducible once the recurrences are accepted. The phase-transition observation for forbidden moves adds a concrete dynamical feature that goes beyond the usual unweighted analysis. The derivations appear internally consistent within the linear-algebra setting they adopt. The main soft spot is the foundational assumption that, for any nonnegative symmetric cost function, the optimum is always captured by exactly one or two moves of the largest disc and that no other pattern yields a strictly lower total. The abstract and strongest claim give no inductive argument or exhaustive small-n check showing that three or more largest-disc moves, or interleaved sequences outside these regimes, cannot win. If a counter-example weight set exists, the closed forms and sequence links would apply only conditionally rather than generally. That gap is not fatal but it is load-bearing; the rest of the algebra stands or falls with it. A reader working in combinatorial optimization or recreational mathematics with an interest in recurrence relations and integer sequences would get the most out of the paper. It is formally grounded enough and raises enough verifiable questions to merit referee time rather than a desk rejection. I would send it out for review so the optimality claim can be tested against the full derivations and any small-case computations the authors may have.

Referee Report

2 major / 2 minor

Summary. The paper develops a unified algebraic theory for the weighted Tower of Hanoi with arbitrary nonnegative symmetric move costs on discs and pegs. It starts from a general optimality recurrence that assumes the minimal-cost solution is always realized by one of two competing strategies (one largest-disc move or two largest-disc moves), derives complete matrix formulations for each regime, and obtains explicit closed forms for the transfer cost. The one-LDM case is governed by a linear operator whose spectral decomposition is claimed to connect directly to the Jacobsthal and Lichtenberg sequences; the two-LDM case yields pure exponential growth. The framework is applied to peg-symmetric, disc-symmetric, polynomial, geometric, and sequence-induced weight models, and extended to forbidden-move variants that exhibit a phase transition between the two regimes.

Significance. If the two-strategy assumption is rigorously justified, the work would supply a coherent algebraic and spectral treatment of a broad family of weighted Hanoi problems, together with a sequence-generating transform that produces new integer sequences from classical ones (Fibonacci, Pell, etc.). The explicit closed forms, matrix spectral analysis, and phase-transition observation constitute genuine contributions that could be cited in combinatorial optimization and recurrence-sequence literature.

major comments (2)

[§2] §2 (General Optimality Recurrence): The manuscript posits that, for arbitrary nonnegative symmetric weights, the optimal solution is always captured exactly by the one-LDM or two-LDM recurrence. No inductive argument, exhaustive case analysis, or verification that patterns with three or more largest-disc moves cannot be cheaper is supplied. Because every subsequent matrix model, closed form, and sequence connection rests on this recurrence being minimal, the claim is load-bearing for the entire paper.
[§3.2] §3.2 (Spectral Decomposition of the One-LDM Operator): The asserted fundamental connection between the eigenvalues of the one-LDM matrix and the Jacobsthal/Lichtenberg sequences is derived directly from the recurrence in §2. If that recurrence does not exhaust all optimal paths for some weight functions, the spectral identification and the resulting closed forms become conditional rather than unconditional.

minor comments (2)

[Abstract] The abstract states that 'explicit closed forms' are obtained but does not display the leading terms or the precise conditions on the weight vector under which they hold.
[§2.1] Notation for the move-cost tensor W(i, p, q) is introduced without a small illustrative table showing how the one-LDM and two-LDM costs are assembled from it.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and insightful comments, which help clarify the foundational assumptions of our work. We respond to each major comment below and describe the revisions we will undertake.

read point-by-point responses

Referee: [§2] §2 (General Optimality Recurrence): The manuscript posits that, for arbitrary nonnegative symmetric weights, the optimal solution is always captured exactly by the one-LDM or two-LDM recurrence. No inductive argument, exhaustive case analysis, or verification that patterns with three or more largest-disc moves cannot be cheaper is supplied. Because every subsequent matrix model, closed form, and sequence connection rests on this recurrence being minimal, the claim is load-bearing for the entire paper.

Authors: We agree that a rigorous justification for the restriction to one-LDM and two-LDM strategies is necessary to support all subsequent results. The recurrence is motivated by the three-peg structure, in which the largest disc must cross between pegs a limited number of times; however, the current manuscript does not supply an inductive argument or exhaustive verification that three or more largest-disc moves cannot yield a lower cost for arbitrary nonnegative symmetric weights. In the revised manuscript we will add a dedicated subsection to §2 that provides a case analysis for small numbers of discs together with a general argument, based on nonnegativity and symmetry, showing that any candidate solution containing three or more moves of the largest disc can be replaced by an equivalent or cheaper solution using at most two such moves. This addition will make the optimality claim explicit and self-contained. revision: yes
Referee: [§3.2] §3.2 (Spectral Decomposition of the One-LDM Operator): The asserted fundamental connection between the eigenvalues of the one-LDM matrix and the Jacobsthal/Lichtenberg sequences is derived directly from the recurrence in §2. If that recurrence does not exhaust all optimal paths for some weight functions, the spectral identification and the resulting closed forms become conditional rather than unconditional.

Authors: The spectral decomposition and the resulting identification with the Jacobsthal and Lichtenberg sequences are indeed conditional on the one-LDM recurrence being optimal. Once the justification requested in the first comment is incorporated into §2, the connection in §3.2 will hold unconditionally for the families of weights considered in the paper. We will revise the opening paragraph of §3.2 to state this dependence explicitly and to cross-reference the new justification subsection. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations are algebraic consequences of the posited recurrence model.

full rationale

The paper explicitly starts from a stated general optimality recurrence that incorporates the two competing strategies (one-LDM and two-LDM) as its modeling premise, then applies standard linear-algebra techniques (matrix formulations and spectral decomposition) to extract closed forms and sequence connections. These steps are direct mathematical consequences of the initial recurrence and do not reduce any claimed prediction or minimal-cost expression back to a fitted parameter or self-referential definition. The links to Jacobsthal/Lichtenberg sequences emerge from the eigenvalues of the derived operator rather than by renaming or smuggling an ansatz. No load-bearing self-citations, uniqueness theorems imported from prior author work, or renamings of known results are required for the central claims. The framework is therefore self-contained as an analysis of the model as defined; any question about whether the two-strategy recurrence truly captures all optima is a matter of model validity rather than circularity in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the domain assumption that optimal solutions are captured by exactly two competing largest-disc-move strategies within a general recurrence for nonnegative symmetric costs; no free parameters or invented entities are mentioned.

axioms (1)

domain assumption Optimal transfer cost is always achieved by either one largest-disc move or two largest-disc moves in the recurrence.
Explicitly stated as the starting point for deriving matrix formulations in both regimes.

pith-pipeline@v0.9.0 · 5773 in / 1434 out tokens · 45019 ms · 2026-05-22T09:54:47.779147+00:00 · methodology

Review history (3 revisions) →

discussion (0)

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

[1]

Aumann, S., G¨ otz, K. A. M., Hinz, A. M., & Petr, C. (2014). The number of moves of the largest disc in shortest paths on Hanoi graphs.The Electronic Journal of Combinatorics, 21(4), Article P4.38.https://doi.org/10.37236/4252

work page doi:10.37236/4252 2014
[2]

Fried, S. (2025). Solving the Tower of Hanoi puzzle with heavy disks.The American Mathe- matical Monthly, 132(8), 806.https://doi.org/10.1080/00029890.2025.2491975

work page doi:10.1080/00029890.2025.2491975 2025
[3]

Hinz, A. M. (1992). Shortest paths between regular states of the Tower of Hanoi.Information Sciences, 63(1–2), 173–181.https://doi.org/10.1016/0020-0255(92)90067-I 18

work page doi:10.1016/0020-0255(92)90067-i 1992
[4]

Hinz, A. M. (2017). The Lichtenberg sequence.The Fibonacci Quarterly, 55(1), 2–12.https: //doi.org/10.1080/00150517.2017.12427786

work page doi:10.1080/00150517.2017.12427786 2017
[5]

M., Klavˇ zar, S., & Petr, C

Hinz, A. M., Klavˇ zar, S., & Petr, C. (2018).The Tower of Hanoi: Myths and Maths(2nd ed.). Birkh¨ auser.https://doi.org/10.1007/978-3-319-73779-9

work page doi:10.1007/978-3-319-73779-9 2018
[6]

M., & Parisse, D

Hinz, A. M., & Parisse, D. (2025). The Tower of Hanoi with heavy discs and some integer sequences.The Fibonacci Quarterly, 63(4), 711–716.https://doi.org/10.1080/00150517. 2025.2481593

work page doi:10.1080/00150517 2025
[7]

(1883).R´ ecr´ eations math´ ematiques(Vol

Lucas, ´E. (1883).R´ ecr´ eations math´ ematiques(Vol. III). Gauthier-Villars et fils

work page
[8]

Mehiri, E.-M., & Belbachir, H. (2024). The weighted Tower of Hanoi.Discrete Mathe- matics, Algorithms and Applications, 16(05), Article 2350051.https://doi.org/10.1142/ S1793830923500519

work page 2024
[9]

(2026).The On-Line Encyclopedia of Integer Sequences.https:// oeis.org

OEIS Foundation Inc. (2026).The On-Line Encyclopedia of Integer Sequences.https:// oeis.org

work page 2026
[10]

Romik, D. (2006). Shortest paths in the Tower of Hanoi graph and finite automata.SIAM Journal on Discrete Mathematics, 20(3), 610–622.https://doi.org/10.1137/050628660

work page doi:10.1137/050628660 2006
[11]

Sapir, A. (2004). The Tower of Hanoi with forbidden moves.The Computer Journal, 47(1), 20–24.https://doi.org/10.1093/comjnl/47.1.20 19

work page doi:10.1093/comjnl/47.1.20 2004

[1] [1]

Aumann, S., G¨ otz, K. A. M., Hinz, A. M., & Petr, C. (2014). The number of moves of the largest disc in shortest paths on Hanoi graphs.The Electronic Journal of Combinatorics, 21(4), Article P4.38.https://doi.org/10.37236/4252

work page doi:10.37236/4252 2014

[2] [2]

Fried, S. (2025). Solving the Tower of Hanoi puzzle with heavy disks.The American Mathe- matical Monthly, 132(8), 806.https://doi.org/10.1080/00029890.2025.2491975

work page doi:10.1080/00029890.2025.2491975 2025

[3] [3]

Hinz, A. M. (1992). Shortest paths between regular states of the Tower of Hanoi.Information Sciences, 63(1–2), 173–181.https://doi.org/10.1016/0020-0255(92)90067-I 18

work page doi:10.1016/0020-0255(92)90067-i 1992

[4] [4]

Hinz, A. M. (2017). The Lichtenberg sequence.The Fibonacci Quarterly, 55(1), 2–12.https: //doi.org/10.1080/00150517.2017.12427786

work page doi:10.1080/00150517.2017.12427786 2017

[5] [5]

M., Klavˇ zar, S., & Petr, C

Hinz, A. M., Klavˇ zar, S., & Petr, C. (2018).The Tower of Hanoi: Myths and Maths(2nd ed.). Birkh¨ auser.https://doi.org/10.1007/978-3-319-73779-9

work page doi:10.1007/978-3-319-73779-9 2018

[6] [6]

M., & Parisse, D

Hinz, A. M., & Parisse, D. (2025). The Tower of Hanoi with heavy discs and some integer sequences.The Fibonacci Quarterly, 63(4), 711–716.https://doi.org/10.1080/00150517. 2025.2481593

work page doi:10.1080/00150517 2025

[7] [7]

(1883).R´ ecr´ eations math´ ematiques(Vol

Lucas, ´E. (1883).R´ ecr´ eations math´ ematiques(Vol. III). Gauthier-Villars et fils

work page

[8] [8]

Mehiri, E.-M., & Belbachir, H. (2024). The weighted Tower of Hanoi.Discrete Mathe- matics, Algorithms and Applications, 16(05), Article 2350051.https://doi.org/10.1142/ S1793830923500519

work page 2024

[9] [9]

(2026).The On-Line Encyclopedia of Integer Sequences.https:// oeis.org

OEIS Foundation Inc. (2026).The On-Line Encyclopedia of Integer Sequences.https:// oeis.org

work page 2026

[10] [10]

Romik, D. (2006). Shortest paths in the Tower of Hanoi graph and finite automata.SIAM Journal on Discrete Mathematics, 20(3), 610–622.https://doi.org/10.1137/050628660

work page doi:10.1137/050628660 2006

[11] [11]

Sapir, A. (2004). The Tower of Hanoi with forbidden moves.The Computer Journal, 47(1), 20–24.https://doi.org/10.1093/comjnl/47.1.20 19

work page doi:10.1093/comjnl/47.1.20 2004