A136094 a(n) is the smallest number consisting of digits {1,...,n} that contains all the permutations of {1,...,n} as subsequences.

1, 121, 1213121, 123412314213, 1234512341523142351, 1234516234152361425312643512, 123451672341526371425361274351263471253, 1234156782315426738152643718265341278635124376812453

Offset: 1

Author

Aniruddha Das (hi.annie.pal(AT)gmail.com), May 10 2008

Keywords

• base
• nonn
• more
• hard

Comments

It is unclear how a(n) is defined for n >= 10.

Links

• P. J. Koutas and T. C. Hu, Shortest String Containing All Permutations, Discrete Mathematics, Vol. 11, 1975, pp. 125-132.
• S.P. Mohanty, Shortest string containing all permutations, Discrete Mathematics, Volume 31, Issue 1, 1980, Pages 91-95.

Crossrefs

The lengths of the terms are given by A062714.

Programs

Mathematica

NextTuple[x_, n_, l_] := Module[{i, x0 = x},
   If[x0 == ConstantArray[n, l], Return[{}]];
   For[i = l, i >= 1, i--,
    If[x0[[i]] < n, x0[[i]]++; Return[x0], x0[[i]] = 1]]];
Join[{1}, Table[p = Permutations[Range[n], {n}];
  For[tl = n + 1, tl <= 50, tl++,
   tup = ConstantArray[1, tl];
   While[tup = NextTuple[tup, n, tl]; tup != {},
    If[Product[Count[tup, i], {i, 1, n}] == 0, Continue[]];
    For[j = 1, j <= Length[p], j++,
     perm = p[[j]]; lst = tup; fnd = True;
     For[k = 1, k <= Length[perm], k++,
      If[lst == {}, fnd = False; Break[]];
      p1 = Position[lst, perm[[k]], 1, 1];
      If[Length[p1] == 0, fnd = False; Break[]];
      p1 = First@First@p1;
      If[! IntegerQ[p1], fnd = False; Break[]];
      lst = Drop[lst, p1];
      ]; If[! fnd, Break[]]]; If[fnd, Break[]]]; If[fnd, Break[]]];
FromDigits@tup, {n, 2, 5}]] (* Robert Price, Oct 13 2019 *)

Extensions

Edited by N. J. A. Sloane, May 16 2008

a(4) corrected from 1234321234321 to 123412314213 by Bridget Tenner, Apr 21 2009, who also confirms a(1), a(2), a(3) and a(5).

a(3) and a(5) are corrected from A062714, incorrect terms a(6), a(7) are removed by Max Alekseyev, Apr 14 2013

a(3) corrected, a(6) added by Max Alekseyev, May 14 2013

a(7) added by Vitaliy Garnashevich, Mar 31 2017

a(8) added by Vitaliy Garnashevich, Jun 24 2020