login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.
(Formerly M2582 N1021)
172

%I M2582 N1021

%S 1,1,3,6,15,27,63,120,252,495,1023,2010,4095,8127,16365,32640,65535,

%T 130788,262143,523770,1048509,2096127,4194303,8386440,16777200,

%U 33550335,67108608,134209530,268435455,536854005,1073741823,2147450880

%N Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

%C 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

%C Also number of perfect parity patterns that have exactly n columns (see A118141). - _Don Knuth_, May 11 2006

%C a(n) is odd if and only if n is squarefree (Tim Keller). - _Emeric Deutsch_, Apr 27 2007

%C a(n) is a multiple of 3 for all n>=3 (see Problem 11161 link). - _Emeric Deutsch_, Aug 13 2008

%C Row sums of triangle A143424. - _Gary W. Adamson_, Aug 14 2008

%C 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

%C 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 run-lengths. - _Gus Wiseman_, Dec 21 2017

%D H. O. Peitgen and P. H. Richter, The Beauty of Fractals, Springer-Verlag; contribution by A. Douady, p. 165.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Seiichi Manyama, <a href="/A000740/b000740.txt">Table of n, a(n) for n = 1..3322</a> (terms 1..300 from T. D. Noe)

%H Hunki Baek, Sejeong Bang, Dongseok Kim, Jaeun Lee, <a href="http://arxiv.org/abs/1412.2426">A bijection between aperiodic palindromes and connected circulant graphs</a>, arXiv:1412.2426 [math.CO], 2014. See Table 2.

%H R. Chapman, D. Knuth, <a href="http://www.jstor.org/stable/27642574">Problem 11243, Perfect Parity Patterns</a>, Am. Math. Monthly 115 (7) (2008) p 668, function c(n).

%H E. Deutsch and Lafayette College Problem Group, <a href="http://www.jstor.org/stable/27642212">Problem 11161: Compositions without Common Factors</a>, American Mathematical Monthly, vol. 114, No. 4, 2007, p. 363.

%H H. W. Gould, <a href="http://www.fq.math.ca/Scanned/2-4/gould.pdf">Binomial coefficients, the bracket function and compositions with relatively prime summands</a>, Fib. Quart. 2(4) (1964), 241-260.

%H R. Munafo, <a href="http://www.mrob.com/pub/muency/enumerationoffeatures.html">Enumeration of Period-N Mu-Atoms</a>

%H J. Shallit & N. J. A. Sloane, <a href="/A002949/a002949.pdf">Correspondence 1974-1975</a>

%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>

%F a(n) = sum_{d|n} mu(n/d)*2^(d-1), Mobius transform of A011782. Furthermore, sum_{d|n} a(d) = 2^{n-1}.

%F a(n) = A027375(n)/2 = A038199(n)/2.

%F a(n) = sum_{k=0..n} A051168(n,k)*k. - _Max Alekseyev_, Apr 09 2013

%F Recurrence relation: a(n) = 2^(n-1) - Sum_{d|n,d>1} a(n/d). (Lafayette College Problem Group; see the Maple program). - _Emeric Deutsch_, Apr 27 2007

%F G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - _Ilya Gutkovskiy_, Oct 24 2018

%e 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>.

%e From _Gus Wiseman_, Dec 19 2017: (Start)

%e The a(6) = 27 aperiodic compositions are:

%e (11112), (11121), (11211), (12111), (21111),

%e (1113), (1122), (1131), (1221), (1311), (2112), (2211), (3111),

%e (114), (123), (132), (141), (213), (231), (312), (321), (411),

%e (15), (24), (42), (51),

%e (6).

%e The a(6) = 27 compositions into relatively prime parts are:

%e (111111),

%e (11112), (11121), (11211), (12111), (21111),

%e (1113), (1122), (1131), (1212), (1221), (1311), (2112), (2121), (2211), (3111),

%e (114), (123), (132), (141), (213), (231), (312), (321), (411),

%e (15), (51).

%e The a(6) = 27 compositions with relatively prime run-lengths are:

%e (11112), (11121), (11211), (12111), (21111),

%e (1113), (1131), (1212), (1221), (1311), (2112), (2121), (3111),

%e (114), (123), (132), (141), (213), (231), (312), (321), (411),

%e (15), (24), (42), (51),

%e (6).

%e (End)

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

%p with(numtheory); A000740:=n-> add(mobius(n/d)*2^(d-1), d in divisors(n)); # _N. J. A. Sloane_, Oct 18 2012

%t a[n_] := Sum[ MoebiusMu[n/d]*2^(d - 1), {d, Divisors[n]}]; Table[a[n], {n, 1, 32}] (* _Jean-Fran├žois Alcover_, Feb 03 2012, after Pari *)

%o (PARI) a(n) = sumdiv(n,d,moebius(n/d)*2^(d-1))

%o (Python)

%o from sympy import mobius, divisors

%o def a(n): return sum([mobius(n / d) * 2**(d - 1) for d in divisors(n)])

%o [a(n) for n in range(1, 101)] # _Indranil Ghosh_, Jun 28 2017

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

%Y Equals A027375/2.

%Y See A056278 for a variant.

%Y First differences of A085945.

%Y Column k=2 of A143325.

%K nonn,nice,easy

%O 1,3

%A _N. J. A. Sloane_

%E Connection with Mandelbrot set discovered by _Warren D. Smith_ and proved by _Robert Munafo_, Feb 06 2000

%E Ambiguous term a(0) removed by _Max Alekseyev_, Jan 02 2012

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 13 06:25 EDT 2020. Contains 335675 sequences. (Running on oeis4.)