cp's OEIS Frontend

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.

%I A340458 #47 Apr 01 2021 15:06:18
%S A340458 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 A340458 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 A340458 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 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.
%C A340458 The uploaded Python script uses G. Manacher's algorithm to efficiently calculate the number of palindromes.
%H A340458 Serguei Zolotov, <a href="/A340458/b340458.txt">Table of n, a(n) for n = 1..5000</a>
%H A340458 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 A340458 Serguei Zolotov, <a href="/A340458/a340458.txt">Table of n, a(n), sample string for n = 1..5000</a>
%H A340458 Serguei Zolotov, <a href="/A340458/a340458_2.txt">Python script to generate b-file and a-file</a>
%F A340458 a(k*(k+1)/2) = k, from a string of k identical symbols.
%e A340458 The string AAA with length 3 has 6 palindromic substrings:
%e A340458     A starting at offset 1,
%e A340458     A starting at offset 2,
%e A340458     A starting at offset 3,
%e A340458    AA starting at offset 1,
%e A340458    AA starting at offset 2,
%e A340458   AAA starting at offset 1.
%e A340458 There is no shorter string with exactly 6 substring palindromes. So a(6) = 3.
%K A340458 nonn
%O A340458 1,2
%A A340458 _Serguei Zolotov_, Feb 13 2021