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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A027375 Number of aperiodic binary strings of length n; also number of binary sequences with primitive period n. 22
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; text; internal format)
OFFSET

0,2

COMMENTS

A sequence S is aperiodic if it is not of the form S = T^k with k>1. - N. J. A. Sloane, Oct 26 2012

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, Aug 13 2006

REFERENCES

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 13. - From N. J. A. Sloane, Oct 26 2012

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.

Blanchet-Sadri, Francine. Algorithmic combinatorics on partial words. Chapman & Hall/CRC, Boca Raton, FL, 2008. ii+385 pp. ISBN: 978-1-4200-6092-8; 1-4200-6092-9 MR2384993 (2009f:68142). See p. 164. - N. J. A. Sloane, Apr 06 2012

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.

B. Chaffin, J. P. Linderman, N. J. A. Sloane and _Allan Wilks_, On Curling Numbers of Integer Sequences, arXiv:1212.6102, Dec 25 2012.

B. Chaffin, J. P. Linderman, N. J. A. Sloane and _Allan Wilks_, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 85

O. Georgiou, C. P. Dettmann and E. G. Altmann, Faster than expected escape for a class of fully chaotic maps, Arxiv preprint arXiv:1207.7000, 2012 - From N. J. A. Sloane, Dec 23 2012

M. B. Nathanson, Primitive sets and Euler phi function for subsets of {1,2,...,n}, arXiv:math.NT/0608150

P. Pongsriiam, Relatively Prime Sets, Divisor Sums, and Partial Sums, preprint.

P. Pongsriiam, A remark on relative prime sets, Integers 13 (2013), A49.

FORMULA

a(n) = sum(d|n, mu(d)*2^(n/d)).

a(n) = 2*A000740(n).

a(n) = n*A001037(n).

sum(d|n, a(n)) = 2^n.

a(p) = 2^p-2 for p prime. - R. J. Mathar, Aug 13 2006

EXAMPLE

a(3) = 6 = |{ 001, 010, 001, 011, 010, 110 }|

MAPLE

with(numtheory): A027375 :=n->add( mobius(d)*2^(n/d), d in divisors(n)); # From N. J. A. Sloane, Sep 25 2012

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

(Haskell)

a027375 n = n * a001037 n  -- Reinhard Zumkeller, Feb 01 2013

CROSSREFS

A027375, A038199 and A056267 are all essentially the same sequence with different initial terms.

Cf. A020921, A216953.

Column k=2 of A143324.

Sequence in context: A216215 A052994 A088219 * A059727 A103872 A216641

Adjacent sequences:  A027372 A027373 A027374 * A027376 A027377 A027378

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Comments from Frank Ruskey, Jan 17 2000

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 April 20 09:30 EDT 2014. Contains 240779 sequences.