Thread: what should I post ? View Single Post
2018-02-02, 02:38   #19
CRGreathouse

Aug 2006

597910 Posts

Quote:
 Originally Posted by science_man_88 I do see ways to cut down the number to search. Because, you can use symmetries picking (a,b) and (b',a') where apostrophies mean reversed permutations, will not change much at the same length, it can in theory reverse the superpermutation.
That cuts it down to a little more than
$n^{n! + (n-1)! + (n-2)! + n-3}/2.$

You can do better: reassign the variables so the first one you use is 1, the first one you use other than that is 2, and so on. This cuts it to about
$n^{n! + (n-1)! + (n-2)! + n-3}/n! \approx n^{n! + (n-1)! + (n-2)! - 3}.$

But these numbers are huge, we need to do much, much better.