A152061 Counts of unique periodic binary strings of length n.

0, 0, 2, 2, 4, 2, 10, 2, 16, 8, 34, 2, 76, 2, 130, 38, 256, 2, 568, 2, 1036, 134, 2050, 2, 4336, 32, 8194, 512, 16396, 2, 33814, 2, 65536, 2054, 131074, 158, 266176, 2, 524290, 8198, 1048816, 2, 2113462, 2, 4194316, 33272, 8388610, 2, 16842496, 128, 33555424

Offset

0,3

Comments

a(p) = 2 for p prime.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2000

Achilles A. Beros, Bjørn Kjos-Hanssen, and Daylan Kaui Yogi, Planar digraphs for automatic complexity, arXiv:1902.00812 [cs.FL], 2019.

Formula

a(n) = 2^n - A001037(n) * n for n>0, a(0) = 0.

a(n) = 2^n - A027375(n) for n>0, a(0) = 0.

a(n) = 2^n - Sum_{d|n} mu(n/d) 2^d for n>0, a(0) = 0.

a(n) = 2^n - A143324(n,2).

a(n) = 2 * A178472(n) for n > 0. - Alois P. Heinz, Jul 04 2019

Example

a(3) = 2 = |{ 000, 111 }|, a(4) = 4 = |{ 0000, 1111, 0101, 1010 }|.

Maple

with(numtheory):
a:= n-> `if`(n=0, 0, 2^n -add(mobius(n/d)*2^d, d=divisors(n))):
seq(a(n), n=0..100);  # Alois P. Heinz, Sep 26 2011

Mathematica

a[0] = 0; a[n_] := 2^n - Sum[MoebiusMu[n/d]*2^d, {d, Divisors[n]}];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jul 04 2019 *)

Prog

(Python)
from sympy import mobius, divisors
def A152061(n): return -sum(mobius(n//d)<<d for d in divisors(n, generator=True) if d<n) # Chai Wah Wu, Sep 21 2024

Crossrefs

Row sums of A050870.

A050871 is bisection (even part). - R. J. Mathar, Sep 24 2011

Cf. A008683, A178472.

Sequence in context: A326486 A357817 A053204 * A103314 A306019 A194560

Adjacent sequences: A152058 A152059 A152060 * A152062 A152063 A152064

Keyword

nonn

Author

Jin S. Choi, Sep 24 2011

Status

approved