A265648 Number of binary strings of length n that are powers of shorter strings, but cannot be written as the concatenation of two or more such strings.

0, 2, 2, 2, 0, 8, 0, 10, 6, 20, 0, 48, 0, 74, 26, 146, 0, 372, 0, 630, 94, 1350, 0, 2864, 0, 5598, 368, 11140, 0, 23892, 0, 46194, 1524, 95552, 0, 193026, 0, 390774, 6098, 778684, 0, 1606572, 0, 3180700, 24554, 6488240, 0, 13003236, 0, 26349278, 99384

Offset

1,2

Links

Table of n, a(n) for n=1..51.

Michael S. Branicky, Python program

Formula

From Michael S. Branicky, Aug 17 2021: (Start)

a(n) <= A152061(n).

a(p) = 0 for prime p >= 5.

(End)

Example

For n = 6 the strings are (01)^3, (001)^2, (010)^2, (011)^2 and their complements.

Maple

Negate:= proc(S) StringTools:-Map(procname, S) end proc:
Negate("0"):= "1":
Negate("1"):= "0":
FC0:= proc(n)
# set of binary strings of length n starting with 0 that are
# concatenations of nontrivial powers
option remember;
local m, s, t;
{seq(seq(seq(cat(s, t), s=FC(m)), t=map(r -> (r, Negate(r)),
    procname(n-m))), m=2..n-2)} union FC(n)
end proc:
FC0(2):= {"00"}:
FC:= proc(n)
# set of binary strings of length n starting with 0 that are
# nontrivial powers
option remember;
local d, s;
{seq(seq(cat(s$d), s = S0(n/d)), d = numtheory:-divisors(n) minus {1})}
end proc:
S0:= proc(n)
# set of binary strings of length n starting with 0
map(t -> cat("0", t), convert(StringTools:-Generate(n-1, "01"), set))
end proc:
FC2:= proc(n)
# set of binary strings of length n starting with 0 that are
# concatenations of two or more nontrivial powers
option remember;
local m, s, t;
{seq(seq(seq(cat(s, t), s=FC(m)), t=map(r -> (r, Negate(r)), FC0(n-m))), m=2..n-2)}
end proc:
seq(2*nops(FC0(n) minus FC2(n)), n=1..25); # Robert Israel, Dec 11 2015

Prog

(Python) # see link for faster version
from sympy import divisors
from itertools import product
def is_pow(s):
    return any(s == s[:d]*(len(s)//d) for d in divisors(len(s))[:-1])
def is_concat_pows(s, c):
    if len(s) < 2: return False
    if c > 0 and is_pow(s): return True
    for i in range(2, len(s)-1):
        if is_pow(s[:i]) and is_concat_pows(s[i:], c+1): return True
    return False
def ok(s):
    return is_pow(s) and not is_concat_pows(s, 0)
def pows_len(n): # generate powers of length n beginning with 0
    for d in divisors(n)[:-1]:
        for b in product("01", repeat=d-1):
            yield "".join(('0'+''.join(b))*(n//d))
def a(n):
    return 2*sum(ok(s) for s in pows_len(n) if s[0] == '0')
print([a(n) for n in range(1, 26)]) # Michael S. Branicky, Aug 17 2021

Crossrefs

Sequence in context: A165490 A298819 A307520 * A181230 A262372 A292520

Adjacent sequences: A265645 A265646 A265647 * A265649 A265650 A265651

Keyword

nonn

Author

Jeffrey Shallit, Dec 11 2015

Extensions

a(26)-a(51) from Michael S. Branicky, Aug 17 2021

Status

approved