login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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)
19
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. 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). - D. E. 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, American Mathematical Monthly, vol. 114, No. 4, 2007, p. 363). [From Emeric Deutsch, Aug 13 2008]

Moebius transform (A054525) of [1, 2, 4, 8,...]; = row sums of triangle A143424. [From Gary W. Adamson, Aug 14 2008]

REFERENCES

E. Deutsch and Lafayette College Problem Group, Problem 11161, 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 (1964), 241-260.

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

T. D. Noe, Table of n, a(n) for n=1..300

R. Chapman, D. Knuth, Problem 11243, Perfect Parity Patterns, Am. Math. Monthly 115 (7) (2008) p 668, function c(n).

R. Munafo, Enumeration of Period-N Mu-Atoms

Index entries for sequences related to Lyndon words

FORMULA

a(n) = sum_{d|n} mu(n/d)*2^(d-1). 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

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

MAPLE

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

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

CROSSREFS

Cf. A003239, A022553, A034738, A035928, A000837, A216954, A054525, A143424, A008683, A178472, A167606, A051168, A056267, A038199.

Equals A027375/2.

See A056278 for a variant.

Sequence in context: A134774 A165729 A056278 * A161625 A234848 A069712

Adjacent sequences:  A000737 A000738 A000739 * A000741 A000742 A000743

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane.

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 2 14:44 EDT 2014. Contains 246361 sequences.