A340458 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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.