%I #17 Aug 26 2020 06:08:32
%S 1,16,112249,36192508500267905991836
%N The smallest superpermutation of order n, read as a base n+1 number.
%C A superpermutation of order n is a string over the alphabet {1,...,n} such that every permutation of {1,...,n} occurs as a substring.
%C Such a string is the base n+1 representation of some number. The terms a(n) here are these numbers, corresponding to the lexicographically first superpermutation of minimal length A180632(n). This is the meaning of "smallest" in the name.
%C It is known that the superpermutations of minimal length are unique only for n < 5. For n = 5 there are 8 inequivalent superpermutations of minimal length 153. The lexicographically first one would correspond to
%C a(5) = 27360223915482678295044186051702391878951111088124776744577\
%C 815578589162223809195375150272260250093757648411736389359241,
%C while there is a unique palindromic one corresponding to a larger term, produced by the standard algorithm given in A332089's formula section.
%C The smallest superpermutation for n = 6 is not yet known for sure. The smallest known has 872 letters, so a(6) ~ 7^870 ~ 10^735, which is too large to be displayed here.
%H Robin Houston, <a href="http://arxiv.org/abs/1303.4150">Tackling the Minimal Superpermutation Problem</a>, arXiv:1408.5108 [math.CO], 2014.
%H Nathaniel Johnston, <a href="http://arxiv.org/abs/1303.4150">Non-uniqueness of minimal superpermutations</a>, arXiv:1303.4150 [math.CO], 2013; Discrete Math., 313 (2013), 1553-1557.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Superpermutation">Superpermutation</a>.
%e For n=2, the shortest superpermutation is '121': it contains the permutations (1,2) and (2,1) as substrings. Considered as a number in base 3 this is 1*3^2 + 2*3 + 1 = 16 = a(2).
%e For n=3, the shortest superpermutation is '123121321': it contains all permutations of {1,2,3} as substrings. As a number written in base 4 this is 1*4^8 + 2*4^7 + ... + 1 = 112249 = a(3).
%e For n=4, the shortest superpermutation is '123412314231243121342132413214321'. As a number written in base 5 this is 1*5^32 + ... + 2*5 + 1 = 36192508500267905991836 = a(4).
%e From n=5 on, the shortest superpermutation is no longer unique: there are 8 inequivalent ones of minimal length 153. Only one of them is symmetric with respect to reversal of the digits, which is not the case for the lexicographically first one, which corresponds to the number a(5) ~ 6^152 + 2*6^151 + ... + 1*6 + 2 ~ 2.7e18.
%o (PARI) SP=[1, 121, 123121321, 123412314231243121342132413214321, fromdigits([d-37| d<-Vecsmall("&<R1G4<N>G1HN<3Y2OXG:ZO2[:GY3H:RE3YDOZ3<XOD[<1RD=H1P4=D>P:[EXP>NER2=4ENH=2>P1")], 100)] \\ custom base100 encoding
%o A332090(n)=fromdigits(digits(SP[n]),n+1)
%o /* Alternatively, considering A332089 as the more fundamental sequence: */
%o A332090(n)=fromdigits(A332089_row(n),n+1)
%Y Cf. A180632, A007489.
%K nonn,base
%O 1,2
%A _M. F. Hasler_, Jul 28 2020