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

1, 16, 112249, 36192508500267905991836

Offset

1,2

Comments

A superpermutation of order n is a string over the alphabet {1,...,n} such that every permutation of {1,...,n} occurs as a substring.

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.

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

a(5) = 27360223915482678295044186051702391878951111088124776744577\

815578589162223809195375150272260250093757648411736389359241,

while there is a unique palindromic one corresponding to a larger term, produced by the standard algorithm given in A332089's formula section.

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.

Links

Table of n, a(n) for n=1..4.

Robin Houston, Tackling the Minimal Superpermutation Problem, arXiv:1408.5108 [math.CO], 2014.

Nathaniel Johnston, Non-uniqueness of minimal superpermutations, arXiv:1303.4150 [math.CO], 2013; Discrete Math., 313 (2013), 1553-1557.

Wikipedia, Superpermutation.

Example

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).
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).
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).
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.

Prog

(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
  A332090(n)=fromdigits(digits(SP[n]), n+1)
/* Alternatively, considering A332089 as the more fundamental sequence: */
A332090(n)=fromdigits(A332089_row(n), n+1)

Crossrefs

Cf. A180632, A007489.

Sequence in context: A278289 A298202 A364777 * A333863 A343245 A300197

Adjacent sequences: A332087 A332088 A332089 * A332091 A332092 A332093

Keyword

nonn,base

Author

M. F. Hasler, Jul 28 2020

Status

approved