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

Author

Jin S. Choi, Sep 24 2011

Keywords

• nonn

Comments

a(p) = 2 for p prime.

Examples

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

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.

Crossrefs

Row sums of A050870.

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

Cf. A008683, A178472.

Programs

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 *)

Python

from sympy import mobius, divisors
def A152061(n): return -sum(mobius(n//d)<Chai Wah Wu, Sep 21 2024

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