A265648 - OEIS

%I #13 Aug 17 2021 17:51:52

%S 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,

%T 5598,368,11140,0,23892,0,46194,1524,95552,0,193026,0,390774,6098,

%U 778684,0,1606572,0,3180700,24554,6488240,0,13003236,0,26349278,99384

%N 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.

%H Michael S. Branicky, <a href="/A265648/a265648.txt">Python program</a>

%F From _Michael S. Branicky_, Aug 17 2021: (Start)

%F a(n) <= A152061(n).

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

%F (End)

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

%p Negate:= proc(S) StringTools:-Map(procname,S) end proc:

%p Negate("0"):= "1":

%p Negate("1"):= "0":

%p FC0:= proc(n)

%p # set of binary strings of length n starting with 0 that are

%p # concatenations of nontrivial powers

%p option remember;

%p local m,s,t;

%p {seq(seq(seq(cat(s,t),s=FC(m)),t=map(r -> (r,Negate(r)),

%p     procname(n-m))),m=2..n-2)} union FC(n)

%p end proc:

%p FC0(2):= {"00"}:

%p FC:= proc(n)

%p # set of binary strings of length n starting with 0 that are

%p # nontrivial powers

%p option remember;

%p local d,s;

%p {seq(seq(cat(s$d),s = S0(n/d)),d = numtheory:-divisors(n) minus {1})}

%p end proc:

%p S0:= proc(n)

%p # set of binary strings of length n starting with 0

%p map(t -> cat("0",t), convert(StringTools:-Generate(n-1,"01"),set))

%p end proc:

%p FC2:= proc(n)

%p # set of binary strings of length n starting with 0 that are

%p # concatenations of two or more nontrivial powers

%p option remember;

%p local m,s,t;

%p {seq(seq(seq(cat(s,t),s=FC(m)),t=map(r -> (r,Negate(r)),FC0(n-m))),m=2..n-2)}

%p end proc:

%p seq(2*nops(FC0(n) minus FC2(n)),n=1..25); # _Robert Israel_, Dec 11 2015

%o (Python) # see link for faster version

%o from sympy import divisors

%o from itertools import product

%o def is_pow(s):

%o     return any(s == s[:d]*(len(s)//d) for d in divisors(len(s))[:-1])

%o def is_concat_pows(s, c):

%o     if len(s) < 2: return False

%o     if c > 0 and is_pow(s): return True

%o     for i in range(2, len(s)-1):

%o         if is_pow(s[:i]) and is_concat_pows(s[i:], c+1): return True

%o     return False

%o def ok(s):

%o     return is_pow(s) and not is_concat_pows(s, 0)

%o def pows_len(n): # generate powers of length n beginning with 0

%o     for d in divisors(n)[:-1]:

%o         for b in product("01", repeat=d-1):

%o             yield "".join(('0'+''.join(b))*(n//d))

%o def a(n):

%o     return 2*sum(ok(s) for s in pows_len(n) if s[0] == '0')

%o print([a(n) for n in range(1, 26)]) # _Michael S. Branicky_, Aug 17 2021

%K nonn

%O 1,2

%A _Jeffrey Shallit_, Dec 11 2015

%E a(26)-a(51) from _Michael S. Branicky_, Aug 17 2021