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