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

Author

Serguei Zolotov, Feb 13 2021

Keywords

• nonn

Comments

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

Examples

			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.
		

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.