login
A370410
Number of length-n binary strings that are the concatenation of two nonempty palindromes.
1
0, 4, 6, 14, 26, 48, 86, 148, 232, 400, 622, 982, 1514, 2440, 3482, 5680, 8162, 12932, 18398, 29146, 40706, 64856, 90070, 141880, 196448, 309712, 425412, 668978, 917450, 1437148, 1966022, 3074080, 4192882, 6545344, 8912278, 13877920, 18874298, 29341624, 39842594, 61835140, 83886002, 129977116, 176160686, 272563362
OFFSET
1,2
COMMENTS
a(6618) has 1001 digits. - Michael S. Branicky, Feb 21 2024
LINKS
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
a(n) = A007055(n) - A056458(n) (conjectured). - Michael S. Branicky, Feb 18 2024
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
(Python) # uses formula above; functions/imports in A007055, A056458
def a(n): return A007055(n) - A056458(n)
print([a(n) for n in range(1, 45)]) # Michael S. Branicky, Feb 21 2024
CROSSREFS
Cf. A007055 (allows the palindromes to be empty), A056458.
Sequence in context: A027632 A175722 A200186 * A192782 A306742 A188576
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Feb 18 2024
EXTENSIONS
a(21)-a(44) from Michael S. Branicky, Feb 18 2024
STATUS
approved