login
A347583
Number of length-2n binary strings of the form xxyy, with x and y both nonempty.
1
0, 4, 14, 42, 116, 292, 722, 1682, 3920, 8820, 19770, 43578, 95540, 207244, 447812, 960676, 2053292, 4368094, 9262226, 19571396, 41243844, 86678272, 181752522, 380276248, 794120918
OFFSET
1,2
FORMULA
A347582(n) - 2^n <= a(n). - Michael S. Branicky, Jan 23 2022
EXAMPLE
For n=3 the sequence counts the strings 000000, 000011, 000101, 001010, 001111, 010100, 010111 and their binary complements.
PROG
(Python)
from itertools import product
from functools import cache
@cache
def b(n): # length-2n binary strings of the form ww
return set(w+w for w in product(b"01", repeat=n))
def a(n):
return len(set(s+t for i in range(1, n) for s in b(i) for t in b(n-i)))
print([a(n) for n in range(1, 18)]) # Michael S. Branicky, Jan 23 2022
(Python) # bit-based version
from itertools import product
def b(n): # length-2n binary strings of the form ww
for i in range(2**n):
yield (i << n) + i
def a(n):
st = set()
for i in range(1, n):
for w in b(i):
s = w << (2*(n-i))
for t in b(n-i):
st.add(s+t)
return len(st)
print([a(n) for n in range(1, 20)]) # Michael S. Branicky, Jan 25 2022
CROSSREFS
Cf. A347582 (where x, y are allowed to be empty).
Sequence in context: A124616 A335514 A221058 * A124617 A124618 A189052
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Jan 23 2022
EXTENSIONS
a(18)-a(21) from Michael S. Branicky, Jan 23 2022
a(22)-a(25) from Michael S. Branicky, Jan 25 2022
STATUS
approved