login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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.

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

Sequence in context: A112342 A256094 A063712 * A185977 A204006 A106251

Adjacent sequences:  A340455 A340456 A340457 * A340459 A340460 A340461

KEYWORD

nonn

AUTHOR

Serguei Zolotov, Feb 13 2021

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 19 05:18 EDT 2021. Contains 345125 sequences. (Running on oeis4.)