A303362 -id:A303362 - cp's OEIS frontend

A350844 Number of strict integer partitions of n with no difference -2.

1, 1, 1, 2, 1, 3, 3, 4, 4, 7, 7, 8, 11, 12, 15, 18, 21, 23, 31, 32, 40, 45, 54, 59, 73, 78, 94, 106, 122, 136, 161, 177, 203, 231, 259, 293, 334, 372, 417, 476, 525, 592, 663, 742, 821, 931, 1020, 1147, 1271, 1416, 1558, 1752, 1916, 2137, 2357, 2613, 2867

Offset: 0

Gus Wiseman, Jan 21 2022

nonn

			The a(1) = 1 through a(12) = 11 partitions (A..C = 10..12):
  1   2   3    4   5    6     7    8     9     A      B     C
          21       32   51    43   62    54    73     65    84
                   41   321   52   71    63    82     74    93
                              61   521   72    91     83    A2
                                         81    541    92    B1
                                         432   721    A1    543
                                         621   4321   632   651
                                                      821   732
                                                            741
                                                            921
                                                            6321

Gus Wiseman, Sequences counting and ranking partitions and compositions by their differences and quotients.

The version for no difference 0 is A000009.
The version for no difference > -2 is A001227, non-strict A034296.
The version for no difference -1 is A003114 (A325160).
The version for subsets of prescribed maximum is A005314.
The version for all differences < -2 is A025157, non-strict A116932.
The opposite version is A072670.
The multiplicative version is A350840, non-strict A350837 (A350838).
The non-strict version is A350842.
A000041 counts integer partitions.
A027187 counts partitions of even length.
A027193 counts partitions of odd length (A026424).
A116931 counts partitions with no difference -1 (A319630).
A323092 counts double-free integer partitions (A320340) strict A120641.
A325534 counts separable partitions (A335433).
A325535 counts inseparable partitions (A335448).
Cf. A000929, A003000, A018819, A040039, A045690, A045691, A154402, A303362, A323094, A342095, A342097.

Table[Length[Select[IntegerPartitions[n],FreeQ[Differences[#],0|-2]&]],{n,0,30}]

A371177 Positive integers whose prime indices include all distinct divisors of all prime indices.

Original entry on oeis.org

1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 30, 32, 34, 36, 40, 42, 44, 48, 50, 54, 60, 62, 64, 66, 68, 72, 80, 82, 84, 88, 90, 96, 100, 102, 108, 110, 118, 120, 124, 126, 128, 132, 134, 136, 144, 150, 160, 162, 164, 166, 168, 170, 176, 180, 186, 192, 198, 200

Offset: 1

Gus Wiseman, Mar 18 2024

nonn

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.

Also positive integers with as many distinct prime factors (A001221) as distinct divisors of prime indices (A370820).

			The terms together with their prime indices begin:
    1: {}
    2: {1}
    4: {1,1}
    6: {1,2}
    8: {1,1,1}
   10: {1,3}
   12: {1,1,2}
   16: {1,1,1,1}
   18: {1,2,2}
   20: {1,1,3}
   22: {1,5}
   24: {1,1,1,2}
   30: {1,2,3}
   32: {1,1,1,1,1}
   34: {1,7}
   36: {1,1,2,2}
   40: {1,1,1,3}
   42: {1,2,4}
   44: {1,1,5}
   48: {1,1,1,1,2}

The LHS is A001221, distinct case of A001222.
The RHS is A370820, for prime factors A303975.
For bigomega on the LHS we have A370802, counted by A371130.
For divisors on the LHS we have A371165, counted by A371172.
Partitions of this type are counted by A371178, strict A371128.
The complement is A371179, counted by A371132.
A000005 counts divisors.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length.
A305148 counts partitions without divisors, strict A303362, ranks A316476.
Cf. A000837, A003963, A239312, A285573, A355529, A370813, A371168.

Select[Range[100],PrimeNu[#]==Length[Union @@ Divisors/@PrimePi/@First/@If[#==1,{},FactorInteger[#]]]&]

A001221(a(n)) = A370820(a(n)).

A087086 Primitive sets of integers, each subset mapped onto a unique binary integer, values here shown in decimal.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 12, 16, 18, 20, 22, 24, 28, 32, 40, 48, 56, 64, 66, 68, 70, 72, 76, 80, 82, 84, 86, 88, 92, 96, 104, 112, 120, 128, 132, 144, 148, 160, 176, 192, 196, 208, 212, 224, 240, 256, 258, 264, 272, 274, 280, 288, 296, 304, 312, 320, 322, 328, 336, 338, 344

Offset: 0

Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 14 2003

A primitive set of integers has no pair of elements one of which divides the other. Each element i in a subset contributes 2^(i-1) to the binary value for that subset. The integers missing from the sequence correspond to nonprimitive subsets.

			a(10)=22 since the 10th primitive set counting from 0 is {5,3,2}, which maps onto 10110 binary = 22 decimal.
From _Gus Wiseman_, Oct 31 2019: (Start)
The sequence of terms together with their binary expansions and binary indices begins:
   0:       0 ~ {}
   1:       1 ~ {1}
   2:      10 ~ {2}
   4:     100 ~ {3}
   6:     110 ~ {2,3}
   8:    1000 ~ {4}
  12:    1100 ~ {3,4}
  16:   10000 ~ {5}
  18:   10010 ~ {2,5}
  20:   10100 ~ {3,5}
  22:   10110 ~ {2,3,5}
  24:   11000 ~ {4,5}
  28:   11100 ~ {3,4,5}
(End)

Alan Sutcliffe, Divisors and Common Factors in Sets of Integers, awaiting publication

A051026 gives the number of primitive subsets of the integers 1 to n.
The version for prime indices (rather than binary indices) is A316476.
The relatively prime case is A328671.
Partitions with no consecutive divisible parts are A328171.
Compositions without consecutive divisible parts are A328460.
A ranking of antichains is A326704.
Cf. A000120, A048793, A070939, A285572, A285573, A303362, A304713, A305148, A328593.

stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Select[Range[0,100],stableQ[Join@@Position[Reverse[IntegerDigits[#,2]],1],Divisible]&] (* Gus Wiseman, Oct 31 2019 *)

A304717 Number of connected strict integer partitions of n with pairwise indivisible parts.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 2, 1, 3, 2, 4, 3, 5, 2, 5, 4, 6, 3, 7, 6, 9, 5, 9, 8, 13, 10, 15, 9, 15, 13, 18, 14, 22, 21, 26, 19, 29, 24, 36, 31, 40, 35, 45, 38, 54, 55, 59, 55, 70, 69, 84, 74, 89, 86, 107, 103, 119, 115, 143, 143, 159

Offset: 1

Gus Wiseman, May 17 2018

nonn

Given a finite set S of positive integers greater than one, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices with a common divisor. For example, G({6,14,15,35}) is a 4-cycle. A multiset S is said to be connected if G(S) is a connected graph.

			The a(34) = 13 connected strict integer partitions with pairwise indivisible parts are (34), (18,16), (20,14), (22,12), (24,10), (26,8), (28,6), (30,4), (14,12,8), (15,10,9), (20,8,6), (14,10,6,4), (15,9,6,4). Their corresponding multiset multisystems (see A112798, A302242) are the following.
         (34): {{1,7}}
       (30 4): {{1,2,3},{1,1}}
       (28 6): {{1,1,4},{1,2}}
       (26 8): {{1,6},{1,1,1}}
      (24 10): {{1,1,1,2},{1,3}}
      (22 12): {{1,5},{1,1,2}}
      (20 14): {{1,1,3},{1,4}}
     (20 8 6): {{1,1,3},{1,1,1},{1,2}}
      (18 16): {{1,2,2},{1,1,1,1}}
    (15 10 9): {{2,3},{1,3},{2,2}}
   (15 9 6 4): {{2,3},{2,2},{1,2},{1,1}}
    (14 12 8): {{1,4},{1,1,2},{1,1,1}}
  (14 10 6 4): {{1,4},{1,3},{1,2},{1,1}}

Cf. A000009, A003963, A006126, A048143, A051424, A054921, A076078, A259936, A281116, A285572, A285573, A286518, A286520, A293993, A302242, A303362, A304714, A304716.

zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[Less@@#,GCD@@s[[#]]]>1&]},If[c==={},s,zsm[Union[Append[Delete[s,List/@c[[1]]],LCM@@s[[c[[1]]]]]]]]];
Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Length[zsm[#]]===1&&Select[Tuples[#,2],UnsameQ@@#&&Divisible@@#&]==={}&]],{n,30}]

A320632 Numbers k such that there exists a pair of factorizations of k into factors > 1 where no factor of one divides any factor of the other.

Original entry on oeis.org

36, 60, 72, 84, 90, 100, 108, 120, 126, 132, 140, 144, 150, 156, 168, 180, 196, 198, 200, 204, 210, 216, 220, 225, 228, 234, 240, 252, 260, 264, 270, 276, 280, 288, 294, 300, 306, 308, 312, 315, 324, 330, 336, 340, 342, 348, 350, 360, 364, 372, 378, 380, 390

Offset: 1

Gus Wiseman, Dec 09 2018

nonn

Positions of nonzero terms in A322437 or A322438.
Mats Granvik has conjectured that these are all the positive integers k such that sigma_0(k) - 2 > (bigomega(k) - 1) * omega(k), where sigma_0 = A000005, omega = A001221, and bigomega = A001222. - Gus Wiseman, Nov 12 2019
Numbers with more semiprime divisors than prime divisors. - Wesley Ivan Hurt, Jun 10 2021

			An example of such a pair for 36 is (4*9)|(6*6).

Antti Karttunen, Table of n, a(n) for n = 1..23437
Christophe Cordero, Factorizations of Cyclic Groups and Bayonet Codes, arXiv:2301.13566 [math.CO], 2023, p. 20.

Cf. A001055, A050336, A285572, A303362, A305149, A305193, A317144, A322435, A322437, A322439, A322440, A322441, A322442.
The following are additional cross-references relating to Granvik's conjecture.
bigomega(n) * omega(n) is A113901(n).
(bigomega(n) - 1) * omega(n) is A307409(n).
sigma_0(n) - bigomega(n) * omega(n) is A328958(n).
sigma_0(n) - 2 - (omega(n) - 1) * nu(n) is A328959(n).
Cf. A060687, A070175, A124010, A323023, A328956, A328957, A328960, A328961, A328963.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Select[Range[100],Select[Subsets[facs[#],{2}],And[!Or@@Divisible@@@Tuples[#],!Or@@Divisible@@@Reverse/@Tuples[#]]&]!={}&]

factorizations(n, m=n, f=List([]), z=List([])) = if(1==n, listput(z,Vec(f)); z, my(newf); fordiv(n, d, if((d>1)&&(d<=m), newf = List(f); listput(newf,d); z = factorizations(n/d, d, newf, z))); (z));
is_ndf_pair(fac1,fac2) = { for(i=1,#fac1,for(j=1,#fac2,if(!(fac1[i]%fac2[j])||!(fac2[j]%fac1[i]),return(0)))); (1); };
has_at_least_one_ndfpair(z) = { for(i=1,#z,for(j=i+1,#z,if(is_ndf_pair(z[i],z[j]),return(1)))); (0); };
isA320632(n) = has_at_least_one_ndfpair(Vec(factorizations(n))); \\ Antti Karttunen, Dec 10 2020

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

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

A304382 Number of z-trees summing to n. Number of connected strict integer partitions of n with pairwise indivisible parts and clutter density -1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 2, 1, 3, 2, 4, 3, 5, 2, 5, 4, 6, 3, 7, 6, 8, 4, 9, 8, 13, 9, 15, 8, 14, 12, 16, 12, 20, 20, 24, 15, 27, 20, 33, 27, 35

Offset: 1

Gus Wiseman, May 21 2018

Given a finite set S of positive integers greater than one, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices with a common divisor. For example, G({6,14,15,35}) is a 4-cycle. A multiset S is said to be connected if G(S) is a connected graph.

The clutter density of a multiset S of positive integers is Sum_{s in S} (omega(s) - 1) - omega(LCM(S)).

			The a(30) = 8 z-trees together with the corresponding multiset systems are the following.
       (30): {{1,2,3}}
     (26,4): {{1,6},{1,1}}
     (22,8): {{1,5},{1,1,1}}
     (21,9): {{2,4},{2,2}}
    (16,14): {{1,1,1,1},{1,4}}
   (15,9,6): {{2,3},{2,2},{1,2}}
  (14,10,6): {{1,4},{1,3},{1,2}}
  (12,10,8): {{1,1,2},{1,3},{1,1,1}}

Roland Bacher, On the enumeration of labelled hypertrees and of labelled bipartite trees, arXiv:1102.2708 [math.CO], 2011.

Cf. A000009, A006126, A048143, A054921, A112798, A285572, A286518, A286520, A293993, A303362, A303837, A304714, A304716, A305194, A305195.

zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[Less@@#,GCD@@s[[#]]]>1&]},If[c=={},s,zsm[Union[Append[Delete[s,List/@c[[1]]],LCM@@s[[c[[1]]]]]]]]];
zensity[s_]:=Total[(PrimeNu[#]-1&)/@s]-PrimeNu[LCM@@s];
zreeQ[s_]:=And[Length[s]>=2,zensity[s]==-1];
strConnAnti[n_]:=Select[IntegerPartitions[n],UnsameQ@@#&&Length[zsm[#]]==1&&Select[Tuples[#,2],UnsameQ@@#&&Divisible@@#&]=={}&];
Table[Length[Select[strConnAnti[n],Length[#]==1||zreeQ[#]&]],{n,20}]

A326077 Number of maximal primitive subsets of {1..n}.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 4, 4, 6, 7, 11, 11, 13, 13, 23, 24, 36, 36, 48, 48, 64, 66, 126, 126, 150, 151, 295, 363, 507, 507, 595, 595, 895, 903, 1787, 1788, 2076, 2076, 4132, 4148, 5396, 5396, 6644, 6644, 9740, 11172, 22300, 22300, 26140, 26141, 40733, 40773, 60333, 60333, 80781, 80783

Offset: 0

Gus Wiseman, Jun 05 2019

nonn

a(n) is the number of maximal primitive subsets of {1, ..., n}. Here primitive means that no element of the subset divides any other and maximal means that no element can be added to the subset while maintaining the property of being pairwise indivisible. - Nathan McNew, Aug 10 2020

			The a(0) = 1 through a(9) = 7 sets:
  {}  {1}  {1}  {1}   {1}   {1}    {1}    {1}     {1}     {1}
           {2}  {23}  {23}  {235}  {235}  {2357}  {2357}  {2357}
                      {34}  {345}  {345}  {3457}  {3457}  {2579}
                                   {456}  {4567}  {3578}  {3457}
                                                  {4567}  {3578}
                                                  {5678}  {45679}
                                                          {56789}

Nathan McNew, Table of n, a(n) for n = 0..300

Cf. A001055, A051026 (all primitive subsets), A067992, A096827, A143824, A285572, A285573, A303362, A305148, A305149, A316476, A325861, A326023, A326082.

stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 1}];
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]],stableQ[#,Divisible]&]]],{n,0,10}]

divset(n)={sumdiv(n, d, if(dif(k>#p, ismax(b), my(f=!bitand(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<Andrew Howroyd, Aug 30 2019

Terms a(19) to a(55) from Andrew Howroyd, Aug 30 2019

Name edited by Nathan McNew, Aug 10 2020

A316468 Matula-Goebel numbers of locally stable rooted trees, meaning no branch is a submultiset of any other branch of the same root.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 15, 16, 17, 19, 23, 25, 27, 31, 32, 33, 35, 45, 47, 49, 51, 53, 55, 59, 64, 67, 69, 75, 77, 81, 83, 85, 93, 95, 97, 99, 103, 119, 121, 125, 127, 128, 131, 135, 137, 141, 149, 153, 155, 161, 165, 175, 177, 187, 197, 201, 207, 209

Offset: 1

Gus Wiseman, Jul 04 2018

nonn

A prime index of n is a number m such that prime(m) divides n. A number is in the sequence iff its distinct prime indices are pairwise indivisible and already belong to the sequence.

			Sequence of locally stable rooted trees preceded by their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   7: ((oo))
   8: (ooo)
   9: ((o)(o))
  11: ((((o))))
  15: ((o)((o)))
  16: (oooo)
  17: (((oo)))
  19: ((ooo))
  23: (((o)(o)))
  25: (((o))((o)))
  27: ((o)(o)(o))
  31: (((((o)))))

Cf. A000081, A004111, A007097, A112798, A277098, A285572, A285573, A303362, A304713, A316467, A316470, A316473, A316475, A316476, A316495.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Or[#==1,And[Select[Tuples[primeMS[#],2],UnsameQ@@#&&Divisible@@#&]=={},And@@#0/@primeMS[#]]]&]

cp's OEIS Frontend

A350844 Number of strict integer partitions of n with no difference -2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A371177 Positive integers whose prime indices include all distinct divisors of all prime indices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A087086 Primitive sets of integers, each subset mapped onto a unique binary integer, values here shown in decimal.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

A304717 Number of connected strict integer partitions of n with pairwise indivisible parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A320632 Numbers k such that there exists a pair of factorizations of k into factors > 1 where no factor of one divides any factor of the other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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.

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

A304382 Number of z-trees summing to n. Number of connected strict integer partitions of n with pairwise indivisible parts and clutter density -1.

Views

Author

Keywords

Comments

Examples