I wonder about the two related problems a), b) where we want the smallest N such that: a) each permutation of n letters must occur as a counterclockwise substring of some circular ordering on N letters; b) each permutation of n letters must occur as a substring of some circular ordering on N letters. (Each substring can occur either counterclockwise or clockwise.) I can't tell whether the N of case a) is likely to be bigger or smaller than the N for the original problem (a linear ordering containing each permutation of n letters). —Dan Warut Roonguthai wrote: ----- Mystery Math Whiz and Novelist Advance Permutation Problem https://www.quantamagazine.org/sci-fi-writer-greg-egan-and-anonymous-math-wh... On Thu, Oct 25, 2018 at 10:24 PM James Propp <jamespropp@gmail.com> wrote:

Maybe the anonymous prover was Satoshi Nakamoto?

Jim Propp

On Wednesday, October 24, 2018, Allan Wechsler <acwacw@gmail.com> wrote:

...

At http://mathsci.wikia.com/wiki/The_Haruhi_Problem, we have an intriguing situation.

The problem is, what is the shortest string that contains every permutation on N letters as a substring.

The problem has been around for a while, but somebody posted it on Wikia, a wiki dedicated to fans of various TV programs, mostly anime.

Then an anonymous commenter posted a proof of a lower-bound that had been conjectured earlier, that the shortest string must have length at least n! + (n-1)! + (n-2)! + n - 3, for n > 2. The style is a little bit amateurish but the proof seems correct. Robin Houston, a mathematician who has worked on the problem, has vetted it.

Nobody knows who the prover is.