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
KEYWORD
nonn
AUTHOR
Serguei Zolotov, Feb 13 2021
STATUS
approved