|
%I M2582 N1021 #143 Apr 15 2024 08:32:36
%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, and 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 and 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 J. E. Iglesias, <a href="https://doi.org/10.1524/zkri.1981.155.1-2.121">A formula for the number of closest packings of equal spheres having a given repeat period</a>, Z. Krist. 155 (1981) 121-127, Table 2.
%H Wolfdieter Lang, <a href="https://arxiv.org/abs/2307.10645">Cantor's List of Real Algebraic Numbers of Heights 1 to 7</a>, arXiv:2307.10645 [math.NT], 2023.
%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 François Vigneron and Nicolae Mihalache, <a href="https://arxiv.org/abs/2402.06083">How to split a tera-polynomial</a>, arXiv:2402.06083 [math.NA], 2024.
%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 and [Iglesias eq (6)). - _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.
%Y Row sums of A356027.
%K nonn,nice,easy,changed
%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
|
