The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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) 170
 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 Row sums of triangle A143424. - Gary W. Adamson, Aug 14 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 run-lengths. - Gus Wiseman, Dec 21 2017 REFERENCES H. O. Peitgen and P. H. Richter, The Beauty of Fractals, Springer-Verlag; 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 Seiichi Manyama, Table of n, a(n) for n = 1..3322 (terms 1..300 from T. D. Noe) Hunki Baek, Sejeong Bang, Dongseok Kim, Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014. See Table 2. R. Chapman, D. Knuth, Problem 11243, Perfect Parity Patterns, Am. Math. Monthly 115 (7) (2008) p 668, function c(n). E. Deutsch and Lafayette College Problem Group, Problem 11161: Compositions without Common Factors, American Mathematical Monthly, vol. 114, No. 4, 2007, p. 363. H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260. R. Munafo, Enumeration of Period-N Mu-Atoms J. Shallit & N. J. A. Sloane, Correspondence 1974-1975 FORMULA a(n) = sum_{d|n} mu(n/d)*2^(d-1), Mobius transform of A011782. Furthermore, sum_{d|n} a(d) = 2^{n-1}. a(n) = A027375(n)/2 = A038199(n)/2. a(n) = sum_{k=0..n} A051168(n,k)*k. - Max Alekseyev, Apr 09 2013 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 G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - Ilya Gutkovskiy, Oct 24 2018 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>. From Gus Wiseman, Dec 19 2017: (Start) 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 run-lengths 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: a:=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 with(numtheory); A000740:=n-> add(mobius(n/d)*2^(d-1), d in divisors(n)); # N. J. A. Sloane, Oct 18 2012 MATHEMATICA 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 *) PROG (PARI) a(n) = sumdiv(n, d, moebius(n/d)*2^(d-1)) (Python) from sympy import mobius, divisors def a(n): return sum([mobius(n / d) * 2**(d - 1) for d in divisors(n)]) [a(n) for n in range(1, 101)]  # Indranil Ghosh, Jun 28 2017 CROSSREFS Cf. A000837, A003239, A008683, A008965, A022553, A034738, A035928, A038199, A051168, A054525, A056267, A059966, A143424, A167606, A178472, A216954, A228369, A294859, A296302. Equals A027375/2. See A056278 for a variant. First differences of A085945. Column k=2 of A143325. Sequence in context: A264686 A165729 A056278 * A161625 A234848 A300761 Adjacent sequences:  A000737 A000738 A000739 * A000741 A000742 A000743 KEYWORD nonn,nice,easy AUTHOR EXTENSIONS Connection with Mandelbrot set discovered by Warren D. Smith and proved by Robert Munafo, Feb 06 2000 Ambiguous term a(0) removed by Max Alekseyev, Jan 02 2012 STATUS approved

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.

Last modified May 29 06:31 EDT 2020. Contains 334697 sequences. (Running on oeis4.)