|
| |
|
|
A027375
|
|
Number of aperiodic binary strings of length n; also number of binary sequences with primitive period n.
|
|
15
| |
|
|
0, 2, 2, 6, 12, 30, 54, 126, 240, 504, 990, 2046, 4020, 8190, 16254, 32730, 65280, 131070, 261576, 524286, 1047540, 2097018, 4192254, 8388606, 16772880, 33554400, 67100670, 134217216, 268419060, 536870910, 1073708010, 2147483646, 4294901760
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| Equivalently, number of output sequences with primitive period n from a simple cycling shift register.
Also, the number of nonempty subsets A of the set of the integers 1 to n such that gcd(A) is relatively prime to n (for n>=1). - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Aug 13 2006
|
|
|
REFERENCES
| E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..300
J.-P. Allouche, Note on the transcendence of a generating function. In A. Laurincikas and E. Manstavicius, editors, Proceedings of the Palanga Conference for the 75th birthday of Prof. Kubilius, New trends in Probab. and Statist., Vol. 4, pages 461-465, 1997.
M. B. Nathanson, Primitive sets and and Euler phi function for subsets of {1,2,...,n}, math.NT/0608150
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 85
|
|
|
FORMULA
| a(n) = sum(d|n, mu(d)*2^(n/d)).
a(n) = n*A001037(n).
sum(d|n, a(n)) = 2^n.
a(p) = 2^p-2 for p prime. - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Aug 13 2006
|
|
|
EXAMPLE
| a(3) = 6 = |{ 001, 010, 001, 011, 010, 110 }|
|
|
|
MATHEMATICA
| Table[ Apply[ Plus, MoebiusMu[ n / Divisors[n] ]*2^Divisors[n] ], {n, 1, 32} ]
|
|
|
PROG
| (PARI) a(n) = sumdiv(n, d, moebius(n/d)*2^d);
|
|
|
CROSSREFS
| Essentially the same as A038199.
Cf. A056267.
Cf. A020921.
Sequence in context: A019311 A052994 A088219 * A059727 A103872 A191970
Adjacent sequences: A027372 A027373 A027374 * A027376 A027377 A027378
|
|
|
KEYWORD
| nonn,nice,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Comments from Frank Ruskey (ruskey(AT)cs.uvic.ca), Jan 17 2000
|
| |
|
|
