cp's OEIS Frontend

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.

%I A265648 #13 Aug 17 2021 17:51:52
%S A265648 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 A265648 5598,368,11140,0,23892,0,46194,1524,95552,0,193026,0,390774,6098,
%U A265648 778684,0,1606572,0,3180700,24554,6488240,0,13003236,0,26349278,99384
%N 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.
%H A265648 Michael S. Branicky, <a href="/A265648/a265648.txt">Python program</a>
%F A265648 From _Michael S. Branicky_, Aug 17 2021: (Start)
%F A265648 a(n) <= A152061(n).
%F A265648 a(p) = 0 for prime p >= 5.
%F A265648 (End)
%e A265648 For n = 6 the strings are (01)^3, (001)^2, (010)^2, (011)^2 and their complements.
%p A265648 Negate:= proc(S) StringTools:-Map(procname,S) end proc:
%p A265648 Negate("0"):= "1":
%p A265648 Negate("1"):= "0":
%p A265648 FC0:= proc(n)
%p A265648 # set of binary strings of length n starting with 0 that are
%p A265648 # concatenations of nontrivial powers
%p A265648 option remember;
%p A265648 local m,s,t;
%p A265648 {seq(seq(seq(cat(s,t),s=FC(m)),t=map(r -> (r,Negate(r)),
%p A265648     procname(n-m))),m=2..n-2)} union FC(n)
%p A265648 end proc:
%p A265648 FC0(2):= {"00"}:
%p A265648 FC:= proc(n)
%p A265648 # set of binary strings of length n starting with 0 that are
%p A265648 # nontrivial powers
%p A265648 option remember;
%p A265648 local d,s;
%p A265648 {seq(seq(cat(s$d),s = S0(n/d)),d = numtheory:-divisors(n) minus {1})}
%p A265648 end proc:
%p A265648 S0:= proc(n)
%p A265648 # set of binary strings of length n starting with 0
%p A265648 map(t -> cat("0",t), convert(StringTools:-Generate(n-1,"01"),set))
%p A265648 end proc:
%p A265648 FC2:= proc(n)
%p A265648 # set of binary strings of length n starting with 0 that are
%p A265648 # concatenations of two or more nontrivial powers
%p A265648 option remember;
%p A265648 local m,s,t;
%p A265648 {seq(seq(seq(cat(s,t),s=FC(m)),t=map(r -> (r,Negate(r)),FC0(n-m))),m=2..n-2)}
%p A265648 end proc:
%p A265648 seq(2*nops(FC0(n) minus FC2(n)),n=1..25); # _Robert Israel_, Dec 11 2015
%o A265648 (Python) # see link for faster version
%o A265648 from sympy import divisors
%o A265648 from itertools import product
%o A265648 def is_pow(s):
%o A265648     return any(s == s[:d]*(len(s)//d) for d in divisors(len(s))[:-1])
%o A265648 def is_concat_pows(s, c):
%o A265648     if len(s) < 2: return False
%o A265648     if c > 0 and is_pow(s): return True
%o A265648     for i in range(2, len(s)-1):
%o A265648         if is_pow(s[:i]) and is_concat_pows(s[i:], c+1): return True
%o A265648     return False
%o A265648 def ok(s):
%o A265648     return is_pow(s) and not is_concat_pows(s, 0)
%o A265648 def pows_len(n): # generate powers of length n beginning with 0
%o A265648     for d in divisors(n)[:-1]:
%o A265648         for b in product("01", repeat=d-1):
%o A265648             yield "".join(('0'+''.join(b))*(n//d))
%o A265648 def a(n):
%o A265648     return 2*sum(ok(s) for s in pows_len(n) if s[0] == '0')
%o A265648 print([a(n) for n in range(1, 26)]) # _Michael S. Branicky_, Aug 17 2021
%K A265648 nonn
%O A265648 1,2
%A A265648 _Jeffrey Shallit_, Dec 11 2015
%E A265648 a(26)-a(51) from _Michael S. Branicky_, Aug 17 2021