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

Author

Jeffrey Shallit, Dec 11 2015

Keywords

• nonn

Examples

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

Links

• Michael S. Branicky, Python program

Programs

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

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

Formula

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

a(n) <= A152061(n).

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

(End)

Extensions

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