Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the 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