Superpermutation

The first four smallest superpermutations have respective lengths 1, 3, 9, and 33, forming the strings 1, 121, 123121321, and 123412314231243121342132413214321.

One such superpermutation is shown below, while another of the same length can be obtained by switching all of the fours and fives in the second half of the string (after the bold 2):[1] 12345123­41523412­53412354­12314523­14253142­35142315­42312453­12435124­31524312­54312134­52134251­34215342­13542132­45132415­32413524­13254132­14532143­52143251­432154321 For the cases of n > 5, a smallest superpermutation has not yet been proved nor a pattern to find them, but lower and upper bounds for them have been found.

In September 2011, an anonymous poster on the Science & Math ("/sci/") board of 4chan proved that the smallest superpermutation on n symbols (n ≥ 2) has at least length n!

[3] In reference to the Japanese anime series The Melancholy of Haruhi Suzumiya, particularly the fact that it was originally broadcast as a nonlinear narrative, the problem was presented on the imageboard as "The Haruhi Problem":[4] if you wanted to watch the 14 episodes of the first season of the series in every possible order, what would be the shortest string of episodes you would need to watch?

[5] The proof for this lower bound came to the general public interest in October 2018, after mathematician and computer scientist Robin Houston tweeted about it.

[3] On 25 October 2018, Robin Houston, Jay Pantone, and Vince Vatter posted a refined version of this proof in the On-Line Encyclopedia of Integer Sequences (OEIS).

[5][6] A published version of this proof, credited to "Anonymous 4chan poster", appears in Engen and Vatter (2021).

[7] For "The Haruhi Problem" specifically (the case for 14 symbols), the current lower and upper bound are 93,884,313,611 and 93,924,230,411, respectively.

[8] On 20 October 2018, by adapting a construction by Aaron Williams for constructing Hamiltonian paths through the Cayley graph of the symmetric group,[9] science fiction author and mathematician Greg Egan devised an algorithm to produce superpermutations of length n!

[2] On 27 February 2019, using ideas developed by Robin Houston, Egan produced a superpermutation for n = 7 of length 5906.

[2] Whether similar shorter superpermutations also exist for values of n > 7 remains an open question.