A370410 Number of length-n binary strings that are the concatenation of two nonempty palindromes.

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

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

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

Adjacent sequences: A370407 A370408 A370409 * A370411 A370412 A370413

Keyword

nonn

Author

Jeffrey Shallit, Feb 18 2024

Extensions

a(21)-a(44) from Michael S. Branicky, Feb 18 2024

Status

approved