W-0099
A superpermutation on 9 symbols, found by 
- Length
- 408,719
- Repeated permutations
- 371
- Received
- Nov 10, 202620:25:05 UTC
012345678012345670812345670182345670128345670123845670123485670123458670123456870123456078123456071823456071283456071238…
Windows
| 408,711 | windows of 9 consecutive letters | |
| = | 362,880 | distinct permutations |
| + | 371 | repeated permutations |
| + | 45,460 | windows that are not permutations |
Detours by weight
A step is the move from one permutation in the superpermutation to the next permutation in it, and its weight is the number of letters added in that move. A detour starts at a step that differs from the next step of the recursive construction, and ends at the first permutation after that whose next step has weight 1. The weight of a detour is the number of letters added in it. After each detour, we consider the recursive construction to begin again from scratch at the permutation where the detour ends.
| Weight | Detours |
|---|---|
| 1 | 0 |
| 2 | 0 |
| 3 | 1,699 |
| 4 | 4 |
| 5 | 8 |
| 6 | 8 |
| 7 | 0 |
| 8 | 0 |
| 9 | 0 |
How it was found
From the submitter
Every n = 9 word of the 43/80 construction uses the same 52 closed trails, and an exact computation shows that no way of cutting and joining those trails beats 408,731. This word uses new trails. It starts from a selection on 8 symbols that is invariant under a group of order 9 (Q = 360, 15 walks). Four square flips using rows of charge 5 join walks: each adds 7 to Q but reduces the number of walks and trails by more. I applied the flips in random order among the improving ones, built a word from each resulting selection, and kept the shortest. Jakub Halfar's geng.py completed it into closed trails (Q = 388, 11 walks, 58 trails), and his trailsearch cut and joined them into this word.
Download
Learn about the Detour file format
Download Detour (.detour) 676 bytes
Download text (.txt) 408.7 kB