Displaying 1-10 of 68 results found.
Number of binary words whose (unique) decreasing Lyndon decomposition is into Lyndon words each with an odd number of 1's; EULER transform of A000048.
+20
5
1, 1, 2, 3, 6, 10, 19, 34, 65, 120, 229, 432, 829, 1583, 3051, 5874, 11370, 22012, 42756, 83113, 161917, 315723, 616588, 1205232, 2358604, 4619485, 9055960, 17766086, 34880215, 68524486, 134707150, 264960828, 521449025
FORMULA
Prod_{n>=1} 1/(1-q^n)^ A000048(n) = 1 + sum_{n>=1} a(n) q^n. G.f. A(x) satisfies: A(x)^2 = A(x^2) / (1 - 2*x). - Paul D. Hanna, Apr 17 2016 a(n) ~ c * 2^n / sqrt(n), where c = 0.3412831644583761326654... . - Vaclav Kotesovec, Apr 18 2016 G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = v^2 * (v^2 - 2*u^2*v - u^4) + 2*w*u^4. - Michael Somos, Jun 27 2017
EXAMPLE
The binary words 1111, 1101, 1001, 0101, 0111, 0001 of length 4 decompose as 1*1*1*1, 1*1*01, 1*001, 01*01, 0111, 0001 and each subword has an odd number of 1's, therefore a(4)=6.
G.f. A(x) = x + x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 10*x^6 + 19*x^7 + 34*x^8 + ... such that A(x)^2 * (1 - 2*x) = A(x^2).
PROG
(PARI) /* G.f. A(x) satisfies: A(x)^2 = A(x^2)/(1 - 2*x) */
{a(n) = my(A=x); for(i=1, n, A = sqrt( subst(A, x, x^2)/(1 - 2*x +x*O(x^n)))); polcoeff(A, n)}
(PARI) /* As the EULER transform of A000048 */ {a(n) = polcoeff( prod(k=1, n, 1/(1 - x^k +x*O(x^n))^ A000048(k)), n-1)}
0, 0, 1, 0, 1, 1, 1, 0, 2, 1, 1, 2, 1, 1, 5, 0, 1, 6, 1, 2, 11, 1, 1, 16, 4, 1, 30, 2, 1, 57, 1, 0, 95, 1, 13, 172, 1, 1, 317, 16, 1, 591, 1, 2, 1124, 1, 1, 2048, 10, 52, 3857, 2, 1, 7286, 97, 16, 13799, 1, 1, 26386, 1, 1, 49968, 0, 319, 95331, 1, 2, 182363
MAPLE
f := proc(n) local d, sum1; sum1 := 0; for d from 1 to n do if d mod 2 = 1 and n mod d = 0 then sum1 := sum1+(phi(d)-mobius(d))*2^(n/d); fi; od; sum1/(2*n); end;
MATHEMATICA
Table[DivisorSum[n, Mod[#, 2] EulerPhi[#]*2^(n/#)/(2 n) &] - DivisorSum[n, Total[MoebiusMu[#]*2^(n/#)]/(2 n) &, OddQ], {n, 69}] (* Michael De Vlieger, Mar 26 2022 *)
1, 0, 0, 2, 0, 2, 4, 2, 0, 8, 4, 2, 16, 2, 4, 38, 0, 2, 64, 2, 16, 134, 4, 2, 256, 32, 4, 512, 16, 2, 1084, 2, 0, 2054, 4, 158, 4096, 2, 4, 8198, 256, 2, 16444, 2, 16, 33272, 4, 2, 65536, 128, 1024, 131078, 16, 2, 262144, 2078, 256, 524294, 4, 2, 1052656, 2, 4, 2097656, 0, 8222, 4194364, 2, 16, 8388614, 17404, 2, 16777216, 2, 4, 33587168, 16, 2174, 67108924
COMMENTS
a(n) = total length of all cycles (see A000048) which are strictly less than the full length of 2n.
REFERENCES
R. K. Guy, Posting to Sequence Fans Mailing List, Apr 20 2012
MAPLE
with (numtheory):
a:= n-> 2^n -add (mobius(d)*2^(n/d), d=select(x->is(x, odd), divisors(n))):
MATHEMATICA
a[n_] := 2^n - DivisorSum[n, Mod[#, 2]*MoebiusMu[#]*2^(n/#)&]; a[0] = 1;
Inverse Moebius transform of A000048 (starting at term 0).
+20
0
1, 2, 2, 3, 3, 6, 6, 12, 18, 32, 52, 100, 171, 322, 589, 1103, 2049, 3877, 7281, 13830, 26221, 49982, 95326, 182470, 349523, 671260, 1290573, 2485827, 4793491, 9257016, 17895680, 34637936, 67108917, 130152543, 252645143, 490857374
Moebius transform of A000048 (starting at term 0).
+20
0
1, 0, 0, 0, 1, 2, 4, 8, 15, 26, 50, 90, 169, 310, 583, 1082, 2047, 3837, 7279, 13769, 26209, 49878, 95324, 182260, 349518, 670918, 1290539, 2485189, 4793489, 9255782, 17895678, 34635742, 67108813, 130148445, 252645129, 490849458
1, 2, 4, 8, 17, 39, 95, 241, 629, 1676, 4533, 12392, 34145, 94670, 263853, 738744, 2076817, 5860033, 16589996, 47108718, 134136047, 382889797, 1095452434, 3140672834, 9021699845, 25961239919, 74829970930, 216016298741, 624469525203
FORMULA
G.f.: (1/(1 - x)) * (1 + Sum_{k>=1} mu(2*k)*log(1 - 2*(x/(1 - x))^k)/(2*k)). - Ilya Gutkovskiy, Nov 12 2019
1, 2, 3, 4, 6, 9, 14, 23, 39, 67, 118, 211, 381, 696, 1281, 2372, 4420, 8275, 15555, 29352, 55566, 105495, 200820, 383181, 732701, 1403789, 2694344, 5179848, 9973338, 19229733, 37125412, 71762245, 138871109, 269021602, 521666737
COMMENTS
Partial sums of 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. Partial sums of 2n-bead balanced binary necklaces of fundamental period 2n that are equivalent to their complements. Partial sums of binary Lyndon words of length n with an odd number of 1's. Partial sums of number of binary Lyndon words with trace 1 over GF(2). Partial sums of number of binary irreducible polynomials of degree n having trace 1. For more equivalences see A000048. The subsequence of primes in this partial sum begins: 2, 3, 23, 67, 211, 1403789.
EXAMPLE
a(35) = 1 + 1 + 1 + 1 + 2 + 3 + 5 + 9 + 16 + 28 + 51 + 93 + 170 + 315 + 585 + 1091 + 2048 + 3855 + 7280 + 13797 + 26214 + 49929 + 95325 + 182361 + 349520 + 671088 + 1290555 + 2485504 + 4793490 + 9256395 + 17895679 + 34636833 + 67108864 + 130150493 + 252645135 + 490853403.
Number of degree-n irreducible polynomials over GF(2); number of n-bead necklaces with beads of 2 colors when turning over is not allowed and with primitive period n; number of binary Lyndon words of length n.
(Formerly M0116 N0046 N0287)
+10
229
1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182, 4080, 7710, 14532, 27594, 52377, 99858, 190557, 364722, 698870, 1342176, 2580795, 4971008, 9586395, 18512790, 35790267, 69273666, 134215680, 260300986, 505286415, 981706806, 1908866960, 3714566310, 7233615333, 14096302710, 27487764474
COMMENTS
Also dimensions of free Lie algebras - see A059966, which is essentially the same sequence. This sequence also represents the number N of cycles of length L in a digraph under x^2 seen modulo a Mersenne prime M_q=2^q-1. This number does not depend on q and L is any divisor of q-1. See Theorem 5 and Corollary 3 of the Shallit and Vasiga paper: N=sum(eulerphi(d)/order(d,2)) where d is a divisor of 2^(q-1)-1 such that order(d,2)=L. - Tony Reix, Nov 17 2005 Except for a(0) = 1, Bau-Sen Du's [1985/2007] Table 1, p. 6, has this sequence as the 7th (rightmost) column. Other columns of the table include (but are not identified as) A006206- A006208. - Jonathan Vos Post, Jun 18 2007 "Number of binary Lyndon words" means: number of binary strings inequivalent modulo rotation (cyclic permutation) of the digits and not having a period smaller than n. This provides a link to A103314, since these strings correspond to the inequivalent zero-sum subsets of U_m (m-th roots of unity) obtained by taking the union of U_n (n|m) with 0 or more U_d (n | d, d | m) multiplied by some power of exp(i 2Pi/n) to make them mutually disjoint. (But not all zero-sum subsets of U_m are of that form.) - M. F. Hasler, Jan 14 2007 Also the number of dynamical cycles of period n of a threshold Boolean automata network which is a quasi-minimal positive circuit of size a multiple of n and which is updated in parallel. - Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Feb 25 2009
Also, the number of periodic points with (minimal) period n in the iteration of the tent map f(x):=2min{x,1-x} on the unit interval. - Pietro Majer, Sep 22 2009 Number of distinct cycles of minimal period n in a shift dynamical system associated with a totally disconnected hyperbolic iterated function system (see Barnsley link). - Michel Marcus, Oct 06 2013 For n > 0, a(n) is also the number of orbits of size n of the transform associated to the Kolakoski sequence A000002 (and this is true for any map with 2^n periodic points of period n). The Kolakoski 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 periodic points of the orbit of size 2. A027375(n) = n*a(n) gives the number of periodic points of minimal period n. For n > 1, this sequence is equal to A059966 and to A060477, and for n = 1, a(1) = A059966(1)+1 = A060477(1)-1; this because the n-th term of all 3 sequences is equal to (1/n)*sum_{d|n} mu(n/d)*(2^d+e), with e = -1/0/1 for resp. A059966/this sequence/ A060477, and sum_{d|n} mu(n/d) equals 1 for n = 1 and 0 for all n > 1. (End) Warning: A000031 and A001037 are easily confused, since they have similar formulas. Following Kam Cheong Au (2020), let d(w,N) be the dimension of the Q-span of weight w and level N of colored multiple zeta values (CMZV). Here Q are the rational numbers.
Deligne's bound says that d(w,N) <= D(w,N), where 1 + Sum_{w >= 1} D(w,N)*t^w = (1 - a*t + b*t^2)^(-1) when N >= 3, where a = phi(N)/2 + omega(N) and b = omega(N) - 1 (with omega(N) = A001221(N) being the number of distinct primes of N). For N = 3, a = phi(3)/2 + omega(3) = 2/2 + 1 = 2 and b = omega(3) - 1 = 0. It follows that D(w, N=3) = A000079(w) = 2^w. For some reason, Kam Cheong Au (2020) assumes Deligne's bound is tight, i.e., d(w,N) = D(w,N). He sets Sum_{w >= 1} c(w,N)*t^w = log(1 + Sum_{w >= 1} d(w,N)*t^w) = log(1 + Sum_{w >= 1} D(w,N)*t^w) = -log(1 - a*t + b*t^2) for N >= 3.
For N = 3, we get that c(w, N=3) = A000079(w)/w = 2^w/w. He defines d*(w,N) = Sum_{k | w} (mu(k)/k)*c(w/k,N) to be the "number of primitive constants of weight w and level N". (Using the terminology of A113788, we may perhaps call d*(w,N) the number of irreducible colored multiple zeta values at weight w and level N.) Using standard techniques of the theory of g.f.'s, we can prove that Sum_{w >= 1} d*(w,N)*t^w = Sum_{s >= 1} (mu(s)/s) Sum_{k >= 1} c(k,N)*(t^s)^k = -Sum_{s >= 1} (mu(s)/s)*log(1 - a*t^s + b*t^(2*s)).
For N = 3, we saw that a = 2 and b = 0, and hence d*(w, N=3) = a(w) = Sum_{k | w} (mu(k)/k) * 2^(w/k) / (w/k) = (1/w) * Sum_{k | w} mu(k) * 2^(w/k) for w >= 1. See Table 1 on p. 6 in Kam Cheong Au (2020). (End)
REFERENCES
Michael F. Barnsley, Fractals Everywhere, Academic Press, San Diego, 1988, page 171, Lemma 3.
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie. On the digraph defined by squaring mod m, when m has primitive roots. Congr. Numer. 82 (1991), 167-177.
P. J. Freyd and A. Scedrov, Categories, Allegories, North-Holland, Amsterdam, 1990. See 1.925.
M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983, pp. 65, 79.
Robert M. May, "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 Guy Melançon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
M. R. Nester, (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2] N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence in entries N0046 and N0287).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Émilie Charlier, Manon Philibert, and Manon Stipulanti, Nyldon words, arXiv:1804.09735 [math.CO], 2018. Also J. Comb. Thy. A, 167 (2019), 60-90.
FORMULA
For n >= 1:
a(n) = (1/n)*Sum_{d | n} mu(n/d)*2^d.
2^n = Sum_{d | n} d*a(d).
G.f.: 1 - Sum_{n >= 1} moebius(n)*log(1 - 2*x^n)/n, where moebius(n) = A008683(n). - Paul D. Hanna, Oct 13 2010 For n >= 1:
a(n) = (1/n)*Sum_{k=1..n} mu(gcd(n,k))*2^(n/gcd(n,k))/phi(n/gcd(n,k)).
a(n) = (1/n)*Sum_{k=1..n} mu(n/gcd(n,k))*2^gcd(n,k)/phi(n/gcd(n,k)). (End)
EXAMPLE
Binary strings (Lyndon words, cf. A102659): a(0) = 1 = #{ "" },
a(1) = 2 = #{ "0", "1" },
a(2) = 1 = #{ "01" },
a(3) = 2 = #{ "001", "011" },
a(4) = 3 = #{ "0001", "0011", "0111" },
a(5) = 6 = #{ "00001", "00011", "00101", "00111", "01011", "01111" }.
MAPLE
with(numtheory): A001037 := proc(n) local a, d; if n = 0 then RETURN(1); else a := 0: for d in divisors(n) do a := a+mobius(n/d)*2^d; od: RETURN(a/n); fi; end;
MATHEMATICA
f[n_] := Block[{d = Divisors@ n}, Plus @@ (MoebiusMu[n/d]*2^d/n)]; Array[f, 32]
PROG
(PARI) A001037(n)=if(n>1, sumdiv(n, d, moebius(d)*2^(n/d))/n, n+1) \\ Edited by M. F. Hasler, Jan 11 2016 (PARI) {a(n)=polcoeff(1-sum(k=1, n, moebius(k)/k*log(1-2*x^k+x*O(x^n))), n)} \\ Paul D. Hanna, Oct 13 2010 (PARI) a(n)=if(n>1, my(s); forstep(i=2^n+1, 2^(n+1), 2, s+=polisirreducible(Mod(1, 2) * Pol(binary(i)))); s, n+1) \\ Charles R Greathouse IV, Jan 26 2012 (Haskell)
a001037 0 = 1
a001037 n = (sum $ map (\d -> (a000079 d) * a008683 (n `div` d)) $
a027750_row n) `div` n
(Python)
from sympy import divisors, mobius
def a(n): return sum(mobius(d) * 2**(n//d) for d in divisors(n))/n if n>1 else n + 1 # Indranil Ghosh, Apr 26 2017
CROSSREFS
Row sums of A051168, which gives the number of Lyndon words with fixed number of zeros and ones. Irreducible over GF(2), GF(3), GF(4), GF(5), GF(7): A058943, A058944, A058948, A058945, A058946. Primitive irreducible over GF(2), GF(3), GF(4), GF(5), GF(7): A058947, A058949, A058952, A058950, A058951. See also A102659 for the list of binary Lyndon words themselves.
Number of n-bead necklaces with 2 colors when turning over is not allowed; also number of output sequences from a simple n-stage cycling shift register; also number of binary irreducible polynomials whose degree divides n.
(Formerly M0564 N0203)
+10
161
1, 2, 3, 4, 6, 8, 14, 20, 36, 60, 108, 188, 352, 632, 1182, 2192, 4116, 7712, 14602, 27596, 52488, 99880, 190746, 364724, 699252, 1342184, 2581428, 4971068, 9587580, 18512792, 35792568, 69273668, 134219796, 260301176, 505294128, 981706832
COMMENTS
Also a(n)-1 is the number of 1's in the truth table for the lexicographically least de Bruijn cycle (Fredricksen).
In music, a(n) is the number of distinct classes of scales and chords in an n-note equal-tempered tuning system. - Paul Cantrell, Dec 28 2011 Also, minimum cardinality of an unavoidable set of length-n binary words (Champarnaud, Hansel, Perrin). - Jeffrey Shallit, Jan 10 2019 a(n) is even for n != 0, 2. Proof: write n = 2^e * s with odd s, then a(n) * s = Sum_{d|s} Sum_{k=0..e} phi((2^e*s)/(2^k*d)) * 2^(2^k*d-e) = Sum_{d|s} Sum_{k=0..e-1} phi(s/d) * 2^(2^k*d-k-1) + Sum_{d|s} phi(s/d) * 2^(2^e*d-e) == Sum_{k=0..e-1} 2^(2^k*s-k-1) + 2^(2^e*s-e) == Sum_{k=0..min{e-1,1}} 2^(2^k*s-k-1) (mod 2). a(n) is odd if and only if s = 1 and e-1 = 0, or n = 2.
a(n) == 2 (mod 4) if and only if n = 1, 4 or n = 2*p^e with prime p == 3 (mod 4).
a(n) == 4 (mod 8) if and only if n = 2^e, 3*2^e for e >= 3, or n = p^e, 4*p^e != 12 with prime p == 3 (mod 4), or n = 2s where s is an odd number such that phi(s) == 4 (mod 8). (End)
REFERENCES
S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, pp. 120, 172.
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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).
LINKS
N. J. A. Sloane, On single-deletion-correcting codes, 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. David Thomson, Musical Polygons, Mathematics Today, Vol. 57, No. 2 (April 2021), pp. 50-51. Eric Weisstein's World of Mathematics, Necklace
FORMULA
a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n/d) = A053635(n)/n, where phi is A000010. Warning: easily confused with A001037, which has a similar formula. a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 2^gcd(n,k). - Ilya Gutkovskiy, Apr 16 2021 a(0) = 1; a(n) = (1/n)*Sum_{k=1..n} 2^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 06 2021 Dirichlet g.f.: f(s+1) * (zeta(s)/zeta(s+1)), where f(s) = Sum_{n>=1} 2^n/n^s. - Jianing Song, Nov 13 2021
EXAMPLE
For n=3 and n=4 the necklaces are {000,001,011,111} and {0000,0001,0011,0101,0111,1111}.
The analogous shift register sequences are {000..., 001001..., 011011..., 111...} and {000..., 00010001..., 00110011..., 0101..., 01110111..., 111...}.
MAPLE
with(numtheory); A000031 := proc(n) local d, s; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+phi(d)*2^(n/d); od; RETURN(s/n); fi; end; [ seq( A000031(n), n=0..50) ];
MATHEMATICA
a[n_] := Sum[If[Mod[n, d] == 0, EulerPhi[d] 2^(n/d), 0], {d, 1, n}]/n
a[n_] := Fold[#1 + 2^(n/#2) EulerPhi[#2] &, 0, Divisors[n]]/n (* Ben Branman, Jan 08 2011 *) Table[Expand[CycleIndex[CyclicGroup[n], t] /. Table[t[i]-> 2, {i, 1, n}]], {n, 0, 30}] (* Geoffrey Critzer, Mar 06 2011*) a[0] = 1; a[n_] := DivisorSum[n, EulerPhi[#]*2^(n/#)&]/n; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 03 2016 *) mx=40; CoefficientList[Series[1-Sum[EulerPhi[i] Log[1-2*x^i]/i, {i, 1, mx}], {x, 0, mx}], x] (* Herbert Kociemba, Oct 29 2016 *)
PROG
(Haskell)
a000031 0 = 1
a000031 n = (`div` n) $ sum $
zipWith (*) (map a000010 divs) (map a000079 $ reverse divs)
where divs = a027750_row n
(Python)
from sympy import totient, divisors
def A000031(n): return sum(totient(d)*(1<<n//d) for d in divisors(n, generator=True))//n if n else 1 # Chai Wah Wu, Nov 16 2022
CROSSREFS
A008965(n) = a(n) - 1 allowing different offsets.
EXTENSIONS
There is an error in Fig. M3860 in the 1995 Encyclopedia of Integer Sequences: in the third line, the formula for A000031 = M0564 should be (1/n) sum phi(d) 2^(n/d).
Number of aperiodic binary strings of length n; also number of binary sequences with primitive period n.
+10
85
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
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; range 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 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 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.
Two properties mentioned by Krusemeyer et al. are:
1) For any n > 2, a(n) is divisible by 6.
2) Lim_{n->oo} a(n+1)/a(n) = 2. (End)
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.
S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967.
Mark I. Krusemeyer, George T. Gilbert, Loren C. Larson, A Mathematical Orchard, Problems and Solutions, MAA, 2012, Problem 128, pp. 225-227.
LINKS
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. Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit and Taylor J. Smith, Periodicity in rectangular arrays, arXiv:1602.06915 [cs.DM], 2016; Information Processing Letters 118 (2017) 58-63. See Table 1. Robert M. May, 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
FORMULA
a(n) = Sum_{d|n} mu(d)*2^(n/d).
Sum_{d|n} a(n) = 2^n.
EXAMPLE
a(3) = 6 = |{ 001, 010, 011, 100, 101, 110 }|. - corrected by Geoffrey Critzer, Dec 07 2014
MATHEMATICA
Table[ Apply[ Plus, MoebiusMu[ n / Divisors[n] ]*2^Divisors[n] ], {n, 1, 32} ]
a[0]=0; a[n_] := DivisorSum[n, MoebiusMu[n/#]*2^#&]; Array[a, 40, 0] (* Jean-François Alcover, Dec 01 2015 *)
PROG
(PARI) a(n) = sumdiv(n, d, moebius(n\d)*2^d);
(Python)
from sympy import mobius, divisors
def a(n): return sum(mobius(d)*2**(n//d) for d in divisors(n))
CROSSREFS
A038199 and A056267 are essentially the same sequence with different initial terms.
Search completed in 0.116 seconds
| 