Minimal superpermutation length $L(9)$
The length of the shortest string that contains each permutation of $9$ symbols as a contiguous substring.
Lower bound:
$408246$
(408,246)
Upper bound:
$408966$
(408,966)
Verified bounds
Verified bounds come with a certificate that is checked automatically: a formal proof in Lean, or an explicit construction checked by a program. Submit a certificate.
- Lower bound: None yet
- Upper bound: None yet
Updates from the literature
-
Upper bound: $409113$
(409,113)
Reference unknown
[via Superpermutations - Greg Egan] -
Upper bound: $408966$
(408,966)
Reference unknown
[via Superpermutations - Greg Egan] -
2018-10-25
Lower bound: $408246$
(408,246)
Anonymous 4chan poster, R. Houston, J. Pantone and V. Vatter. A lower bound on the length of the shortest superpattern (2018).
[via Superpermutations - Greg Egan]