Yamagishi Complexity Torus LabYamagishi Lab
Mathematical physics

[Paper 413] Adding One Peg Destroys the Closed Form

Abstract

With three pegs the Tower of Hanoi takes $2^{n}-1$ moves. Add a peg and the count falls dramatically. This paper shows that it falls and the formula disappears—becoming easier and having a closed form are separate matters. No new theorem or law is claimed.

First, with three pegs $n=64$ takes $18{,}446{,}744{,}073{,}709{,}551{,}615$ moves, exactly $2^{64}-1$ (Section 2).

Second, at one move a second that is $\mathbf{5.8454\times10^{11}}$ years, or $\mathbf{42.3581}$ times the age of the universe (Section 2).

Third, this is the core of the paper. Add a peg and $n=64$ becomes $\mathbf{18{,}433}$ moves, a factor of $\mathbf{1.0007\times10^{15}}$—but no formula in $n$ of the kind that works for three pegs produces that $18{,}433$ (Section 3).

Fourth, how much is saved depends strongly on $n$: a factor of $2.38$ at $n=5$, $3628.29$ at $n=20$, and $1{,}047{,}553$ at $n=30$ (Section 3).

Fifth, the closed form $2^{n}-1$ agrees with the recursion $T(n)=2T(n-1)+1$ for every $n$ from $2$ to $29$ (Section 2).

Sixth, the separator is what a single move settles. With three pegs the next move is forced; with four, a split point must be chosen (Section 4).

Scope (what is not claimed)

No new theorem or law is claimed—the three-peg value $2^{n}-1$ and the Frame--Stewart recursion are both standard (1883, 1941). Optimality is not discussed—whether the four-peg value equals the true minimum is not the subject, and nothing is settled here. Only the question “can a closed form be written” is treated. Five or more pegs are not treated—only the contrast between three and four. No algorithm is designed—implementation and search methods are not the subject. No complexity theory is developed—this is not about $P$ and $NP$. The legend is not treated as history—the tale of the tower of Brahma is Lucas’s invention of 1883, and the comparison with the age of the universe is for legibility. Relation to earlier papers: Paper 411 showed that a transformation preserving nothing still has an invariant—there the shape broke and a quantity survived; here the quantity falls and the formula does not survive. Paper 300 showed that common root and distinct root can be decided—“easy to solve” and “expressible as a formula” are distinct roots by that criterion. Paper 412 showed that “nearest” is not defined until the distance is—here “the minimum number of moves” has no form until the number of pegs is fixed. What is added is tabulating three and four pegs at five values of $n$, giving the factor $1.0007\times10^{15}$ at $n=64$, checking $2^{n}-1$ against the recursion at $28$ values of $n$, giving the ratio to the age of the universe as $42.3581$, and placing the separator at “is the next move forced”.

1. Notation and the Question

Setting: Move $n$ discs under the rule that no disc may rest on a smaller one. With three pegs the minimum is given by

$$T_3(n)=2\,T_3(n-1)+1,\qquad T_3(1)=1$$

With four pegs, the top $k$ discs are parked and the rest moved with three pegs.

$$T_4(n)=\min_{1\le k<n}\bigl(2\,T_4(k)+2^{\,n-k}-1\bigr)$$

Observation 1.1　The three-peg formula is closed. $T_3(n)=2^{n}-1$—put in $n$ and the answer comes out.

Observation 1.2　The four-peg formula contains a $\min$. Where to split must be searched for—putting in $n$ does not produce the answer.

Question: Adding a peg makes the puzzle easier. Why does it make the formula harder.

2. Three Pegs: There Is a Closed Form

Computation 2.1: Evaluate $T_3(64)=2^{64}-1$ exactly.

$T_3(64)=18{,}446{,}744{,}073{,}709{,}551{,}615$.

Observation 2.2　Check the recursion against the closed form. Running $T(n)=2T(n-1)+1$ and comparing with $2^{n}-1$ agrees for every $n$ from $2$ to $29$—confirmation that the closed form is right.

Computation 2.3: At one move a second, how many years?

$\mathbf{5.8454\times10^{11}}$ years, which is $\mathbf{42.3581}$ times the age of the universe, $1.38\times10^{10}$ years.

Observation 2.4　The size of that number is available instantly, thanks to the closed form. One evaluates $2^{64}-1$—there is no need to trace the procedure.

3. Four Pegs: The Count Falls, the Formula Goes

Computation 3.1: Set three and four pegs side by side at the same $n$.

Discs $n$Three pegs $2^{n}-1$Four pegsRatio
$5$$31$$13$$2.38$
$10$$1{,}023$$49$$20.88$
$20$$1{,}048{,}575$$289$$3{,}628.29$
$30$$1{,}073{,}741{,}823$$1{,}025$$1{,}047{,}553.00$
$64$$18{,}446{,}744{,}073{,}709{,}551{,}615$$18{,}433$$1.0007\times10^{15}$

Observation 3.2　The saving is dramatic. A factor of $\mathbf{1.0007\times10^{15}}$ at $n=64$—what took $42$ times the age of the universe now takes about five hours at one move a second.

Observation 3.3　How much is saved depends strongly on $n$. At $n=5$ it is still only a factor of $2.38$—$3{,}628.29$ at $n=20$ and $1{,}047{,}553$ at $n=30$, because the gap opens exponentially.

Observation 3.4　But the number $18{,}433$ does not come directly out of a formula in $n$. The $k$ attaining the $\min$ must be found for each $n$—unlike $2^{n}-1$, substituting $n$ does not finish the job.

Observation 3.5　So “easier” and “expressible” pointed in opposite directions. The count fell by a factor of $10^{15}$—and the procedure for obtaining the answer grew longer.

4. The Separator

The separator: is the next move forced, or must it be chosen.

Observation 4.1　With three pegs there is no choice. There is nowhere to put the top $n-1$ discs except the free peg—one road, and so one recursion with one term.

Observation 4.2　With four pegs the number $k$ parked may be chosen. Any $1\le k<n$ will do—because there is a choice it is shorter, and because there is a choice there is no formula.

Observation 4.3　These are distinct roots by the criterion of Paper 300. “Easy to solve” is measured in moves—“expressible as a formula” is measured in the shape of the procedure. Two axes of the same problem.

Observation 4.4　More freedom bringing an optimisation with it happens elsewhere too. With one road no computation is needed—the moment there are several, a second question appears: which is best.

Observation 4.5　To be honest—this paper does not claim that no closed form exists for four pegs. It claims only that the elementary argument which works for three pegs does not carry over, and that a $\min$ remains in the expression—neither optimality nor the non-existence of a closed form is treated here.

Observation 4.6　One last thing—$2^{64}-1$ has the same shape as the grains of rice on the chessboard. Both come from “double at every step”—adding a peg splits that doubling and pushes it down.

5. Roll Call and Closing

  1. $T_3(64)=18{,}446{,}744{,}073{,}709{,}551{,}615$ (Computation 2.1): that is $2^{64}-1$.
  2. Recursion and closed form agree for $n=2$--$29$ (Observation 2.2): the form is confirmed.
  3. $5.8454\times10^{11}$ years at one move a second (Computation 2.3): not practical.
  4. $42.3581$ times the age of the universe (Computation 2.3): large as a ratio too.
  5. Four pegs give $18{,}433$ at $n=64$ (Computation 3.1): about five hours.
  6. A factor of $1.0007\times10^{15}$ (Observation 3.2): dramatic.
  7. Only $2.38$ at $n=5$ (Computation 3.1): no help when $n$ is small.
  8. $1{,}047{,}553$ at $n=30$ (Computation 3.1): the gap opens exponentially.
  9. A $\min$ remains in the four-peg expression (Observation 3.4): substitution does not finish.
  10. The separator is forced or chosen (Observation 4.2): a choice costs the formula.

Closing: With three pegs the Tower of Hanoi ends in a closed form—$T_3(n)=2^{n}-1$, so $n=64$ takes $\mathbf{18{,}446{,}744{,}073{,}709{,}551{,}615}$ moves. Running the recursion $T(n)=2T(n-1)+1$ agrees with it for every $n$ from $2$ to $29$, so the closed form is certain. At one move a second that is $\mathbf{5.8454\times10^{11}}$ years, or $\mathbf{42.3581}$ times the age of the universe—and the size is available instantly without tracing the procedure. That is what a closed form is for. Add one peg and the count falls dramatically—$n=64$ becomes $\mathbf{18{,}433}$ moves, a factor of $\mathbf{1.0007\times10^{15}}$, finishing in about five hours at one move a second. The saving depends strongly on $n$: only a factor of $2.38$ at $n=5$, $3{,}628.29$ at $n=20$, $1{,}047{,}553$ at $n=30$, the gap opening exponentially. But trying to write that $18{,}433$ as a formula in $n$, the hand stops—the four-peg recursion carries a $\min_{1\le k<n}$, and where to split must be found for each $n$. Unlike the three-peg case, substituting $n$ does not finish the job. So “easier” and “expressible” pointed in opposite directions: the count fell by a factor of $10^{15}$, and the procedure for obtaining the answer grew longer. One thing separates them—is the next move forced, or must it be chosen. With three pegs there is nowhere to put the top $n-1$ discs except the free peg, and one road gives one recursion with one term. With four pegs the number parked may be any $1\le k<n$—because there is a choice it is shorter, and because there is a choice there is no formula. They are distinct roots by the criterion of Paper 300: “easy to solve” is measured in moves, “expressible” in the shape of the procedure. To be honest—this paper does not claim that no closed form exists for four pegs. It claims only that the elementary argument which works for three does not carry over, and that a $\min$ remains. Neither optimality nor the non-existence of a closed form is treated here. One last thing—$2^{64}-1$ has the same shape as the grains of rice on the chessboard; both come from “double at every step”, and adding a peg splits that doubling and pushes it down.

References

  1. Lucas, É. (as N. Claus de Siam) (1883). La Tour d’Hanoï, véritable casse-tête annamite. Paris.
  2. Frame, J. S. (1941). Solution to Advanced Problem 3918. American Mathematical Monthly.
  3. Stewart, B. M. (1941). Solution to Advanced Problem 3918. American Mathematical Monthly.
  4. Hinz, A. M., Klavžar, S., Milutinović, U., & Petr, C. (2013). The Tower of Hanoi — Myths and Maths. Basel: Birkhäuser.
  5. Yamagishi, Y. (2026). The Three Hundredth Census: Whether Two Things Share a Root Is Decidable [Paper 300]. Zenodo. 10.5281/zenodo.22171914
  6. Yamagishi, Y. (2026). A Transformation That Preserves Nothing Still Has an Invariant [Paper 411]. Zenodo. 10.5281/zenodo.22699656
  7. Yamagishi, Y. (2026). “Nearest” Is Not Defined Until the Distance Is [Paper 412]. Zenodo. 10.5281/zenodo.22699661

Reference

Yamagishi, Y. (2026). Adding One Peg Destroys the Closed Form [Paper 413]. YOI: https://www.yamagishiyuuki.com/yoi/413
DOI: 10.5281/zenodo.22699750
ORCID: 0009-0006-8587-3450

PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS

The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 413. This paper is a preprint and has not been peer reviewed.