

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.  Frank Ruskey, Jan 17 2000
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; corrected by Geoffrey Critzer, Dec 07 2014
Without the first term, this sequence is the Moebius transform of 2^n (n>0). For n > 0, a(n) is also the number of periodic points of period n of the transform associated to the OldenburgerKolakoski sequence A000002. This transform changes a sequence of 1's and 2's by the sequence of the lengths of its runs. The OldenburgerKolakoski sequence is one of the two fixed points of this transform, the other being the same sequence without the initial term. A025142 and A025143 are the 2 periodic points of period 2. A001037(n) = a(n)/n gives the number of orbits of size n.  JeanChristophe HervĂ©, Oct 25 2014


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, McGrawHill, NY, 1968, p. 84.
BlanchetSadri, Francine. Algorithmic combinatorics on partial words. Chapman & Hall/CRC, Boca Raton, FL, 2008. ii+385 pp. ISBN: 9781420060928; 1420060929 MR2384993 (2009f:68142). See p. 164.  N. J. A. Sloane, Apr 06 2012
S. W. Golomb, ShiftRegister Sequences, HoldenDay, 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 461465, 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
John D. Cook, Counting primitive bit strings (2014)
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
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657665.
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, arXiv:1306.4891 [math.NT], 2013.
P. Pongsriiam, A remark on relative prime sets, arXiv:1306.2529 [math.NT], 2013.
P. Pongsriiam, A remark on relative prime sets, Integers 13 (2013), A49.
R. C. Read, Combinatorial problems in the theory of music, Disc. Math. 167/168 (1997) 543551, sequence A(n).


FORMULA

a(n) = sum(dn, mu(d)*2^(n/d)).
a(n) = 2*A000740(n).
a(n) = n*A001037(n).
sum(dn, a(n)) = 2^n.
a(p) = 2^p2 for p prime.  R. J. Mathar, Aug 13 2006


EXAMPLE

a(3) = 6 = { 001, 010, 011, 100, 101, 110 }.  corrected by Geoffrey Critzer, Dec 07 2014


MAPLE

with(numtheory): A027375 :=n>add( mobius(d)*2^(n/d), d in divisors(n)); # 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


STATUS

approved



