A328171 -id:A328171 - cp's OEIS frontend

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

0, 0, 0, 0, 1, 0, 2, 1, 3, 5, 5, 7, 10, 18, 20, 29, 40, 58, 78, 111, 156, 218, 304, 429, 604, 859, 1209, 1726, 2423, 3462, 4904, 7000, 9953, 14210, 20270, 28979, 41391, 59253, 84799, 121539, 174162, 249931, 358577, 515090, 739932, 1063826, 1529766, 2201382, 3168565

Offset: 1

Gus Wiseman, Oct 25 2019

nonn

A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.

Circularity means the last part is followed by the first.

			The a(5) = 1 through a(13) = 18 necklace compositions (empty column not shown):
  (2,3)  (2,5)  (3,5)  (2,7)    (3,7)      (2,9)    (5,7)      (4,9)
         (3,4)         (4,5)    (4,6)      (3,8)    (2,3,7)    (5,8)
                       (2,4,3)  (2,3,5)    (4,7)    (2,7,3)    (6,7)
                                (2,5,3)    (5,6)    (3,4,5)    (2,11)
                                (2,3,2,3)  (2,4,5)  (3,5,4)    (3,10)
                                                    (2,3,2,5)  (2,4,7)
                                                    (2,3,4,3)  (2,6,5)
                                                               (2,8,3)
                                                               (3,6,4)
                                                               (2,3,5,3)

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

The non-necklace version is A328598.
The version with singletons is A318729.
The case forbidding multiples as well as divisors is A328601.
The non-necklace, non-circular version is A328460.
The version for co-primality (instead of divisibility) is A328602.
Necklace compositions are A008965.
Partitions with no part followed by a divisor are A328171.
Cf. A032153, A167606, A318748, A328508, A328593, A328599, A328603, A328608, A328609.

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

a(n) = A318729(n) - 1.

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

A328601 Number of necklace compositions of n with no part circularly followed by a divisor or a multiple.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 2, 1, 2, 5, 4, 7, 6, 13, 14, 20, 30, 38, 50, 68, 97, 132, 176, 253, 328, 470, 631, 901, 1229, 1709, 2369, 3269, 4590, 6383, 8897, 12428, 17251, 24229, 33782, 47404, 66253, 92859, 130141, 182468, 256261, 359675, 505230, 710058, 997952, 1404214

Offset: 1

Gus Wiseman, Oct 25 2019

nonn

A necklace composition of n (A008965) is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.

Circularity means the last part is followed by the first.

			The a(5) = 1 through a(13) = 6 necklace compositions (empty column not shown):
  (2,3)  (2,5)  (3,5)  (2,7)  (3,7)      (2,9)  (5,7)      (4,9)
         (3,4)         (4,5)  (4,6)      (3,8)  (2,3,7)    (5,8)
                              (2,3,5)    (4,7)  (2,7,3)    (6,7)
                              (2,5,3)    (5,6)  (3,4,5)    (2,11)
                              (2,3,2,3)         (3,5,4)    (3,10)
                                                (2,3,2,5)  (2,3,5,3)
                                                (2,3,4,3)

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

The non-necklace version is A328599.
The case forbidding divisors only is A328600 or A318729 (with singletons).
The non-necklace, non-circular version is A328508.
The version for co-primality (instead of indivisibility) is A328597.
Cf. A000740, A008965, A032153, A167606, A318748, A328171, A328460, A328593, A328598, A328602, A328603, A328608, A328609.

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

a(n) = A318730(n) - 1.

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

A328221 Number of integer partitions of n with at least one pair of consecutive divisible parts.

Original entry on oeis.org

0, 0, 1, 2, 4, 5, 10, 12, 20, 26, 38, 51, 73, 92, 126, 166, 219, 283, 369, 470, 604, 763, 968, 1217, 1534, 1907, 2376, 2944, 3640, 4476, 5501, 6723, 8212, 9986, 12130, 14682, 17748, 21376, 25717, 30847, 36959, 44152, 52688, 62714, 74557, 88440, 104775, 123878

Offset: 0

Gus Wiseman, Oct 15 2019

nonn

Includes all non-strict partitions.

			The a(2) = 1 through a(8) = 20 partitions:
  (11)  (21)   (22)    (41)     (33)      (61)       (44)
        (111)  (31)    (221)    (42)      (322)      (62)
               (211)   (311)    (51)      (331)      (71)
               (1111)  (2111)   (222)     (421)      (332)
                       (11111)  (321)     (511)      (422)
                                (411)     (2221)     (431)
                                (2211)    (3211)     (521)
                                (3111)    (4111)     (611)
                                (21111)   (22111)    (2222)
                                (111111)  (31111)    (3221)
                                          (211111)   (3311)
                                          (1111111)  (4211)
                                                     (5111)
                                                     (22211)
                                                     (32111)
                                                     (41111)
                                                     (221111)
                                                     (311111)
                                                     (2111111)
                                                     (11111111)

The complement is counted by A328171.
Partitions whose consecutive parts are relatively prime are A328172.
Partitions with no pair of consecutive parts relatively prime are A328187.
Numbers without consecutive divisible proper divisors are A328028.
Cf. A000837, A018783, A328026, A328161, A328188, A328189, A328194, A328220.

Table[Length[Select[IntegerPartitions[n],MatchQ[#,{_,x_,y_,_}/;Divisible[x,y]]&]],{n,0,30}]

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.

A328195 Maximum length of a divisibility chain of consecutive divisors of n greater than 1.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Oct 14 2019

nonn

Also the maximum length of a divisibility chain of consecutive divisors of n less than n.

The divisors of n (except 1) are row n of A027749.

			The divisors of 272 greater than 1 are {2, 4, 8, 16, 17, 34, 68, 136, 272}, with divisibility chains {{2, 4, 8, 16}, {17, 34, 68, 136, 272}}, so a(272) = 5.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Allowing 1 as a divisor gives A328162.
Forbidding n as a divisor of n gives A328194.
Positions of 1's are A000040 (primes).
Indices of terms greater than 1 are A002808 (composite numbers).
The maximum run-length of divisors of n is A055874(n).
Cf. A000005, A033676, A060775, A163870, A328026, A328161, A328171.

Table[If[n==1,0,Max@@Length/@Split[DeleteCases[Divisors[n],1],Divisible[#2,#1]&]],{n,100}]

A328195(n) = if(1==n, 0, my(divs=divisors(n), rl=0,ml=1); for(i=2,#divs,if(!(divs[i]%divs[i-1]), rl++, ml = max(rl,ml); rl=1)); max(ml,rl)); \\ Antti Karttunen, Dec 07 2024

Data section extended up to a(105) by Antti Karttunen, Dec 07 2024

A328599 Number of compositions of n with no part circularly followed by a divisor or a multiple.

Original entry on oeis.org

1, 0, 0, 0, 0, 2, 0, 4, 2, 4, 12, 8, 22, 14, 36, 44, 62, 114, 130, 206, 264, 414, 602, 822, 1250, 1672, 2520, 3518, 5146, 7408, 10448, 15224, 21496, 31284, 44718, 64170, 92314, 131618, 190084, 271870, 391188, 560978, 804264, 1155976, 1656428, 2381306, 3414846

Offset: 0

Gus Wiseman, Oct 25 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(0) = 1 through a(12) = 22 compositions (empty columns 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,3,5)    (6,5)  (3,2,7)
                                  (2,5,3)    (7,4)  (3,4,5)
                                  (3,2,5)    (8,3)  (3,5,4)
                                  (3,5,2)    (9,2)  (3,7,2)
                                  (5,2,3)           (4,3,5)
                                  (5,3,2)           (4,5,3)
                                  (2,3,2,3)         (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 A328601.
The case forbidding only divisors (not multiples) is A328598.
The non-circular version is A328508.
Partitions with no part followed by a divisor are A328171.
Cf. A000740, A008965, A167606, A318729, A318748, A328460, A328593, A328600, A328603, A328608, A328609, A328674.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],And@@Not/@Divisible@@@Partition[#,2,1,1]&&And@@Not/@Divisible@@@Reverse/@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&&j%i<>0)))} \\ Andrew Howroyd, Oct 26 2019

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

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]]&]

A328676 Number of relatively prime integer partitions of n whose distinct parts are pairwise indivisible.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 4, 3, 5, 5, 11, 7, 16, 14, 18, 22, 34, 30, 47, 45, 59, 66, 89, 90, 118, 125, 159, 169, 218, 225, 289, 304, 369, 400, 486, 520, 636, 680, 806, 873, 1051, 1105, 1333, 1424, 1664, 1803, 2122, 2253, 2659, 2841, 3283, 3560, 4118, 4388, 5096

Offset: 1

Gus Wiseman, Oct 29 2019

nonn

			The a(4) = 1 through a(11) = 11 partitions:
  1111  32     111111  43       53        54         73          65
        11111          52       332       72         433         74
                       322      11111111  522        532         83
                       1111111            3222       3322        92
                                          111111111  1111111111  443
                                                                 533
                                                                 722
                                                                 3332
                                                                 5222
                                                                 32222
                                                                 11111111111

The Heinz numbers of these partitions are given by A328677.
The strict case is A328678.
The binary index version is A328671.
Relatively prime partitions are A000837.
Partitions whose distinct parts are pairwise indivisible are A305148.
Cf. A285573, A289509, A303362, A316476, A326912, A327393, A328171.

stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[IntegerPartitions[n],GCD@@#==1&&stableQ[#,Divisible]&]],{n,30}]

A356736 Heinz numbers of integer partitions with no neighborless parts.

Original entry on oeis.org

1, 6, 12, 15, 18, 24, 30, 35, 36, 45, 48, 54, 60, 72, 75, 77, 90, 96, 105, 108, 120, 135, 143, 144, 150, 162, 175, 180, 192, 210, 216, 221, 225, 240, 245, 270, 288, 300, 315, 323, 324, 360, 375, 384, 385, 405, 420, 432, 437, 450, 462, 480, 486, 525, 539, 540

Offset: 1

Gus Wiseman, Aug 31 2022

nonn

First differs from A066312 in having 1 and lacking 462.
First differs from A104210 in having 1 and lacking 42.
A part x is neighborless iff neither x - 1 nor x + 1 are parts.
The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.

			The terms together with their prime indices begin:
   1: {}
   6: {1,2}
  12: {1,1,2}
  15: {2,3}
  18: {1,2,2}
  24: {1,1,1,2}
  30: {1,2,3}
  35: {3,4}
  36: {1,1,2,2}
  45: {2,2,3}
  48: {1,1,1,1,2}
  54: {1,2,2,2}
  60: {1,1,2,3}
  72: {1,1,1,2,2}
  75: {2,3,3}
  77: {4,5}
  90: {1,2,2,3}
  96: {1,1,1,1,1,2}

These partitions are counted by A355394.
The singleton case is the complement of A356237.
The singleton case is counted by A355393, complement A356235.
The strict complement is A356606, counted by A356607.
The complement is A356734, counted by A356236.
A000041 counts integer partitions, strict A000009.
A001221 counts distinct prime factors, sum A001414.
A003963 multiplies together the prime indices of n.
A007690 counts partitions with no singletons, complement A183558.
A056239 adds up prime indices, row sums of A112798, lengths A001222.
A073491 lists numbers with gapless prime indices, complement A073492.
Cf. A066312, A286470, A287170 (firsts A066205), A328171, A328187, A328221, A328335, A356231, A356234.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Function[ptn,!Or@@Table[!MemberQ[ptn,x-1]&&!MemberQ[ptn,x+1],{x,Union[ptn]}]]@*primeMS]

A328674 Numbers whose distinct prime indices have no consecutive divisible parts.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 15, 16, 17, 19, 23, 25, 27, 29, 31, 32, 33, 35, 37, 41, 43, 45, 47, 49, 51, 53, 55, 59, 61, 64, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 113, 119, 121, 123, 125, 127, 128, 131, 135

Offset: 1

Gus Wiseman, Oct 29 2019

nonn

First differs from A316476 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}
    4: {1,1}
    5: {3}
    7: {4}
    8: {1,1,1}
    9: {2,2}
   11: {5}
   13: {6}
   15: {2,3}
   16: {1,1,1,1}
   17: {7}
   19: {8}
   23: {9}
   25: {3,3}
   27: {2,2,2}
   29: {10}
   31: {11}
   32: {1,1,1,1,1}
For example, 45 is in the sequence because its distinct prime indices are {2,3} and 2 is not a divisor of 3.

These are the Heinz numbers of the partitions counted by A328675.
The strict version is A328603.
Partitions without consecutive divisibilities are A328171.
Compositions without consecutive divisibilities are A328460.
Cf. A056239, A112798, A316476, A318729, A328335, A328336, A328593, A328598.

Select[Range[100],!MatchQ[PrimePi/@First/@FactorInteger[#],{_,x_,y_,_}/;Divisible[y,x]]&]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A328601 Number of necklace compositions of n with no part circularly followed by a divisor or a multiple.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A328221 Number of integer partitions of n with at least one pair of consecutive divisible parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

A328195 Maximum length of a divisibility chain of consecutive divisors of n greater than 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A328599 Number of compositions of n with no part circularly followed by a divisor or a multiple.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A328676 Number of relatively prime integer partitions of n whose distinct parts are pairwise indivisible.