cp's OEIS Frontend

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

%I A370410 #63 Mar 23 2024 20:57:18
%S A370410 0,4,6,14,26,48,86,148,232,400,622,982,1514,2440,3482,5680,8162,12932,
%T A370410 18398,29146,40706,64856,90070,141880,196448,309712,425412,668978,
%U A370410 917450,1437148,1966022,3074080,4192882,6545344,8912278,13877920,18874298,29341624,39842594,61835140,83886002,129977116,176160686,272563362
%N A370410 Number of length-n binary strings that are the concatenation of two nonempty palindromes.
%C A370410 a(6618) has 1001 digits. - _Michael S. Branicky_, Feb 21 2024
%H A370410 Michael S. Branicky, <a href="/A370410/b370410.txt">Table of n, a(n) for n = 1..6617</a>
%H A370410 Michael S. Branicky, <a href="/A370410/a370410.txt">Python program for A370410 (bitwise operations)</a>
%H A370410 Michael S. Branicky, <a href="/A370410/a370410_1.txt">Python program for A370410 (explicit construction)</a>
%H A370410 R. C. Lyndon and M. P. Schützenberger, <a href="http://doi.org/10.1307/mmj/1028998766">The equation a^M = b^N c^P in a free group</a>, Michigan Math. J., 9(4):289-298, 1962.
%F A370410 a(n) = A007055(n) - A056458(n) (conjectured). - _Michael S. Branicky_, Feb 18 2024
%F A370410 From _Daniel Gabric_, Feb 21 2024: (Start)
%F A370410 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.
%F A370410 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.
%F A370410 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)
%o A370410 (Python) # see below and Links for faster programs
%o A370410 from itertools import product
%o A370410 def p(w): return w == w[::-1]
%o A370410 def c(w): return any(p(w[:i]) and p(w[i:]) for i in range(1, len(w)))
%o A370410 def a(n): return 2*sum(1 for w in product("01", repeat=n-1) if c(("1",)+w))
%o A370410 print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Feb 18 2024
%o A370410 (Python)
%o A370410 from itertools import product
%o A370410 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])
%o A370410 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)))
%o A370410 print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Feb 18 2024
%o A370410 (Python) # uses formula above; functions/imports in A007055, A056458
%o A370410 def a(n): return A007055(n) - A056458(n)
%o A370410 print([a(n) for n in range(1, 45)]) # _Michael S. Branicky_, Feb 21 2024
%Y A370410 Cf. A007055 (allows the palindromes to be empty), A056458.
%K A370410 nonn
%O A370410 1,2
%A A370410 _Jeffrey Shallit_, Feb 18 2024
%E A370410 a(21)-a(44) from _Michael S. Branicky_, Feb 18 2024