login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A136094 a(n) is the smallest number consisting of digits {1,...,n} that contains all the permutations of {1,...,n} as subsequences. 2
1, 121, 1213121, 123412314213, 1234512341523142351, 1234516234152361425312643512, 123451672341526371425361274351263471253, 1234156782315426738152643718265341278635124376812453 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
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.
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 *)
CROSSREFS
The lengths of the terms are given by A062714.
Sequence in context: A227301 A261364 A317956 * A317197 A082215 A123179
KEYWORD
base,nonn,more,hard
AUTHOR
Aniruddha Das (hi.annie.pal(AT)gmail.com), May 10 2008
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
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 25 01:35 EDT 2024. Contains 371964 sequences. (Running on oeis4.)