A330022 Length of shortest binary string containing all palindromes of length n as substrings.

0, 2, 4, 8, 12, 22, 32, 60, 74, 142, 180, 344, 408

Offset

0,2

Comments

Greedy supersequence algorithms give the upper bounds a(7) <= 60, a(8) <= 74, a(9) <= 142, a(10) <= 180, a(11) <= 344, a(12) <= 410, a(13) <= 798. Probably some of these are tight.

The value for a(6) was computed by checking all 8! arrangements of the 8 palindromes of length 3, optimizing overlaps.

Computing a(n) can be posed as a Hamiltonian path problem on the weighted complete graph with the binary palindromes of length n as vertices and the overlap distances between them as weights. - Max Alekseyev, Nov 22 2025

Links

Table of n, a(n) for n=0..12.

Example

The corresponding strings are:
  1: 01
  2: 0011
  3: 00010111
  4: 000011001111
  5: 0000010001010111011111
  6: 00000011001111000010010110111111
  7: 000000010000011100011111011101011011010101000101001001111111 [Max Alekseyev, Nov 22 2025]
  8: 00000000100100001011010010111101101111110011110000110000001100110011111111 [Max Alekseyev, Nov 22 2025]

Crossrefs

Cf. A057148, A291633, A390882 (number of shortest superstrings).

Sequence in context: A103787 A365076 A327480 * A362261 A032473 A084422

Adjacent sequences: A330019 A330020 A330021 * A330023 A330024 A330025

Keyword

nonn,more

Author

Jeffrey Shallit, Nov 27 2019

Extensions

Edited and a(7)-a(12) added by Max Alekseyev, Nov 22 2025

Status

approved