← All problems

The minimal superpermutation length conjecture

13 years old · traced to

A superpermutation on nn symbols is a string containing each of the n!n! permutations of those symbols as a contiguous substring; a minimal superpermutation is one of shortest possible length. The known recursive construction produces superpermutations of length

∑k=1nk!.\sum_{k=1}^n k!.

Minimal superpermutation length conjecture. The length of the minimal superpermutation on nn symbols is

∑k=1nk!.\sum_{k=1}^n k!.

The quantity n!+n−1n!+n-1 gives a trivial lower bound, but it is not tight for n≥3n\geq 3. The formula agrees with the optimal values known for n≤4n\leq 4, while minimal superpermutations for larger nn were not computable by the brute-force methods discussed in the source.

References

Status

Source: Nathaniel Johnston, “Non-Uniqueness of Minimal Superpermutations”, arXiv:1303.4150 (2013).

Progress summary

Refreshed
Open · solution reported

An explicit six-symbol example disproved the proposed formula in 2014, but the true shortest lengths from six symbols onward remain unknown.

Ashlock and Tillotson posed the conjecture in 1993: the shortest length should be ∑k=1nk!\sum_{k=1}^n k!. It is now known to be false, although the underlying optimization problem remains open for n≥6n \ge 6.

Known results

  • The minimum was established for n≤4n \le 4; the recursive construction is optimal there (Johnston, 2013).
  • Chaffin’s exhaustive search established the n=5n=5 minimum as 153=∑k=15k!153=\sum_{k=1}^5 k! and found exactly 88 examples (2014).
  • Houston’s construction gives length 872872 for n=6n=6, below the conjectured 873873 (2014).

August 2014 counterexample

Houston’s explicit n=6n=6 construction disproves the formula. Its recursive extension yields lengths below ∑k=1nk!\sum_{k=1}^n k! for every n≥6n \ge 6, but the exact minimum is unknown there; later records include a(7)≤5908a(7)\le 5908, a(8)≤46205a(8)\le 46205, and a(9)≤408966a(9)\le 408966.

Current status (as of August 2026): The conjectured formula is disproved for n=6n=6 and therefore for all n≥6n \ge 6 as a universal claim; the exact minimal lengths remain open for n≥6n \ge 6.

Sources

Solutions 0

No solutions have been posted yet.