[math-fun] Lower bound in superpermutation problem proven by anonymous anime fan
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.
I bet someone knows who the prover is. (But remarkable, really!) On Wed, Oct 24, 2018 at 8:03 PM 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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Allan Wechsler -
James Propp -
Tomas Rokicki -
Warut Roonguthai