|
%I M0711 N0262 #172 Apr 15 2024 07:55:05
%S 1,1,1,1,2,3,5,9,16,28,51,93,170,315,585,1091,2048,3855,7280,13797,
%T 26214,49929,95325,182361,349520,671088,1290555,2485504,4793490,
%U 9256395,17895679,34636833,67108864,130150493,252645135,490853403,954437120,1857283155
%N Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is not allowed but the two colors can be interchanged.
%C Also 2n-bead balanced binary necklaces of fundamental period 2n that are equivalent to their complements.
%C Also binary Lyndon words of length n with an odd number of 1's (for n>=1).
%C Also number of binary irreducible polynomials of degree n having trace 1.
%C Also number of binary irreducible polynomials of degree n having linear coefficient 1 (this is the same as the trace-1 condition, as the reciprocal of an irreducible polynomial is again irreducible).
%C Also number of binary irreducible self-reciprocal polynomials of degree 2*n; there is no such polynomial for odd degree except for x+1.
%C Also number of binary vectors (x_1,...x_n) satisfying Sum_{i=1..n} i*x_i = 1 (mod n+1) = size of Varshamov-Tenengolts code VT_1(n).
%C Also the number of dynamical cycles of period 2n of a threshold Boolean automata network which is a quasi-minimal negative circuit of size nq where q is odd and which is updated in parallel. - Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Mar 03 2009
%C Also the number of 3-elements orbits of the symmetric group S3 action on irreducible polynomials of degree 2n, n>1, over GF(2). - _Jean Francis Michon_, Philippe Ravache (philippe.ravache(AT)univ-rouen.fr), Oct 04 2009
%C Conjecture: Also the number of caliber-n cycles of Zagier-reduced indefinite binary quadratic forms with sum invariant equal to s, where (s-1)/n is an odd integer. - _Barry R. Smith_, Dec 14 2014
%C The Metropolis, Stein, Stein (1973) reference on page 31 Table II lists a(k) for k = 2 to 15 and is actually for sequence A056303 since there a(k) = 0 for k<2. - _Michael Somos_, Dec 20 2014
%D B. D. Ginsburg, On a number theory function applicable in coding theory, Problemy Kibernetiki, No. 19 (1967), pp. 249-252.
%D H. Kawakami, Table of rotation sequences of x_{n+1} = x_n^2 - lambda, pp. 73-92 of G. Ikegami, Editor, Dynamical Systems and Nonlinear Oscillations, Vol. 1, World Scientific, 1986.
%D May, Robert M. "Simple mathematical models with very complicated dynamics." 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
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H G. C. Greubel, <a href="/A000048/b000048.txt">Table of n, a(n) for n = 0..3320</a> (terms 0..200 from T. D. Noe)
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p.408 and p.848.
%H L. Carlitz, <a href="http://dx.doi.org/10.1090/S0002-9939-1952-0049940-6">A theorem of Dickson on irreducible polynomials</a>, Proc. Amer. Math. Soc. 3, (1952). 693-700.
%H CombOS - Combinatorial Object Server, <a href="http://combos.org/necklace">Generate necklaces, Lyndon words, chord diagrams, and relatives</a>
%H J. Demongeot, M. Noual and S. Sene, <a href="https://hal.archives-ouvertes.fr/hal-00647877">On the number of attractors of positive and negative threshold Boolean automata circuits</a>, hal-00647877 preprint (2009). [From Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Mar 03 2009]
%H N. J. Fine, <a href="http://projecteuclid.org/euclid.ijm/1255381350">Classes of periodic sequences</a>, Illinois J. Math., 2 (1958), 285-302.
%H H. L. Fisher, <a href="/A027601/a027601.pdf">Letter to N. J. A. Sloane, Mar 16 1989</a>
%H 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 R. W. Hall and P. Klingsberg, <a href="http://www.jstor.org/stable/27642087">Asymmetric rhythms and tiling canons</a>, Amer. Math. Monthly, 113 (2006), 887-896.
%H J. E. Iglesias, <a href="https://doi.org/10.1524/zkri.1981.155.1-2.121">A formula for the number of closest packings of equal spheres having a given repeat period</a>, Z. Krist. 155 (1981) 121-127, Table 2.
%H J. E. Iglesias, <a href="https://dx.doi.org/10.1107/S0108767306003126">Enumeration of polytypes MX and MX_2 through the use of the symmetry of the Zhadanov symbol</a>, Acta Cryst. A 62 (3) (2006) 178-194, Table 1.
%H Veronika Irvine, <a href="http://hdl.handle.net/1828/7495">Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns</a>, PhD Dissertation, University of Victoria, 2016.
%H A. A. Kulkarni, N. Kiyavash and R. Sreenivas, <a href="http://www.sc.iitb.ac.in/~ankur/docs/CombinInsightDM_final.pdf">On the Varshamov-Tenengolts Construction on Binary Strings</a>, 2013.
%H R. P. Loh, A. G. Shannon, A. F. Horadam, <a href="/A000969/a000969.pdf">Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients</a>, Preprint, 1980.
%H R. M. May, <a href="http://abel.harvard.edu/archive/118r_spring_05/docs/may.pdf">Simple mathematical models with very complicated dynamics</a>, Nature, 261 (Jun 10, 1976), 459-467.
%H N. Metropolis, M. L. Stein and P. R. Stein, <a href="http://dx.doi.org/10.1016/0097-3165(73)90033-2">On finite limit sets for transformations on the unit interval</a>, J. Combin. Theory, A 15 (1973), 25-44; reprinted in P. Cvitanovic, ed., Universality in Chaos, Hilger, Bristol, 1986, pp. 187-206.
%H H. Meyn and W. Götz, <a href="http://www.mat.univie.ac.at/~slc/opapers/s21meyn.html">Self-reciprocal polynomials over finite fields</a>, Séminaire Lotharingien de Combinatoire, B21d (1989), 8 pp.
%H Simon Michalowsky, Bahman Gharesifard, Christian Ebenbauer, <a href="https://arxiv.org/abs/1711.05486">A Lie bracket approximation approach to distributed optimization over directed graphs</a>, arXiv:1711.05486 [math.OC], 2017.
%H R. Pries and C. Weir, <a href="http://arxiv.org/abs/1302.6261">The Ekedahl-Oort type of Jacobians of Hermitian curves</a>, arXiv preprint arXiv:1302.6261 [math.NT], 2013.
%H F. Ruskey, <a href="http://combos.org/TSlyndon">Number of q-ary Lyndon words with given trace mod q</a>
%H F. Ruskey, <a href="http://combos.org/TlyndonFk">Number of Lyndon words over GF(q) with given trace</a>
%H N. J. A. Sloane, <a href="http://arxiv.org/abs/math/0207197">On single-deletion-correcting codes</a>, arXiv:math/0207197 [math.CO], 2002; in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.
%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/dijen.txt">On single-deletion-correcting codes</a>
%H B. R. Smith, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Smith/smith5.html"> Reducing quadratic forms by kneading sequences</a>, Journal of Integer Sequences, 17 (2014), article 14.11.8.
%H P. R. Stein, <a href="/A000048/a000048.pdf">Letter to N. J. A. Sloane, Jun 02 1971</a>
%H J.-Y. Thibon, <a href="https://arxiv.org/abs/math/0102051">The cycle enumerator of unimodal permutations</a>, arXiv:math/0102051 [math.CO], 2001.
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>
%H <a href="/index/Su#subsetsums">Index entries for sequences related to subset sums modulo m</a>
%F a(n) = (1/(2*n)) * Sum_{odd d divides n} mu(d)*2^(n/d), where mu is the Mobius function A008683.
%F a(n) = A056303(n) for all integer n>=2. - _Michael Somos_, Dec 20 2014
%F Sum_{k dividing m for which m/k is odd} k*a(k) = 2^(m-1). (This explains the observation that the sequence is very close to A006788. Unless m has some nontrivial odd divisors that are small relative to m, the term m*a(m) will dominate the sum. Thus, we see for instance that a(n) = A006788(n) when n has one of the forms 2^m or 2^m*p where p is an odd prime with a(2^m) < p.) - _Barry R. Smith_, Oct 24 2015
%F A000013(n) = Sum_{d|n} a(d). - _Robert A. Russell_, Jun 09 2019
%F G.f.: 1 + Sum_{k>=1} mu(2*k)*log(1 - 2*x^k)/(2*k). - _Ilya Gutkovskiy_, Nov 11 2019
%e a(5) = 3 corresponding to the necklaces 00001, 00111, 01011.
%e a(6) = 5 from 000001, 000011, 000101, 000111, 001011.
%p with(numtheory); A000048 := proc(n) local d,t1; if n = 0 then RETURN(1) else t1 := 0; for d from 1 to n do if n mod d = 0 and d mod 2 = 1 then t1 := t1+mobius(d)*2^(n/d)/(2*n); fi; od; RETURN(t1); fi; end;
%t a[n_] := Total[ MoebiusMu[#]*2^(n/#)& /@ Select[ Divisors[n], OddQ]]/(2n); a[0] = 1; Table[a[n], {n,0,35}] (* _Jean-François Alcover_, Jul 21 2011 *)
%t a[ n_] := If[ n < 1, Boole[n == 0], DivisorSum[ n, MoebiusMu[#] 2^(n/#) &, OddQ] / (2 n)]; (* _Michael Somos_, Dec 20 2014 *)
%o (PARI) A000048(n) = sumdiv(n,d,(d%2)*(moebius(d)*2^(n/d)))/(2*n) \\ _Michael B. Porter_, Nov 09 2009
%o (PARI) L(n, k) = sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d, k/d) );
%o a(n) = sum(k=0, n, if( (n+k)%2==1, L(n, k), 0 ) ) / n;
%o vector(55,n,a(n)) \\ _Joerg Arndt_, Jun 28 2012
%o (Python)
%o from sympy import divisors, mobius
%o def a(n): return 1 if n<1 else sum(mobius(d)*2**(n//d) for d in divisors(n) if d%2)//(2*n) # _Indranil Ghosh_, Apr 28 2017
%Y Like A000013, but primitive necklaces. Half of A064355.
%Y Equals A042981 + A042982.
%Y Cf. A002823, A000016, A053633, A051841, A001037, A002075, A002076, A008683.
%Y Cf. also A001037, A056303.
%Y Very close to A006788 [Fisher, 1989].
%K nonn,core,easy,nice,changed
%O 0,5
%A _N. J. A. Sloane_
%E Additional comments from _Frank Ruskey_, Dec 13 1999
|
