A318726 -id:A318726 - cp's OEIS frontend

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.

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

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

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 4, 6, 6, 8, 11, 19, 21, 30, 41, 59, 79, 112, 157, 219, 305, 430, 605, 860, 1210, 1727, 2424, 3463, 4905, 7001, 9954, 14211, 20271, 28980, 41392, 59254, 84800, 121540, 174163, 249932, 358578, 515091, 739933, 1063827, 1529767, 2201383

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

			The a(13) = 11 cyclic compositions with successive parts indivisible:
  (13)
  (2,11) (3,10) (4,9) (5,8) (6,7)
  (2,4,7) (2,6,5) (2,8,3) (3,6,4)
  (2,3,5,3)

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

Cf. A000740, A008965, A059966, A167606, A285573, A303362, A304713, A316476, A318726, A318727, A318728, A318730, A328600.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Or[Length[#]==1,neckQ[#]&&And@@Not/@Divisible@@@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)->i%j<>0))); vector(n, n, 1 + sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 27 2019

a(n) = A328600(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

A328598 Number of compositions of n with no part circularly followed by a divisor.

Original entry on oeis.org

1, 0, 0, 0, 0, 2, 0, 4, 2, 7, 12, 11, 22, 26, 55, 63, 99, 149, 215, 324, 458, 699, 1006, 1492, 2185, 3202, 4734, 6928, 10242, 14951, 22023, 32365, 47557, 69905, 102633, 150983, 221712, 325918, 478841, 703647, 1034103, 1519431, 2233061, 3281003, 4821790, 7085358

Offset: 0

Gus Wiseman, Oct 24 2019

nonn

A composition of n is a finite sequence of positive integers summing to n.

Circularity means the last part is followed by the first.

			The a(5) = 2 through a(12) = 22 compositions (empty column not shown):
  (2,3)  (2,5)  (3,5)  (2,7)    (3,7)      (2,9)    (5,7)
  (3,2)  (3,4)  (5,3)  (4,5)    (4,6)      (3,8)    (7,5)
         (4,3)         (5,4)    (6,4)      (4,7)    (2,3,7)
         (5,2)         (7,2)    (7,3)      (5,6)    (2,7,3)
                       (2,4,3)  (2,3,5)    (6,5)    (3,2,7)
                       (3,2,4)  (2,5,3)    (7,4)    (3,4,5)
                       (4,3,2)  (3,2,5)    (8,3)    (3,5,4)
                                (3,5,2)    (9,2)    (3,7,2)
                                (5,2,3)    (2,4,5)  (4,3,5)
                                (5,3,2)    (4,5,2)  (4,5,3)
                                (2,3,2,3)  (5,2,4)  (5,3,4)
                                (3,2,3,2)           (5,4,3)
                                                    (7,2,3)
                                                    (7,3,2)
                                                    (2,3,2,5)
                                                    (2,3,4,3)
                                                    (2,5,2,3)
                                                    (3,2,3,4)
                                                    (3,2,5,2)
                                                    (3,4,3,2)
                                                    (4,3,2,3)
                                                    (5,2,3,2)

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

The necklace version is A328600, or A318729 without singletons.
The version with singletons is A318726.
The non-circular version is A328460.
Also forbidding parts circularly followed by a multiple gives A328599.
Partitions with no part followed by a divisor are A328171.
Cf. A000740, A008965, A167606, A178470, A318748, A328187, A328508, A328593, A328597, A328601, A328603, A328609.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],And@@Not/@Divisible@@@Partition[#,2,1,1]&]],{n,0,10}]

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)={concat([1], sum(k=1, n, b(n, k, (i,j)->i%j<>0)))} \\ Andrew Howroyd, Oct 26 2019

a(n > 0) = A318726(n) - 1.

Terms a(26) and beyond from Andrew Howroyd, Oct 26 2019

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

Original entry on oeis.org

1, 1, 2, 4, 7, 13, 24, 43, 82, 151, 285, 535, 1005, 1883, 3533, 6631, 12460, 23407, 43952, 82538, 154999, 291088, 546674, 1026687, 1928118, 3621017, 6800300, 12771086, 23984329, 45042959, 84591339, 158863807, 298348613, 560303342, 1052258402, 1976157510

Offset: 0

Gus Wiseman, Sep 02 2018

nonn

			The a(5) = 13 compositions with adjacent parts coprime:
  (5)
  (41) (14) (32) (23)
  (311) (131) (113)
  (2111) (1211) (1121) (1112)
  (11111)
Missing from this list are (221), (212), and (122).

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

Cf. A000740, A008965, A059966, A100953, A167606, A296302, A318726, A318727, A318728, A318745, A328609.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Or[Length[#]==1,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)={concat([1], vector(n, i, i > 1) + sum(k=1, n, b(n, k, (i, j)->gcd(i, j)==1)))} \\ Andrew Howroyd, Nov 01 2019

a(n) = A328609(n) + 1 for n > 1. - Andrew Howroyd, Nov 01 2019

a(21)-a(35) from Alois P. Heinz, Sep 02 2018

Name corrected by Gus Wiseman, Nov 04 2019

A328609 Number of compositions of n whose circularly adjacent parts are relatively prime.

Original entry on oeis.org

1, 1, 1, 3, 6, 12, 23, 42, 81, 150, 284, 534, 1004, 1882, 3532, 6630, 12459, 23406, 43951, 82537, 154998, 291087, 546673, 1026686, 1928117, 3621016, 6800299, 12771085, 23984328, 45042958, 84591338, 158863806, 298348612, 560303341, 1052258401, 1976157509

Offset: 0

Gus Wiseman, Oct 26 2019

nonn

Circularity means the last part is followed by the first.

			The a(1) = 1 through a(6) = 23 compositions:
  (1)  (11)  (12)   (13)    (14)     (15)
             (21)   (31)    (23)     (51)
             (111)  (112)   (32)     (114)
                    (121)   (41)     (123)
                    (211)   (113)    (132)
                    (1111)  (131)    (141)
                            (311)    (213)
                            (1112)   (231)
                            (1121)   (312)
                            (1211)   (321)
                            (2111)   (411)
                            (11111)  (1113)
                                     (1131)
                                     (1212)
                                     (1311)
                                     (2121)
                                     (3111)
                                     (11112)
                                     (11121)
                                     (11211)
                                     (12111)
                                     (21111)
                                     (111111)

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

The necklace version is A328597 or A318728 (with singletons).
The aperiodic version is A328670.
The Lyndon word version is A318745.
The version with singletons is A318748.
The non-circular version is A167606.
Relatively prime compositions are A000740.
Compositions with no part circularly followed by a divisor are A328598.
Cf. A008965, A178470, A318726, A325680, A328172, A328335, A328599, A328600.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],And@@CoprimeQ@@@Partition[#,2,1,1]&]],{n,10}]

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)={concat([1], sum(k=1, n, b(n, k, (i, j)->gcd(i, j)==1)))} \\ Andrew Howroyd, Nov 01 2019

a(n > 1) = A318748(n) - 1.

A328603 Numbers whose prime indices have no consecutive divisible parts, meaning no prime index is a divisor of the next-smallest prime index, counted with multiplicity.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 33, 35, 37, 41, 43, 47, 51, 53, 55, 59, 61, 67, 69, 71, 73, 77, 79, 83, 85, 89, 91, 93, 95, 97, 101, 103, 105, 107, 109, 113, 119, 123, 127, 131, 137, 139, 141, 143, 145, 149, 151, 155, 157, 161, 163, 165, 167

Offset: 1

Gus Wiseman, Oct 26 2019

nonn

First differs from A304713 in having 105, with prime indices {2, 3, 4}.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The sequence of terms together with their prime indices begins:
    1: {}
    2: {1}
    3: {2}
    5: {3}
    7: {4}
   11: {5}
   13: {6}
   15: {2,3}
   17: {7}
   19: {8}
   23: {9}
   29: {10}
   31: {11}
   33: {2,5}
   35: {3,4}
   37: {12}
   41: {13}
   43: {14}
   47: {15}
   51: {2,7}

A subset of A005117.
These are the Heinz numbers of the partitions counted by A328171.
The non-strict version is A328674 (Heinz numbers for A328675).
The version for relatively prime instead of indivisible is A328335.
Compositions without consecutive divisibilities are A328460.
Numbers whose binary indices lack consecutive divisibilities are A328593.
The version with all pairs indivisible is A304713.
Cf. A056239, A112798, A316476, A318726, A318729, A326704, A328336, A328598, A328599.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],!MatchQ[primeMS[#],{_,x_,y_,_}/;Divisible[y,x]]&]

Intersection of A005117 and A328674.

A318727 Number of integer compositions of n where adjacent parts are indivisible (either way) and the last and first part are also indivisible (either way).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 5, 3, 5, 13, 9, 23, 15, 37, 45, 63, 115, 131, 207, 265, 415, 603, 823, 1251, 1673, 2521, 3519, 5147, 7409, 10449, 15225, 21497, 31285, 44719, 64171, 92315, 131619, 190085, 271871, 391189, 560979, 804265, 1155977, 1656429, 2381307, 3414847

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)

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

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

Table[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,({_,x_,y_,_}/;Divisible[x,y]||Divisible[y,x])|({y_,_,x_}/;Divisible[x,y]||Divisible[y,x])]&]//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&&j%i<>0))} \\ Andrew Howroyd, Sep 08 2018

a(21)-a(28) from Robert Price, Sep 07 2018

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

A318730 Number of cyclic compositions (necklaces of positive integers) summing to n with adjacent parts (including the last and first part) being indivisible (either way).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 3, 6, 5, 8, 7, 14, 15, 21, 31, 39, 51, 69, 98, 133, 177, 254, 329, 471, 632, 902, 1230, 1710, 2370, 3270, 4591, 6384, 8898, 12429, 17252, 24230, 33783, 47405, 66254, 92860, 130142, 182469, 256262, 359676, 505231, 710059, 997953, 1404215

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

			The a(14) = 14 cyclic compositions with adjacent parts indivisible either way:
  (14)
  (3,11) (4,10) (5,9) (6,8)
  (2,5,7) (2,7,5) (3,4,7) (3,7,4)
  (2,3,2,7) (2,3,4,5) (2,5,2,5) (2,5,4,3) (3,4,3,4)

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

Cf. A000740, A008965, A059966, A167606, A285573, A303362, A304713, A316476, A318726, A318727, A318728, A318729, A328601.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Or[Length[#]==1,And[neckQ[#],And@@Not/@Divisible@@@Partition[#,2,1,1],And@@Not/@Divisible@@@Reverse/@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)->i%j<>0 && j%i<>0))); vector(n, n, 1 + sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 27 2019

a(n) = A328601(n) + 1. - Andrew Howroyd, Oct 27 2019

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

A328608 Numbers whose binary indices have no part circularly followed by a divisor or a multiple.

Original entry on oeis.org

6, 12, 18, 20, 22, 24, 28, 30, 40, 48, 56, 66, 68, 70, 72, 76, 78, 80, 82, 84, 86, 88, 92, 94, 96, 104, 108, 110, 112, 114, 116, 118, 120, 124, 126, 132, 144, 148, 156, 160, 172, 176, 180, 188, 192, 196, 204, 208, 212, 220, 224, 236, 240, 244, 252, 258, 264

Offset: 1

Gus Wiseman, Oct 25 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
Circularity means the last part is followed by the first.
Note that this is a somewhat degenerate case, as a part could only be followed by a divisor if it is the last part followed by the first.

			The sequence of terms together with their binary expansions and binary indices begins:
    6:       110 ~ {2,3}
   12:      1100 ~ {3,4}
   18:     10010 ~ {2,5}
   20:     10100 ~ {3,5}
   22:     10110 ~ {2,3,5}
   24:     11000 ~ {4,5}
   28:     11100 ~ {3,4,5}
   30:     11110 ~ {2,3,4,5}
   40:    101000 ~ {4,6}
   48:    110000 ~ {5,6}
   56:    111000 ~ {4,5,6}
   66:   1000010 ~ {2,7}
   68:   1000100 ~ {3,7}
   70:   1000110 ~ {2,3,7}
   72:   1001000 ~ {4,7}
   76:   1001100 ~ {3,4,7}
   78:   1001110 ~ {2,3,4,7}
   80:   1010000 ~ {5,7}
   82:   1010010 ~ {2,5,7}
   84:   1010100 ~ {3,5,7}

The composition version is A328599.
The necklace composition version is A328601.
Compositions with no consecutive divisors or multiples are A328508.
Numbers whose binary indices are pairwise indivisible are A326704.
Cf. A000031, A318726, A318729, A328171, A328460, A328593, A328598, A328600, A328603.

Select[Range[100],!MatchQ[Append[Join@@Position[Reverse[IntegerDigits[#,2]],1],1+IntegerExponent[#,2]],{_,x_,y_,_}/;Divisible[x,y]||Divisible[y,x]]&]

A318746 Number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and successive parts (including the last with the first part) being indivisible.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 4, 5, 6, 8, 11, 17, 20, 29, 41, 56, 79, 107, 155, 214, 305, 422, 604, 850, 1207, 1709, 2424, 3439, 4905, 6972, 9949, 14171, 20268, 28915, 41392, 59176, 84790, 121428, 174163, 249760, 358578, 514873, 739910, 1063523, 1529767, 2200926

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

			The a(14) = 17 Lyndon compositions with successive parts indivisible:
  (14)
  (3,11) (4,10) (5,9) (6,8)
  (2,3,9) (2,5,7) (2,7,5) (3,4,7) (3,6,5) (3,7,4)
  (2,3,2,7) (2,3,4,5) (2,4,3,5) (2,4,5,3) (2,5,4,3)
  (2,3,2,4,3)

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

Cf. A000740, A008965, A059966, A285573, A303362, A318726, A318727, A318729, A318730, A318731, A318745, A318747.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Or[Length[#]==1,LyndonQ[#]&&And@@Not/@Divisible@@@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)->i%j<>0))); vector(n, n, 1 + sumdiv(n, d, moebius(d)*v[n/d])/n)} \\ Andrew Howroyd, Nov 01 2019

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

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A328598 Number of compositions of n with no part circularly followed by a divisor.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A328609 Number of compositions of n whose circularly adjacent parts are relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A328603 Numbers whose prime indices have no consecutive divisible parts, meaning no prime index is a divisor of the next-smallest prime index, counted with multiplicity.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A318727 Number of integer compositions of n where adjacent parts are indivisible (either way) and the last and first part are also indivisible (either way).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs