cp's OEIS Frontend

A332090 The smallest superpermutation of order n, read as a base n+1 number.

%I A332090 #17 Aug 26 2020 06:08:32
%S A332090 1,16,112249,36192508500267905991836
%N A332090 The smallest superpermutation of order n, read as a base n+1 number.
%C A332090 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 A332090 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 A332090 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 A332090   a(5) = 27360223915482678295044186051702391878951111088124776744577\
%C A332090          815578589162223809195375150272260250093757648411736389359241,
%C A332090   while there is a unique palindromic one corresponding to a larger term, produced by the standard algorithm given in A332089's formula section.
%C A332090 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 A332090 Robin Houston, <a href="http://arxiv.org/abs/1303.4150">Tackling the Minimal Superpermutation Problem</a>, arXiv:1408.5108 [math.CO], 2014.
%H A332090 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 A332090 Wikipedia, <a href="http://en.wikipedia.org/wiki/Superpermutation">Superpermutation</a>.
%e A332090 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 A332090 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 A332090 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 A332090 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 A332090 (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   A332090(n)=fromdigits(digits(SP[n]),n+1)
%o A332090 /* Alternatively, considering A332089 as the more fundamental sequence: */
%o A332090 A332090(n)=fromdigits(A332089_row(n),n+1)
%Y A332090 Cf. A180632, A007489.
%K A332090 nonn,base
%O A332090 1,2
%A A332090 _M. F. Hasler_, Jul 28 2020