

A000740


Number of 2nbead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive ncycle.
(Formerly M2582 N1021)


199



1, 1, 3, 6, 15, 27, 63, 120, 252, 495, 1023, 2010, 4095, 8127, 16365, 32640, 65535, 130788, 262143, 523770, 1048509, 2096127, 4194303, 8386440, 16777200, 33550335, 67108608, 134209530, 268435455, 536854005, 1073741823, 2147450880
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Also number of compositions of n into relatively prime parts (that is, the gcd of all the parts is 1). Also number of subsets of {1,2,..,n} containing n and consisting of relatively prime numbers.  Vladeta Jovovic, Aug 13 2003
Also number of perfect parity patterns that have exactly n columns (see A118141).  Don Knuth, May 11 2006
a(n) is odd if and only if n is squarefree (Tim Keller).  Emeric Deutsch, Apr 27 2007
a(n) is a multiple of 3 for all n>=3 (see Problem 11161 link).  Emeric Deutsch, Aug 13 2008
a(n) is the number of monic irreducible polynomials with nonzero constant coefficient in GF(2)[x] of degree n.  Michel Marcus, Oct 30 2016
a(n) is the number of aperiodic compositions of n, the number of compositions of n with relatively prime parts, and the number of compositions of n with relatively prime runlengths.  Gus Wiseman, Dec 21 2017


REFERENCES

H. O. Peitgen and P. H. Richter, The Beauty of Fractals, SpringerVerlag; contribution by A. Douady, p. 165.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS



FORMULA

a(n) = Sum_{dn} mu(n/d)*2^(d1), Mobius transform of A011782. Furthermore, Sum_{dn} a(d) = 2^(n1).
Recurrence relation: a(n) = 2^(n1)  Sum_{dn,d>1} a(n/d). (Lafayette College Problem Group; see the Maple program and [Iglesias eq (6)).  Emeric Deutsch, Apr 27 2007


EXAMPLE

For n=4, there are 6 compositions of n into coprime parts: <3,1>, <2,1,1>, <1,3>, <1,2,1>, <1,1,2>, and <1,1,1,1>.
The a(6) = 27 aperiodic compositions are:
(11112), (11121), (11211), (12111), (21111),
(1113), (1122), (1131), (1221), (1311), (2112), (2211), (3111),
(114), (123), (132), (141), (213), (231), (312), (321), (411),
(15), (24), (42), (51),
(6).
The a(6) = 27 compositions into relatively prime parts are:
(111111),
(11112), (11121), (11211), (12111), (21111),
(1113), (1122), (1131), (1212), (1221), (1311), (2112), (2121), (2211), (3111),
(114), (123), (132), (141), (213), (231), (312), (321), (411),
(15), (51).
The a(6) = 27 compositions with relatively prime runlengths are:
(11112), (11121), (11211), (12111), (21111),
(1113), (1131), (1212), (1221), (1311), (2112), (2121), (3111),
(114), (123), (132), (141), (213), (231), (312), (321), (411),
(15), (24), (42), (51),
(6).
(End)


MAPLE

with(numtheory): a[1]:=1: a[2]:=1: for n from 3 to 32 do div:=divisors(n): a[n]:=2^(n1)sum(a[n/div[j]], j=2..tau(n)) od: seq(a[n], n=1..32); # Emeric Deutsch, Apr 27 2007


MATHEMATICA

a[n_] := Sum[ MoebiusMu[n/d]*2^(d  1), {d, Divisors[n]}]; Table[a[n], {n, 1, 32}] (* JeanFrançois Alcover, Feb 03 2012, after PARI *)


PROG

(PARI) a(n) = sumdiv(n, d, moebius(n/d)*2^(d1))
(Python)
from sympy import mobius, divisors
def a(n): return sum([mobius(n / d) * 2**(d  1) for d in divisors(n)])


CROSSREFS

Cf. A000837, A003239, A008683, A008965, A022553, A034738, A035928, A038199, A051168, A054525, A056267, A059966, A143424, A167606, A178472, A216954, A228369, A294859, A296302.


KEYWORD

nonn,nice,easy


AUTHOR



EXTENSIONS



STATUS

approved



