login
A265642
Number of binary strings of length n that can be written as the concatenation of nontrivial powers of other strings.
1
0, 2, 2, 6, 6, 26, 24, 94, 118, 340, 464, 1298, 1842, 4860, 7448, 18188, 29344, 68900, 114638, 260558, 447954, 986664, 1739736, 3746824, 6732712, 14241630, 26009968, 54182570, 100266862, 206375170, 385891332, 786632426, 1483493024, 3000203428, 5697403240
OFFSET
1,2
FORMULA
a(n) = 2^n - A265639(n).
EXAMPLE
For n = 5, the 6 strings are 00000,00011,00111,11000,11100,11111.
MAPLE
Negate:= proc(S) StringTools:-Map(procname, S) end proc:
Negate("0"):= "1":
Negate("1"):= "0":
FC:= 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=FC1(m)), t=map(r -> (r, Negate(r)),
procname(n-m))), m=2..n-2)} union FC1(n)
end proc:
FC(2):= {"00"}:
FC1:= proc(n)
# set of nontrivial powers of length n starting with 0
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:
seq(2*nops(FC(n)), n=1..22); # Robert Israel, Dec 11 2015
CROSSREFS
Cf. A265639.
Sequence in context: A081123 A056038 A076929 * A186944 A247525 A305295
KEYWORD
nonn,base
AUTHOR
Jeffrey Shallit, Dec 11 2015
EXTENSIONS
a(17)-a(25) from Robert Israel, Dec 11 2015
a(26)-a(35) from Lars Blomberg, Dec 20 2015
STATUS
approved