A265642 Number of binary strings of length n that can be written as the concatenation of nontrivial powers of other strings.

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

Links

Table of n, a(n) for n=1..35.

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

Adjacent sequences: A265639 A265640 A265641 * A265643 A265644 A265645

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