A180632 -id:A180632 - cp's OEIS frontend

A324145 Minimal length of a string over the alphabet A = {1,2,...,n} that contains every derangement of A as a substring exactly once.

0, 2, 4, 22, 102, 662, 4678

Offset: 1

José Eduardo Castrejón González, Feb 17 2019

Such strings could be called superderangements (compare A180632).
From Rob Pratt, Feb 22 2019: (Start)
I used the TSP (Traveling Salesman) solver in SAS, which discovered the values reported for n = 4 through 7 and proved that they are optimal.
For n = 2 and 3, the optimal solution is unique.
For n = 4, there are exactly four optimal solutions:
4321431241314234123421
4312413142341234214321
4312341231424134214321
4321431234123142413421
(End)

			Examples of minimal superderangements for 2,3,4 symbols:
For n = 2: 21, length 2.
For n = 3: 2312, length = 4 (For n=3 there are just two derangements, 231 and 312, so 2312 is clearly optimal.)
For n = 4: 4312413142341234214321, length = 22 (optimality established by _Rob Pratt_, Feb 21 2019).
For examples for n = 5, 6, and 7 that were discovered and proved optimal by _Rob Pratt_ using SAS, see the link.
Strings for n = 4,5,6,7 were earlier found by _Sigurd Kittilsen_ and _Lars Tveito_, although they did not prove they were optimal.

Rob Pratt, Solutions for n = 5, 6, 7

Cf. A000166, A180632.

a(4) confirmed and a(5)-a(7) found by Rob Pratt, Feb 21 2019

Edited by N. J. A. Sloane, Feb 21 2019

A332088 Primes which yield again a prime when the digits are taken according to the lexicographically first superpermutation of corresponding order and of minimal length.

Original entry on oeis.org

2, 3, 5, 7, 13, 19, 31, 37, 79, 109, 113, 139, 193, 317, 331, 911, 991, 1453, 1481, 1669, 1831, 1901, 7127, 7561, 7589, 7687, 9343, 9413, 9811, 11369, 13397, 19759, 19961, 31397, 33181, 33809, 37567, 39089, 41017, 41257, 41399, 49633, 59921, 61651, 67409, 77573, 81131, 83621, 87011, 91837, 93493, 97127

Offset: 1

M. F. Hasler, Jul 28 2020

See A180632 for more about superpermutations, i.e., strings over a finite alphabet, say {1, ..., n}, that contain all permutations thereof as a substring. "Digits taken according to ..." means the number whose i-th digit is d[s[i]], 1 <= i <= A180632(#d), where d and s are the sequences of digits of the prime and of the superpermutation, respectively.
In March 2014, Ben Chaffin showed that minimal superpermutations of order n = 5 have length 153, and found all 8 distinct superpermutations of this kind (the lexicographically first being non-palindromic), so the 5-digit terms are known. For n = 6, Robin Houston has found a few months later several superpermutations of length 872 (one less than the previously conjectured minimal length), but we still don't know which is the shortest (and/or lexico-first) superpermutation for that case.
This is a variant of A244311, which (by definition) lacks single-digit terms and which uses the easily computed palindromic superpermutations produced by the classical recursive algorithm (see PARI code there), of non-minimal length A007489(n) for n > 5 and non-minimal lex order for n = 5. The lexico-first minimal-length superpermutations aren't palindromic, and therefore the corresponding primes aren't so here, in contrast to A244311.

			The superpermutations with minimal length of less than 5 objects are unique (up to the choice of the symbols), the one for 3 objects is "123121321".
The prime p = 109 is in this sequence since under the above superpermutation (i.e., taking the 1st, 2nd, 3rd, 1st, 2nd, 1st, 3rd, 2nd and 1st digit) it yields the number 109101901 which is also prime.
The minimal superpermutation of order 5 is the first one to be not palindromic, it reads "1234512...3254312". Correspondingly, when this "acts on" the 5-digit prime p = 11369, we get a non-palindromic 153 digit prime P = 1136911...3196311 whose 7th digit from the left is p's 2nd digit, '1', but whose 7th digit from the right is p's 3rd digit, '3'.

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

Cf. A180632 (length of the superpermutations and primes related to n-digit terms), A007489 (upper bound and corresponding lengths in A244311), A244311 (a variant of this sequence), A224986 (related to the difference between A180632 and A007489).

SP=[digits(p) | p <- [1, 121, 123121321, 123412314231243121342132413214321, fromdigits( [d-37| d<-Vecsmall( "&G1HN<3Y2OXG:ZO2[:GY3H:RE3YDOZ3P:[EXP>NER2=4ENH=2>P1")], 100)]] /* minimal superperms up to n=5, in custom base100 encoding for n=5 for lack of algorithm and to avoid the 153-digit decimal number */
is_A332088(n)=ispseudoprime(fromdigits(vecextract(n=digits(n),SP[#n])))
(A332088_upto(N)=select( is_A332088, primes([1,N])))(10^5)

A374085 Number of sequences of length A062714(n) with symbols from {1, 2, 3, ..., n} which contains, as a subsequence, each possible ordering of the n symbols 1, 2, 3, ..., n.

Original entry on oeis.org

1, 2, 42, 216

Offset: 1

Chai Wah Wu, Jun 27 2024

a(n) is a multiple of n!.

			a(1) = 1 as '1' is the only sequence of length A062714(1) = 1.
a(2) = 2 corresponding to the sequences of length A062714(2) = 3 : {'121', '212'}.
a(3) = 42 corresponding to the sequences of length A062714(3) = 7 : {'1213121', '1213212', '1231213', '1231231', '1231321', '1232123', '1232132', '1312131', '1312313', '1321231', '1321312', '1321321', '1323123', '1323132', '2123121', '2123212', '2131213', '2131231', '2132123', '2132132', '2132312', '2312132', '2312312', '2312321', '2313213', '2313231', '2321232', '2321323', '3121312', '3121321', '3123123', '3123132', '3123213', '3132131', '3132313', '3212312', '3212321', '3213123', '3213213', '3213231', '3231232', '3231323'}.

Cf. A062714, A180632.

A376069 a(n) is the lexicographically earliest minimal superpermutation on n symbols, where the symbols are {1, 2, ..., n}, with 1 <= n <= 9.

Original entry on oeis.org

1, 121, 123121321, 123412314231243121342132413214321, 123451234152341253412354123145213425134215342135421345214352145321452314253142351423154231245312435124315243125432154325143254132451324153241352413254312

Offset: 1

Paolo Xausa, Sep 20 2024

Please refer to A332089 (the main entry, where symbols in each superpermutation are individually listed) for more information.

In this sequence superpermutations are encoded by concatenating the symbols in a single word. Such encoding ensures unambiguous representation only up to n = 9.

Michael Engen and Vincent Vatter, Containing All Permutations, The American Mathematical Monthly, 128 (1), 2021, pp. 4-24 (preprint version).
James Grime and Brady Haran, Superpermutations, Numberphile video, 2018.
Nathaniel Johnston, Non-uniqueness of minimal superpermutations, Discrete Mathematics, Vol. 313, Issue 14, 2013, pp. 1553-1557 (preprint version).
Nathaniel Johnston, All Minimal Superpermutations on Five Symbols Have Been Found, 2014.
Wikipedia, Superpermutation.

Cf. A180632, A332089, A332090, A341300, A376269.

A376572 Triangle read by rows: T(n,k) is the frequency of the symbol k in the lexicographically earliest minimal superpermutation on n symbols, where the symbols are {1, 2, ..., n}.

Original entry on oeis.org

1, 2, 1, 4, 3, 2, 10, 9, 8, 6, 32, 33, 31, 31, 26

Offset: 1

Paolo Xausa, Sep 28 2024

Equivalently, T(n,k) is the frequency of k in row n of A332089 (see there for more information).

			Triangle begins:
  n\k|  1   2   3   4   5  ...
  ----------------------------
   1 |  1;
   2 |  2,  1;
   3 |  4,  3,  2;
   4 | 10,  9,  8,  6;
   5 | 32, 33, 31, 31, 26;
  ...
For n = 3, the minimal superpermutation is 123121321; symbol 1 appears 4 times, symbol 2 appears 3 times and symbol 3 appears 2 times.

Michael Engen and Vincent Vatter, Containing All Permutations, The American Mathematical Monthly, 128 (1), 2021, pp. 4-24 (preprint version).
Wikipedia, Superpermutation.

Cf. A180632 (row sums, for n >= 1), A332089.

cp's OEIS Frontend

A324145 Minimal length of a string over the alphabet A = {1,2,...,n} that contains every derangement of A as a substring exactly once.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A332088 Primes which yield again a prime when the digits are taken according to the lexicographically first superpermutation of corresponding order and of minimal length.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A374085 Number of sequences of length A062714(n) with symbols from {1, 2, 3, ..., n} which contains, as a subsequence, each possible ordering of the n symbols 1, 2, 3, ..., n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A376069 a(n) is the lexicographically earliest minimal superpermutation on n symbols, where the symbols are {1, 2, ..., n}, with 1 <= n <= 9.

Views

Author

Keywords

Comments

Links

Crossrefs

A376572 Triangle read by rows: T(n,k) is the frequency of the symbol k in the lexicographically earliest minimal superpermutation on n symbols, where the symbols are {1, 2, ..., n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs