OFFSET
1,2
COMMENTS
a(6618) has 1001 digits. - Michael S. Branicky, Feb 21 2024
LINKS
Michael S. Branicky, Table of n, a(n) for n = 1..6617
Michael S. Branicky, Python program for A370410 (bitwise operations)
Michael S. Branicky, Python program for A370410 (explicit construction)
R. C. Lyndon and M. P. Schützenberger, The equation a^M = b^N c^P in a free group, Michigan Math. J., 9(4):289-298, 1962.
FORMULA
From Daniel Gabric, Feb 21 2024: (Start)
Proof of the above formula: Let w be a length-n binary string that is the concatenation of two possibly empty palindromes. It suffices to show that w is not the concatenation of two nonempty palindromes iff w is a primitive palindrome.
We prove the forward direction. Suppose w is not the concatenation of two nonempty palindromes. By assumption, w is the concatenation of two possibly empty palindromes. Therefore, w must be a palindrome. Suppose, for the sake of a contradiction, that w is not primitive. Then w = z^i for some nonempty string z and some integer i>=2. But since w is a palindrome, we have that z^i = w = w^R = (z^i)^R = (z^R)^i, which implies z is a palindrome. Thus, w is the concatenation of the nonempty palindromes z and z^(i-1), a contradiction.
Now we prove the backward direction. Assume, for the sake of a contradiction, that w is a primitive palindrome, and w = uv for some nonempty palindromes u and v. Then uv = w = w^R = (uv)^R = v^Ru^R = vu. By Lemma 3 in a paper of Lyndon and Schützenberger (see links for reference), uv = vu implies w is not primitive, a contradiction. (End)
PROG
(Python) # see below and Links for faster programs
from itertools import product
def p(w): return w == w[::-1]
def c(w): return any(p(w[:i]) and p(w[i:]) for i in range(1, len(w)))
def a(n): return 2*sum(1 for w in product("01", repeat=n-1) if c(("1", )+w))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Feb 18 2024
(Python)
from itertools import product
def bin_pals(d): yield from ("".join(p+(m, )+p[::-1]) for p in product("01", repeat=d//2) for m in [[""], ["0", "1"]][d%2])
def a(n): return len(set(a+b for i in range(1, n) for a in bin_pals(i) for b in bin_pals(n-i)))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Feb 18 2024
print([a(n) for n in range(1, 45)]) # Michael S. Branicky, Feb 21 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Feb 18 2024
EXTENSIONS
a(21)-a(44) from Michael S. Branicky, Feb 18 2024
STATUS
approved