login
A247000
Maximal number of palindromes in a circular binary word of length n.
1
1, 2, 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, 23, 24, 26, 28, 29, 31, 33, 34, 36, 38, 39, 41, 43, 44, 46, 48
OFFSET
1,2
COMMENTS
The word is to be imagined as written around a circle. We only count palindromes of length m with 1 <= m <= n.
LINKS
David Consiglio, Jr., Alternate Python Program
Jamie Simpson, Palindromes in circular words, Theoretical Computer Science, Volume 550, 18 September 2014, Pages 66-78; DOI: 10.1016/j.tcs.2014.07.012.
FORMULA
Conjectures from Colin Barker, Nov 14 2015: (Start)
a(n) = a(n-1)+a(n-3)-a(n-4) for n>4.
G.f.: x*(x^13-x^12+x^11-x^10+x^9-x^8+x^7-x^6+x^3+2*x^2+x+1) / ((x-1)^2*(x^2+x+1)).
(End)
EXAMPLE
n a(n) Example of a word with a(n) palindromes
1 1 (a)
2 2 (aa)
3 4 (aab)
4 6 (aabb) Palindromes are a,b,aa,bb,abba,baab
5 7 (aaaab)
6 9 (aaaabb)
7 10 (aaaaaab)
8 12 (aaaaaabb)
9 13 (aaaaaaaab)
10 15 (aaaaaaaabb)
11 16 (aaaaaaaaaab)
12 18 (aaaaaaaaaabb)
13 19 (aaaaaaaaaaaab)
14 21 (aaaaaaaaaaaabb)
15 23 (aaaaabaaaabaaab)
16 24 (aaaaaaaaaaaaaabb)
17 26 (aaaaaabaaaaabaaab)
18 28 (aaaaaabaaaaabaaaab)
19 29 (aaaaaaabaaaaaabaaab)
20 31 (aaaaaaabaaaaaabaaaab)
21 33 (aaaaaaabaaaaaabaaaaab)
22 34 (aaaaaaaabaaaaaaabaaaab)
23 36 (aaaaaaaabaaaaaaabaaaaab)
24 38 (aaaaaaaabaaaaaaabaaaaaab)
25 39 (aaaaaaaaabaaaaaaaabaaaaab)
26 41 (aaaaaaaaabaaaaaaaabaaaaaab)
27 43 (aaaaaaaaabaaaaaaaabaaaaaaab)
28 44 (aaaaaaaaaabaaaaaaaaabaaaaaab)
29 46 (aaaaaaaaaabaaaaaaaaabaaaaaaab)
30 48 (aaaaaaaaaabaaaaaaaaabaaaaaaaab)
PROG
(Python)
def A247000(n):
....maxcount = 0
....for i in range(2**(n-1), 2**n):
........s = format(i, '0'+str(n)+'b')
........s, plist = s+s[:-1], []
........for j in range(n):
............for k in range(n):
................t = s[j:j+k+1]
................if t == t[::-1] and not t in plist:
....................plist.append(t)
........if len(plist) > maxcount:
............maxcount = len(plist)
....return maxcount # Chai Wah Wu, Sep 16 2014
CROSSREFS
Sequence in context: A289243 A183569 A248612 * A213356 A079393 A047512
KEYWORD
nonn,more
AUTHOR
N. J. A. Sloane, Sep 15 2014
EXTENSIONS
More terms from David Consiglio, Jr., Sep 16 2014
STATUS
approved