cp's OEIS Frontend

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

%I A136094 #29 Jul 25 2020 23:22:44
%S A136094 1,121,1213121,123412314213,1234512341523142351,
%T A136094 1234516234152361425312643512,123451672341526371425361274351263471253,
%U A136094 1234156782315426738152643718265341278635124376812453
%N A136094 a(n) is the smallest number consisting of digits {1,...,n} that contains all the permutations of {1,...,n} as subsequences.
%C A136094 It is unclear how a(n) is defined for n >= 10.
%H A136094 P. J. Koutas and T. C. Hu, <a href="http://dx.doi.org/10.1016/0012-365X(75)90004-7">Shortest String Containing All Permutations</a>, Discrete Mathematics, Vol. 11, 1975, pp. 125-132.
%H A136094 S.P. Mohanty, <a href="http://dx.doi.org/10.1016/0012-365X(80)90177-6">Shortest string containing all permutations</a>, Discrete Mathematics, Volume 31, Issue 1, 1980, Pages 91-95.
%t A136094 NextTuple[x_, n_, l_] := Module[{i, x0 = x},
%t A136094    If[x0 == ConstantArray[n, l], Return[{}]];
%t A136094    For[i = l, i >= 1, i--,
%t A136094     If[x0[[i]] < n, x0[[i]]++; Return[x0], x0[[i]] = 1]]];
%t A136094 Join[{1}, Table[p = Permutations[Range[n], {n}];
%t A136094   For[tl = n + 1, tl <= 50, tl++,
%t A136094    tup = ConstantArray[1, tl];
%t A136094    While[tup = NextTuple[tup, n, tl]; tup != {},
%t A136094     If[Product[Count[tup, i], {i, 1, n}] == 0, Continue[]];
%t A136094     For[j = 1, j <= Length[p], j++,
%t A136094      perm = p[[j]]; lst = tup; fnd = True;
%t A136094      For[k = 1, k <= Length[perm], k++,
%t A136094       If[lst == {}, fnd = False; Break[]];
%t A136094       p1 = Position[lst, perm[[k]], 1, 1];
%t A136094       If[Length[p1] == 0, fnd = False; Break[]];
%t A136094       p1 = First@First@p1;
%t A136094       If[! IntegerQ[p1], fnd = False; Break[]];
%t A136094       lst = Drop[lst, p1];
%t A136094       ]; If[! fnd, Break[]]]; If[fnd, Break[]]]; If[fnd, Break[]]];
%t A136094 FromDigits@tup, {n, 2, 5}]] (* _Robert Price_, Oct 13 2019 *)
%Y A136094 The lengths of the terms are given by A062714.
%K A136094 base,nonn,more,hard
%O A136094 1,2
%A A136094 Aniruddha Das (hi.annie.pal(AT)gmail.com), May 10 2008
%E A136094 Edited by _N. J. A. Sloane_, May 16 2008
%E A136094 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).
%E A136094 a(3) and a(5) are corrected from A062714, incorrect terms a(6), a(7) are removed by _Max Alekseyev_, Apr 14 2013
%E A136094 a(3) corrected, a(6) added by _Max Alekseyev_, May 14 2013
%E A136094 a(7) added by _Vitaliy Garnashevich_, Mar 31 2017
%E A136094 a(8) added by _Vitaliy Garnashevich_, Jun 24 2020