Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #47 Apr 01 2021 15:06:18
%S 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,
%T 10,11,8,9,10,10,11,11,11,12,12,9,10,11,11,12,12,12,13,13,14,10,11,12,
%U 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
%N 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.
%C The uploaded Python script uses G. Manacher's algorithm to efficiently calculate the number of palindromes.
%H Serguei Zolotov, <a href="/A340458/b340458.txt">Table of n, a(n) for n = 1..5000</a>
%H Glenn Manacher, <a href="https://dl.acm.org/doi/10.1145/321892.321896">A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string</a>, Journal of the ACM, (1975) 22 (3): 346-351.
%H Serguei Zolotov, <a href="/A340458/a340458.txt">Table of n, a(n), sample string for n = 1..5000</a>
%H Serguei Zolotov, <a href="/A340458/a340458_2.txt">Python script to generate b-file and a-file</a>
%F a(k*(k+1)/2) = k, from a string of k identical symbols.
%e The string AAA with length 3 has 6 palindromic substrings:
%e A starting at offset 1,
%e A starting at offset 2,
%e A starting at offset 3,
%e AA starting at offset 1,
%e AA starting at offset 2,
%e AAA starting at offset 1.
%e There is no shorter string with exactly 6 substring palindromes. So a(6) = 3.
%K nonn
%O 1,2
%A _Serguei Zolotov_, Feb 13 2021