cp's OEIS Frontend

A027375 Number of aperiodic binary strings of length n; also number of binary sequences with primitive period n.

%I A027375 #187 Feb 16 2023 12:24:35
%S A027375 0,2,2,6,12,30,54,126,240,504,990,2046,4020,8190,16254,32730,65280,
%T A027375 131070,261576,524286,1047540,2097018,4192254,8388606,16772880,
%U A027375 33554400,67100670,134217216,268419060,536870910,1073708010,2147483646,4294901760
%N A027375 Number of aperiodic binary strings of length n; also number of binary sequences with primitive period n.
%C A027375 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
%C A027375 Equivalently, number of output sequences with primitive period n from a simple cycling shift register. - _Frank Ruskey_, Jan 17 2000
%C A027375 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; range corrected by _Geoffrey Critzer_, Dec 07 2014
%C A027375 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 Kolakoski sequence A000002. This transform changes a sequence of 1's and 2's by the sequence of the lengths of its runs. The Kolakoski 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. - _Jean-Christophe Hervé_, Oct 25 2014
%C A027375 From _Bernard Schott_, Jun 19 2019: (Start)
%C A027375 There are 2^n strings of length n that can be formed from the symbols 0 and 1; in the example below with a(3) = 6, the last two strings that are not aperiodic binary strings are { 000, 111 }, corresponding to 0^3 and 1^3, using the notation of the first comment.
%C A027375 Two properties mentioned by Krusemeyer et al. are:
%C A027375 1) For any n > 2, a(n) is divisible by 6.
%C A027375 2) Lim_{n->oo} a(n+1)/a(n) = 2. (End)
%D A027375 J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 13. - From _N. J. A. Sloane_, Oct 26 2012
%D A027375 E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
%D A027375 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.
%D A027375 S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967.
%D A027375 Mark I. Krusemeyer, George T. Gilbert, Loren C. Larson, A Mathematical Orchard, Problems and Solutions, MAA, 2012, Problem 128, pp. 225-227.
%H A027375 T. D. Noe, <a href="/A027375/b027375.txt">Table of n, a(n) for n = 0..300</a>
%H A027375 J.-P. Allouche, <a href="http://www.math.jussieu.fr/~allouche/bibliorecente.html">Note on the transcendence of a generating function</a>. 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.
%H A027375 B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, <a href="http://arxiv.org/abs/1212.6102">On Curling Numbers of Integer Sequences</a>, arXiv:1212.6102 [math.CO], Dec 25 2012.
%H A027375 B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Sloane/sloane3.html">On Curling Numbers of Integer Sequences</a>, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
%H A027375 John D. Cook, <a href="http://www.johndcook.com/blog/2014/12/23/counting-primitive-bit-strings/">Counting primitive bit strings</a> (2014).
%H A027375 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 85.
%H A027375 Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit and Taylor J. Smith, <a href="https://arxiv.org/abs/1602.06915">Periodicity in rectangular arrays</a>, arXiv:1602.06915 [cs.DM], 2016; Information Processing Letters 118 (2017) 58-63. See Table 1.
%H A027375 O. Georgiou, C. P. Dettmann and E. G. Altmann, <a href="http://arxiv.org/abs/1207.7000">Faster than expected escape for a class of fully chaotic maps</a>, arXiv preprint arXiv:1207.7000 [nlin.CD], 2012. - From _N. J. A. Sloane_, Dec 23 2012
%H A027375 E. N. Gilbert and J. Riordan, <a href="http://projecteuclid.org/euclid.ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.
%H A027375 David W. Lyons, Cristina Mullican, Adam Rilatt, and Jack D. Putnam, <a href="https://arxiv.org/abs/2302.05572">Werner states from diagrams</a>, arXiv:2302.05572 [quant-ph], 2023.
%H A027375 Robert M. May, <a href="https://www.researchgate.net/publication/237005499_Simple_Mathematical_Models_With_Very_Complicated_Dynamics">Simple mathematical models with very complicated dynamics</a>, Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - _N. J. A. Sloane_, Mar 17 2019
%H A027375 M. B. Nathanson, <a href="https://arxiv.org/abs/math/0608150">Primitive sets and Euler phi function for subsets of {1,2,...,n}</a>, arXiv:math/0608150 [math.NT], 2006-2007.
%H A027375 P. Pongsriiam, <a href="http://arxiv.org/abs/1306.4891">Relatively Prime Sets, Divisor Sums, and Partial Sums</a>, arXiv:1306.4891 [math.NT], 2013 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Pongsriiam/pong2.html">J. Int. Seq. 16 (2013) #13.9.1</a>.
%H A027375 P. Pongsriiam, <a href="http://arxiv.org/abs/1306.2529">A remark on relative prime sets</a>, arXiv:1306.2529 [math.NT], 2013.
%H A027375 P. Pongsriiam, <a href="http://www.emis.de/journals/INTEGERS/papers/n49/n49.Abstract.html">A remark on relative prime sets</a>, Integers 13 (2013), A49.
%H A027375 R. C. Read, <a href="http://dx.doi.org/10.1016/S0012-365X(96)00255-5">Combinatorial problems in the theory of music</a>, Disc. Math. 167/168 (1997) 543-551, sequence A(n).
%H A027375 M. Tang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Tang/tang2.html">Relatively Prime Sets and a Phi Function for Subsets of {1, 2, ... , n}</a>, J. Int. Seq. 13 (2010) # 10.7.6.
%H A027375 László Tóth, <a href="https://arxiv.org/abs/2109.06541">Menon-type identities concerning subsets of the set {1,2,...,n}</a>, arXiv:2109.06541 [math.NT], 2021.
%F A027375 a(n) = Sum_{d|n} mu(d)*2^(n/d).
%F A027375 a(n) = 2*A000740(n).
%F A027375 a(n) = n*A001037(n).
%F A027375 Sum_{d|n} a(n) = 2^n.
%F A027375 a(p) = 2^p - 2 for p prime. - _R. J. Mathar_, Aug 13 2006
%F A027375 a(n) = 2^n - O(2^(n/2)). - _Charles R Greathouse IV_, Apr 28 2016
%F A027375 a(n) = 2^n - A152061(n). - _Bernard Schott_, Jun 20 2019
%F A027375 G.f.: 2 * Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - _Ilya Gutkovskiy_, Nov 11 2019
%e A027375 a(3) = 6 = |{ 001, 010, 011, 100, 101, 110 }|. - corrected by _Geoffrey Critzer_, Dec 07 2014
%p A027375 with(numtheory): A027375 :=n->add( mobius(d)*2^(n/d), d = divisors(n)); # _N. J. A. Sloane_, Sep 25 2012
%t A027375 Table[ Apply[ Plus, MoebiusMu[ n / Divisors[n] ]*2^Divisors[n] ], {n, 1, 32} ]
%t A027375 a[0]=0; a[n_] := DivisorSum[n, MoebiusMu[n/#]*2^#&]; Array[a, 40, 0] (* _Jean-François Alcover_, Dec 01 2015 *)
%o A027375 (PARI) a(n) = sumdiv(n,d,moebius(n\d)*2^d);
%o A027375 (Haskell) a027375 n = n * a001037 n  -- _Reinhard Zumkeller_, Feb 01 2013
%o A027375 (Python)
%o A027375 from sympy import mobius, divisors
%o A027375 def a(n): return sum(mobius(d)*2**(n//d) for d in divisors(n))
%o A027375 print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jun 28 2017
%Y A027375 A038199 and A056267 are essentially the same sequence with different initial terms.
%Y A027375 Cf. A020921, A216953.
%Y A027375 Column k=2 of A143324.
%K A027375 nonn,nice,easy
%O A027375 0,2
%A A027375 _N. J. A. Sloane_