A296302 -id:A296302 - cp's OEIS frontend

A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

1, 1, 3, 6, 15, 27, 63, 120, 252, 495, 1023, 2010, 4095, 8127, 16365, 32640, 65535, 130788, 262143, 523770, 1048509, 2096127, 4194303, 8386440, 16777200, 33550335, 67108608, 134209530, 268435455, 536854005, 1073741823, 2147450880

Offset: 1

N. J. A. Sloane

Also number of compositions of n into relatively prime parts (that is, the gcd of all the parts is 1). Also number of subsets of {1,2,..,n} containing n and consisting of relatively prime numbers. - Vladeta Jovovic, Aug 13 2003
Also number of perfect parity patterns that have exactly n columns (see A118141). - Don Knuth, May 11 2006
a(n) is odd if and only if n is squarefree (Tim Keller). - Emeric Deutsch, Apr 27 2007
a(n) is a multiple of 3 for all n>=3 (see Problem 11161 link). - Emeric Deutsch, Aug 13 2008
Row sums of triangle A143424. - Gary W. Adamson, Aug 14 2008
a(n) is the number of monic irreducible polynomials with nonzero constant coefficient in GF(2)[x] of degree n. - Michel Marcus, Oct 30 2016
a(n) is the number of aperiodic compositions of n, the number of compositions of n with relatively prime parts, and the number of compositions of n with relatively prime run-lengths. - Gus Wiseman, Dec 21 2017

			For n=4, there are 6 compositions of n into coprime parts: <3,1>, <2,1,1>, <1,3>, <1,2,1>, <1,1,2>, and <1,1,1,1>.
From _Gus Wiseman_, Dec 19 2017: (Start)
The a(6) = 27 aperiodic compositions are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1221), (1311), (2112), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
The a(6) = 27 compositions into relatively prime parts are:
  (111111),
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1212), (1221), (1311), (2112), (2121), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (51).
The a(6) = 27 compositions with relatively prime run-lengths are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1131), (1212), (1221), (1311), (2112), (2121), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
(End)

H. O. Peitgen and P. H. Richter, The Beauty of Fractals, Springer-Verlag; contribution by A. Douady, p. 165.
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).

Seiichi Manyama, Table of n, a(n) for n = 1..3322 (terms 1..300 from T. D. Noe)
Hunki Baek, Sejeong Bang, Dongseok Kim, and Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014. See Table 2.
Donald Knuth, Robin Chapman and Reiner Martin, Problem 11243, Perfect Parity Patterns, Am. Math. Monthly 115 (7) (2008) p 668, function c(n).
Emeric Deutsch and Lafayette College Problem Group, Problem 11161: Compositions without Common Factors, American Mathematical Monthly, vol. 114, No. 4, 2007, p. 363.
H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.
J. E. Iglesias, A formula for the number of closest packings of equal spheres having a given repeat period, Z. Krist. 155 (1981) 121-127, Table 2.
Wolfdieter Lang, Cantor's List of Real Algebraic Numbers of Heights 1 to 7, arXiv:2307.10645 [math.NT], 2023.
Nicolae Mihalache and Francois Vigneron, Factorization of the quadratic Misiurewicz-Thurston polynomials, arXiv:2506.17662 [math.DS], 2025. See p. 8.
Robert Munafo, Enumeration of Period-N Mu-Atoms
Jeffrey Shallit and N. J. A. Sloane, Correspondence 1974-1975
François Vigneron and Nicolae Mihalache, How to split a tera-polynomial, arXiv:2402.06083 [math.NA], 2024.
Index entries for sequences related to Lyndon words

Cf. A000837, A003239, A008683, A008965, A022553, A034738, A035928, A038199, A051168, A054525, A056267, A059966, A143424, A167606, A178472, A216954, A228369, A294859, A296302.
Equals A027375/2.
See A056278 for a variant.
First differences of A085945.
Column k=2 of A143325.
Row sums of A101391.

with(numtheory): a[1]:=1: a[2]:=1: for n from 3 to 32 do div:=divisors(n): a[n]:=2^(n-1)-sum(a[n/div[j]],j=2..tau(n)) od: seq(a[n],n=1..32); # Emeric Deutsch, Apr 27 2007
with(numtheory); A000740:=n-> add(mobius(n/d)*2^(d-1), d in divisors(n)); # N. J. A. Sloane, Oct 18 2012

a[n_] := Sum[ MoebiusMu[n/d]*2^(d - 1), {d, Divisors[n]}]; Table[a[n], {n, 1, 32}] (* Jean-François Alcover, Feb 03 2012, after PARI *)

a(n) = sumdiv(n,d,moebius(n/d)*2^(d-1))

from sympy import mobius, divisors
def a(n): return sum([mobius(n // d) * 2**(d - 1) for d in divisors(n)])
[a(n) for n in range(1, 101)]  # Indranil Ghosh, Jun 28 2017

a(n) = Sum_{d|n} mu(n/d)*2^(d-1), Mobius transform of A011782. Furthermore, Sum_{d|n} a(d) = 2^(n-1).
a(n) = A027375(n)/2 = A038199(n)/2.
a(n) = Sum_{k=0..n} A051168(n,k)*k. - Max Alekseyev, Apr 09 2013
Recurrence relation: a(n) = 2^(n-1) - Sum_{d|n,d>1} a(n/d). (Lafayette College Problem Group; see the Maple program and Iglesias eq (6)). - Emeric Deutsch, Apr 27 2007
G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - Ilya Gutkovskiy, Oct 24 2018
G.f. satisfies Sum_{n>=1} A( (x/(1 + 2*x))^n ) = x. - Paul D. Hanna, Apr 02 2025

Connection with Mandelbrot set discovered by Warren D. Smith and proved by Robert Munafo, Feb 06 2000

Ambiguous term a(0) removed by Max Alekseyev, Jan 02 2012

A059966 a(n) = (1/n) * Sum_{ d divides n } mu(n/d) * (2^d - 1).

Original entry on oeis.org

1, 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

Offset: 1

Roland Bacher, Mar 05 2001

Dimensions of the homogeneous parts of the free Lie algebra with one generator in 1,2,3, etc. (Lie analog of the partition numbers).
This sequence is the Lie analog of the partition sequence (which gives the dimensions of the homogeneous polynomials with one generator in each degree) or similarly, of the partitions into distinct (or odd numbers) (which gives the dimensions of the homogeneous parts of the exterior algebra with one generator in each dimension).
The number of cycles of length n of rectangle shapes in the process of repeatedly cutting a square off the end of the rectangle. For example, the one cycle of length 1 is the golden rectangle. - David Pasino (davepasino(AT)yahoo.com), Jan 29 2009
In music, the number of distinct rhythms, at a given tempo, produced by a continuous repetition of measures with identical patterns of 1's and 0's (where 0 means no beat, and 1 means one beat), where each measure allows for n possible beats of uniform character, and when counted under these two conditions: (i) the starting and ending times for the measure are unknown or irrelevant and (ii) identical rhythms that can be produced by using a measure with fewer than n possible beats are excluded from the count. - Richard R. Forberg, Apr 22 2013
Richard R. Forberg's comment does not hold for n=1 because a(1)=1 but there are the two possible rhythms: "0" and "1". - Herbert Kociemba, Oct 24 2016
The comment does hold for n=1 as the rhythm "0" can be produced by using a measure of 0 beats and so is properly excluded from a(1)=1 by condition (ii) of the comment. - Travis Scott, May 28 2022
a(n) is also the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n. - Gus Wiseman, Dec 19 2017
Mobius transform of A008965. - Jianing Song, Nov 13 2021
a(n) is the number of cycles of length n for the map x->1 - abs(2*x-1) applied on rationals 0Michel Marcus, Jul 16 2025

			a(4)=3: the 3 elements [a,c], [a[a,b]] and d form a basis of all homogeneous elements of degree 4 in the free Lie algebra with generators a of degree 1, b of degree 2, c of degree 3 and d of degree 4.
From _Gus Wiseman_, Dec 19 2017: (Start)
The sequence of Lyndon compositions organized by sum begins:
  (1),
  (2),
  (3),(12),
  (4),(13),(112),
  (5),(14),(23),(113),(122),(1112),
  (6),(15),(24),(114),(132),(123),(1113),(1122),(11112),
  (7),(16),(25),(115),(34),(142),(124),(1114),(133),(223),(1213),(1132),(1123),(11113),(1222),(11212),(11122),(111112). (End)

C. Reutenauer, Free Lie algebras, Clarendon press, Oxford (1993).

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, When are Hopf algebras determined by integer sequences?, arXiv:2505.06941 [math.CO], 2025. See p. 17.
S. V. Duzhin and D. V. Pasechnik, Groups acting on necklaces and sandpile groups, Journal of Mathematical Sciences, August 2014, Volume 200, Issue 6, pp 690-697. See page 85. - N. J. A. Sloane, Jun 30 2014
Seok-Jin Kang and Myung-Hwan Kim, Free Lie Algebras, Generalized Witt Formula and the Denominator Identity, Journal of Algebra 183, 560-594 (1996).
Michael J. Mossinghoff and Timothy S. Trudgian, A tale of two omegas, arXiv:1906.02847 [math.NT], 2019.
G. Niklasch, Some number theoretical constants: 1000-digit values [Cached copy]
Jakob Oesinghaus, Quasi-symmetric functions and the Chow ring of the stack of expanded pairs, arXiv:1806.10700 [math.AG], 2018.
Robert Schneider, Andrew V. Sills, and Hunter Waldron, On the q-factorization of power series, arXiv:2501.18744 [math.CO], 2025. See p. 6.

Apart from initial terms, same as A001037.

Cf. A000225, A000740, A008683, A008965, A011782, A060223, A185700, A228369, A269134 A281013, A296302, A296373.

a059966 n = sum (map (\x -> a008683 (n `div` x) * a000225 x)
                     [d | d <- [1..n], mod n d == 0]) `div` n
-- Reinhard Zumkeller, Nov 18 2011

Table[1/n Apply[Plus, Map[(MoebiusMu[n/# ](2^# - 1)) &, Divisors[n]]], {n, 20}]
(* Second program: *)
Table[(1/n) DivisorSum[n, MoebiusMu[n/#] (2^# - 1) &], {n, 35}] (* Michael De Vlieger, Jul 22 2019 *)

from sympy import mobius, divisors
def A059966(n): return sum(mobius(n//d)*(2**d-1) for d in divisors(n,generator=True))//n # Chai Wah Wu, Feb 03 2022

G.f.: Product_{n>0} (1-q^n)^a(n) = 1-q-q^2-q^3-q^4-... = 2-1/(1-q).
Inverse Euler transform of A011782. - Alois P. Heinz, Jun 23 2018
G.f.: Sum_{k>=1} mu(k)*log((1 - x^k)/(1 - 2*x^k))/k. - Ilya Gutkovskiy, May 19 2019
a(n) ~ 2^n / n. - Vaclav Kotesovec, Aug 10 2019
Dirichlet g.f.: f(s+1)/zeta(s+1) - 1, where f(s) = Sum_{n>=1} 2^n/n^s. - Jianing Song, Nov 13 2021

Explicit formula from Paul D. Hanna, Apr 15 2002

Description corrected by Axel Kleinschmidt, Sep 15 2002

A100953 Number of partitions of n into relatively prime parts such that multiplicities of parts are also relatively prime.

Original entry on oeis.org

1, 1, 0, 1, 2, 5, 5, 13, 14, 25, 28, 54, 54, 99, 105, 160, 192, 295, 315, 488, 546, 760, 890, 1253, 1404, 1945, 2234, 2953, 3459, 4563, 5186, 6840, 7909, 10029, 11716, 14843, 17123, 21635, 25035, 30981, 36098, 44581, 51370, 63259, 73223, 88739, 103048, 124752

Offset: 0

Vladeta Jovovic, Jan 11 2005

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Cf. A000740, A000837, A007916, A281116, A296302.

read transforms : a000837 := [] : b000837 := fopen("b000837.txt",READ) : bfil := readline(b000837) : while StringTools[WordCount](bfil) > 0 do b := sscanf( bfil,"%d %d") ; a000837 := [op(a000837),op(2,b)] ; bfil := readline(b000837) ; od: fclose(b000837) ; a000837 := subsop(1=NULL,a000837) : a := MOBIUS(a000837) : for n from 1 to 120 do printf("%d, ",op(n,a)) ; od: # R. J. Mathar, Mar 12 2008
# second Maple program:
with(numtheory): with(combinat):
b:= proc(n) option remember; `if`(n=0, 1, add(
       mobius(n/d)*numbpart(d), d=divisors(n)))
    end:
a:= proc(n) option remember; `if`(n=0, 1, add(
       mobius(n/d)*b(d), d=divisors(n)))
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Dec 19 2017

Table[Length[Select[IntegerPartitions[n],And[GCD@@#===1,GCD@@Length/@Split[#]===1]&]],{n,20}] (* Gus Wiseman, Dec 19 2017 *)
b[n_] := b[n] = If[n==0, 1, Sum[
     MoebiusMu[n/d]*PartitionsP[d], {d, Divisors[n]}]];
a[n_] := a[n] = If[n==0, 1, Sum[
     MoebiusMu[n/d]*b[d], {d, Divisors[n]}]];
a /@ Range[0, 60] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)

Moebius transform of A000837.

More terms from David Wasserman and R. J. Mathar, Mar 04 2008

a(0)=1 prepended by Alois P. Heinz, Dec 19 2017

A296774 Triangle read by rows in which row n lists the compositions of n ordered first by length and then reverse-lexicographically.

Original entry on oeis.org

1, 2, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 1, 2, 2, 1, 3, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 5, 4, 1, 3, 2, 2, 3, 1, 4, 3, 1, 1, 2, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 2, 1, 1, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 6, 5, 1, 4, 2, 3, 3

Offset: 1

Gus Wiseman, Dec 20 2017

			Triangle of compositions begins:
(1),
(2),(11),
(3),(21),(12),(111),
(4),(31),(22),(13),(211),(121),(112),(1111),
(5),(41),(32),(23),(14),(311),(221),(212),(131),(122),(113),(2111),(1211),(1121),(1112),(11111).

Cf. A066099, A101211, A108730, A124734, A228369, A281013, A294859, A296302, A296656, A296772, A296773.

Table[Sort[Join@@Permutations/@IntegerPartitions[n],Or[Length[#1]

A298748 Heinz numbers of aperiodic (relatively prime multiplicities) integer partitions with relatively prime parts.

Original entry on oeis.org

2, 6, 10, 12, 14, 15, 18, 20, 22, 24, 26, 28, 30, 33, 34, 35, 38, 40, 42, 44, 45, 46, 48, 50, 51, 52, 54, 55, 56, 58, 60, 62, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 84, 85, 86, 88, 90, 92, 93, 94, 95, 96, 98, 99, 102, 104, 105, 106, 108, 110, 112, 114

Offset: 1

Gus Wiseman, Mar 01 2018

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			Sequence of partitions begins: (1), (21), (31), (211), (41), (32), (221), (311), (51), (2111), (61), (411), (321), (52), (71), (43), (81), (3111), (421), (511), (322), (91), (21111), (331), (72), (611), (2221), (53), (4111).

Cf. A000740, A000837, A007916, A052410, A064989, A100953, A289508, A289509, A296302, A300272.

Select[Range[100],With[{t=Transpose[FactorInteger[#]]},And[GCD@@PrimePi/@t[[1]]===1,GCD@@t[[2]]===1]]&] (* Gus Wiseman, Apr 14 2018 *)

A185700 The number of periods in a reshuffling operation for compositions of n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 3, 5, 5, 3, 1, 0, 1, 3, 7, 8, 7, 3, 1, 0, 1, 4, 9, 14, 14, 9, 4, 1, 0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 0, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 0, 1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1

Offset: 1

Paul Weisenhorn, Feb 10 2011

n has 2^(n-1) compositions. For each composition remove the largest part and redistribute it by adding 1 to subsequently smaller parts (creating 1's if needed) to get a new composition of n. (This is reversing the operation in A188160.) Repeat. Eventually this sequence of compositions will cycle. We are interested in the length of the period.
Let the indices k and j be uniquely associated with n using the triangular numbers T=A000217: T(k-1) < n <= T(k) and n = T(k-1) + j with 0 < j <= k.
a(n) with T(k-1) < n <= T(k) is the number of periods with length k for 1 < k.
If k is prime then all periods of the numbers T(k-1) < n < T(k) have length k.
If k is not prime, then the length of the periods is k or a divisor of k.
n = T(k-1) + j has binomial(k,j) partitions in its periods with 0 < j < k.
n = T(k-1) + j has c(n) = Sum_{d|gcd(k,j)} (phi(d)*binomial(k/d,j/d))/k periods of length k or a divisor of k as tabulated in A047996; phi is Euler's totient function. If k is prime then a(n)=c(n) gives the number of periods with length k. If k is not prime, subtract all periods of length < k from c(n).
Obtained from A092964 by adding an initial column of 1's and appending a 1 and 0 to each row. Obtained from A051168 by reading the array downwards along antidiagonals. - R. J. Mathar, Apr 14 2011
As a regular triangle, T(n,k) is the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and length k. Row sums are A059966. - Gus Wiseman, Dec 19 2017

			For k=5: T(4)=10 < n < T(5)=15 and all periods are of length 5:
a(11)=1 period: [(4+3+2+1+1), (4+3+2+2), (4+3+3+1), (4+4+2+1), (5+3+2+1)];
a(12)=2 periods: [(4+3+2+2+1), (4+3+3+2), (4+4+3+1), (5+4+2+1), (5+3+2+1+1)]; and [(4+4+2+2), (5+3+3+1), (4+4+2+1+1), (5+3+2+2), (4+3+3+1+1)];
a(13)=2 periods: [(4+4+2+2+1), (5+3+3+2), (4+4+3+1+1), (5+4+2+2), (5+3+3+1+1)]; and [(5+4+3+1), (5+4+2+1+1), (5+3+2+2+1), (4+3+3+2+1), (4+4+3+2)];
a(14)=1 period: [(5+4+3+2), (5+4+3+1+1), (5+4+2+2+1), (5+3+3+2+1), (4+4+3+2+1)].
For k=16; j=8; n=T(k-1)+j=128; 1<q|(16,8) --> {2,4,8} a(128) = c(128) - a(T(7)+4) - a(T(3)+2) - a(T(1)+1) =  810 - 8 - 1 - 1 = 800.
  (binomial(16,8)-8*a(T(7)+4)-4*a(T(3)+2)-2*a(T(1)+1))/16 = (12870-64-4-2)/16 = 800 = a(128).
Triangular view, with a(n) distributed in rows k=1,2,3.. according to T(k-1)< n <= T(k):
1;     k=1, n=1
1, 0;    k=2, n=2..3
1, 1,  0;    k=3, n=4..6
1, 1,  1,  0;    k=4, n=7..10
1, 2,  2,  1,   0;    k=5, n=11..15
1, 2,  3,  2,   1,   0;    k=6, n=16..21
1, 3,  5,  5,   3,   1,   0;
1, 3,  7,  8,   7,   3,   1,   0;
1, 4,  9, 14,  14,   9,   4,   1,   0;
1, 4, 12, 20,  25,  20,  12,   4,   1,  0;
1, 5, 15, 30,  42,  42,  30,  15,   5,  1,  0;
1, 5, 18, 40,  66,  75,  66,  40,  18,  5,  1, 0;
1, 6, 22, 55,  99, 132, 132,  99,  55, 22,  6, 1, 0;
1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1, 0;

R. Baumann, Computer-Knobelei, LOGIN (1987), 483-486 (in German).

Ethan Akin, Morton Davis, Bulgarian solitaire, Am. Math. Monthly 92 (4) (1985) 237-250
J. Brandt, Cycles of partitions, Proc. Am. Math. Soc. 85 (3) (1982) 483-486

Cf. A000740, A001037, A008965, A051168, A059966, A060223, A245558, A294859, A296302, A296373, A092964, A245559, A245558.

A000217 := proc(n) n*(n+1)/2 ; end proc:
A185700 := proc(n) local k,j,a,q; k := ceil( (-1+sqrt(1+8*n))/2 ) ; j := n-A000217(k-1) ; if n = 1 then return 1; elif j = k then return 0 ; end if; a := binomial(k,j) ; if not isprime(k) then for q in numtheory[divisors]( igcd(k,j)) minus {1} do a := a- procname(j/q+A000217(k/q-1))*k/q ; end do: end if; a/k ; end proc:
seq(A185700(n),n=1..80) ; # R. J. Mathar, Jun 11 2011

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length@Select[Join@@Permutations/@Select[IntegerPartitions[n],Length[#]===k&],LyndonQ],{n,10},{k,n}] (* Gus Wiseman, Dec 19 2017 *)

a(T(k))=0 with k > 1. a(1)=1.
If k is a prime number and n = T(k-1) + j with 0 < j < k, then a(n) = binomial(k,j)/k.
If k is not prime, subtract the sum of partitions in all periods of n with length < k from the term binomial(k,j). The difference divided by k gives the number of periods for n=T(k-1)+j: a(n)=( binomial(k,j) -sum {a(T(k/q-1)+j/q) *k/q })/k summed over all 1 < q|gcd(k,j).
If k is not prime, subtract the sum of all periods of n with length < k from the term c(n) = sum{ phi(d)*binomial(k/d,j/d) }/k summed over d|gcd(k,j), namely
  a(n) = c(n)-sum{a(T(k/q-1)+j))} summed over all 1 < q|gcd(k,j).

I have added a comment and deleted a Jun 11 2011 question from R. J. Mathar. - Paul Weisenhorn, Jan 08 2017

A296373 Triangle T(n,k) = number of compositions of n whose factorization into Lyndon words (aperiodic necklaces) is of length k.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 6, 5, 3, 1, 1, 9, 12, 6, 3, 1, 1, 18, 21, 14, 6, 3, 1, 1, 30, 45, 27, 15, 6, 3, 1, 1, 56, 84, 61, 29, 15, 6, 3, 1, 1, 99, 170, 120, 67, 30, 15, 6, 3, 1, 1, 186, 323, 254, 136, 69, 30, 15, 6, 3, 1, 1, 335, 640, 510, 295, 142, 70, 30, 15, 6, 3, 1, 1

Offset: 1

Gus Wiseman, Dec 11 2017

			Triangle begins:
    1;
    1,   1;
    2,   1,   1;
    3,   3,   1,   1;
    6,   5,   3,   1,   1;
    9,  12,   6,   3,   1,   1;
   18,  21,  14,   6,   3,   1,   1;
   30,  45,  27,  15,   6,   3,   1,   1;
   56,  84,  61,  29,  15,   6,   3,   1,   1;
   99, 170, 120,  67,  30,  15,   6,   3,   1,   1;
  186, 323, 254, 136,  69,  30,  15,   6,   3,   1,   1;
  335, 640, 510, 295, 142,  70,  30,  15,   6,   3,   1,   1;

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Wikipedia, Lyndon word: Standard factorization

Cf. A000740, A001045, A008965, A019536, A059966, A060223, A185700, A228369, A232472, A277427, A281013, A296302, A296372.

neckQ[q_]:=Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
aperQ[q_]:=UnsameQ@@Table[RotateRight[q,k],{k,Length[q]}];
qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],neckQ[Take[q,#]]&&aperQ[Take[q,#]]&]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[qit[#]]===k&]],{n,12},{k,n}]

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
A(n)=[Vecrev(p/y) | p<-EulerMT(y*vector(n, n, sumdiv(n, d, moebius(n/d) * (2^d-1))/n))]
{ my(T=A(12)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Dec 01 2018

First column is A059966.

A318726 Number of integer compositions of n that have only one part or whose consecutive parts are indivisible and the last and first part are also indivisible.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 5, 3, 8, 13, 12, 23, 27, 56, 64, 100, 150, 216, 325, 459, 700, 1007, 1493, 2186, 3203, 4735, 6929, 10243, 14952, 22024, 32366, 47558, 69906, 102634, 150984, 221713, 325919, 478842, 703648, 1034104, 1519432, 2233062, 3281004, 4821791, 7085359

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

			The a(10) = 13 compositions:
  (10)
  (7,3) (3,7) (6,4) (4,6)
  (5,3,2) (5,2,3) (3,5,2) (3,2,5) (2,5,3) (2,3,5)
  (3,2,3,2) (2,3,2,3)
The a(11) = 12 compositions:
  (11)
  (9,2) (2,9) (8,3) (3,8) (7,4) (4,7) (6,5) (5,6)
  (5,2,4) (4,5,2) (2,4,5)

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A000740, A008965, A167606, A285573, A296302, A303362, A304713, A316476, A318727.

Table[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,({_,x_,y_,_}/;Divisible[x,y])|({y_,_,x_}/;Divisible[x,y])]&]//Length,{n,20}]

b(n,k,pred)={my(M=matrix(n,n)); for(n=1, n, M[n,n]=pred(k,n); for(j=1, n-1, M[n,j]=sum(i=1, n-j, if(pred(i,j), M[n-j,i], 0)))); sum(i=1, n, if(pred(i,k), M[n,i], 0))}
a(n)={1 + sum(k=1, n-1, b(n-k, k, (i,j)->i%j<>0))} \\ Andrew Howroyd, Sep 08 2018

a(n) = A328598(n) + 1. - Gus Wiseman, Nov 04 2019

a(21)-a(28) from Robert Price, Sep 08 2018
Terms a(29) and beyond from Andrew Howroyd, Sep 08 2018
Name corrected by Gus Wiseman, Nov 04 2019

A318728 Number of cyclic compositions (necklaces of positive integers) summing to n that have only one part or whose adjacent parts (including the last with first) are coprime.

Original entry on oeis.org

1, 2, 3, 4, 6, 9, 13, 22, 34, 58, 95, 168, 280, 492, 853, 1508, 2648, 4715, 8350, 14924, 26643, 47794, 85779, 154475, 278323, 502716, 908913, 1646206, 2984547, 5418653, 9847190, 17916001, 32625618, 59470540, 108493150, 198094483, 361965239, 661891580, 1211162271

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

			The a(7) = 13 cyclic compositions with adjacent parts coprime:
  7,
  16, 25, 34,
  115,
  1114, 1213, 1132, 1123,
  11113, 11212,
  111112,
  1111111.

Andrew Howroyd, Table of n, a(n) for n = 1..100

Cf. A000740, A000837, A008965, A059966, A100953, A167606, A296302, A318726, A318727, A328597.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Or[Length[#]==1,neckQ[#]&&And@@CoprimeQ@@@Partition[#,2,1,1]]&]],{n,20}]

b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q,]}
seq(n)={my(v=sum(k=1, n, k*b(n, k, (i,j)->gcd(i,j)==1))); vector(n, n, (n > 1) + sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 27 2019

a(n) = A328597(n) + 1 for n > 1. - Andrew Howroyd, Oct 27 2019

Terms a(21) and beyond from Andrew Howroyd, Sep 08 2018

Name corrected by Gus Wiseman, Nov 04 2019

A294859 Triangle whose n-th row is the concatenated sequence of all Lyndon compositions of n in lexicographic order.

Original entry on oeis.org

1, 2, 1, 2, 3, 1, 1, 2, 1, 3, 4, 1, 1, 1, 2, 1, 1, 3, 1, 2, 2, 1, 4, 2, 3, 5, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 4, 1, 2, 3, 1, 3, 2, 1, 5, 2, 4, 6, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 1, 4, 1, 1, 2, 1, 2, 1, 1, 2, 3, 1, 1, 3, 2, 1

Offset: 1

Gus Wiseman, Dec 18 2017

			Triangle of Lyndon compositions begins:
(1),
(2),
(12),(3),
(112),(13),(4),
(1112),(113),(122),(14),(23),(5),
(11112),(1113),(1122),(114),(123),(132),(15),(24),(6),
(111112),(11113),(11122),(1114),(11212),(1123),(1132),(115),(1213),(1222),(124),(133),(142),(16),(223),(25),(34),(7).

Cf. A000740, A001037, A001045, A008965, A059966, A060223, A066099, A101211, A102659, A124734, A185700, A228369, A281013, A296302, A296373, A296656.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Sort[Select[Join@@Permutations/@IntegerPartitions[n],LyndonQ],OrderedQ[PadRight[{#1,#2}]]&],{n,7}]

Row n is a concatenation of A059966(n) Lyndon words with total length A000740(n).

cp's OEIS Frontend

A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A059966 a(n) = (1/n) * Sum_{ d divides n } mu(n/d) * (2^d - 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

Extensions

A100953 Number of partitions of n into relatively prime parts such that multiplicities of parts are also relatively prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A296774 Triangle read by rows in which row n lists the compositions of n ordered first by length and then reverse-lexicographically.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A298748 Heinz numbers of aperiodic (relatively prime multiplicities) integer partitions with relatively prime parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A185700 The number of periods in a reshuffling operation for compositions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A296373 Triangle T(n,k) = number of compositions of n whose factorization into Lyndon words (aperiodic necklaces) is of length k.

Views

Author

Keywords

Examples

Links