A340458 Minimum length of the string over the alphabet of 3 or more symbols that has exactly n substring palindromes. Substrings are counted as distinct if they start at different offsets.

1, 2, 2, 3, 4, 3, 4, 5, 5, 4, 5, 6, 6, 7, 5, 6, 7, 7, 8, 8, 6, 7, 8, 8, 9, 9, 9, 7, 8, 9, 9, 10, 10, 10, 11, 8, 9, 10, 10, 11, 11, 11, 12, 12, 9, 10, 11, 11, 12, 12, 12, 13, 13, 14, 10, 11, 12, 12, 13, 13, 13, 14, 14, 15, 14, 11, 12, 13, 13, 14, 14, 14, 15, 15, 16, 15, 16, 12, 13, 14, 14, 15, 15, 15, 16, 16, 17, 16, 17, 17

Offset

1,2

Comments

The uploaded Python script uses G. Manacher's algorithm to efficiently calculate the number of palindromes.

Links

Serguei Zolotov, Table of n, a(n) for n = 1..5000

Glenn Manacher, A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string, Journal of the ACM, (1975) 22 (3): 346-351.

Serguei Zolotov, Table of n, a(n), sample string for n = 1..5000

Serguei Zolotov, Python script to generate b-file and a-file

Formula

a(k*(k+1)/2) = k, from a string of k identical symbols.

Example

The string AAA with length 3 has 6 palindromic substrings:
    A starting at offset 1,
    A starting at offset 2,
    A starting at offset 3,
   AA starting at offset 1,
   AA starting at offset 2,
  AAA starting at offset 1.
There is no shorter string with exactly 6 substring palindromes. So a(6) = 3.

Crossrefs

Sequence in context: A112342 A256094 A063712 * A185977 A204006 A369879

Adjacent sequences: A340455 A340456 A340457 * A340459 A340460 A340461

Keyword

nonn

Author

Serguei Zolotov, Feb 13 2021

Status

approved