A303362 -id:A303362 - cp's OEIS frontend

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.

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

A318747 Number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and adjacent parts (including the last with the first part) being indivisible (either way).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 3, 5, 5, 8, 7, 12, 14, 20, 31, 37, 51, 64, 96, 129, 177, 246, 328, 465, 630, 889, 1230, 1692, 2370, 3250, 4587, 6354, 8895, 12384, 17252, 24180, 33777, 47336, 66254, 92752, 130142, 182337, 256246, 359500, 505231, 709787, 997951, 1403883

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

			The a(14) = 12 Lyndon 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,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, A318746.

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,And[LyndonQ[#],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, moebius(d)*v[n/d])/n)} \\ Andrew Howroyd, Nov 01 2019

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

A327394 Number of stable divisors of n.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Sep 15 2019

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. A number is stable if its distinct prime indices are pairwise indivisible. Stable numbers are listed in A316476. Maximum stable divisor is A327393.

			The stable divisors of 60 are {1, 2, 3, 4, 5, 15}, so a(60) = 6.

Antti Karttunen, Table of n, a(n) for n = 1..20000
Gus Wiseman, Sequences counting and encoding certain classes of multisets
Index entries for sequences related to prime indices in the factorization of n

See link for additional cross-references.
Cf. A000005, A033273, A303362, A316476, A327393.
Inverse Möbius transform of A378442.

stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Divisors[n],stableQ[PrimePi/@First/@FactorInteger[#],Divisible]&]],{n,100}]

A378442(n)={my(v=apply(primepi, factor(n)[, 1])); for(j=2, #v, for(i=1, j-1, if(v[j]%v[i]==0, return(0)))); 1}; \\ From the function "ok" in A316476 by Andrew Howroyd, Aug 26 2018
A327394(n) = sumdiv(n,d,A378442(d)); \\ Antti Karttunen, Nov 27 2024

a(n) = Sum_{d|n} A378442(d). - Antti Karttunen, Nov 27 2024

More terms from Antti Karttunen, Nov 27 2024

A305194 Number of z-forests summing to n. Number of strict integer partitions of n with pairwise indivisible parts and all connected components having clutter density -1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 3, 4, 5, 4, 6, 7, 7, 9, 11, 12, 13, 15, 17, 20, 23, 25, 27, 32, 35, 40, 45, 49, 54, 58, 67, 78, 82, 95, 99, 111, 123, 135, 150, 164, 177, 194, 214, 236, 260, 282, 309, 330

Offset: 1

Gus Wiseman, May 27 2018

Given a finite set S of positive integers greater than 1, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices that have a common divisor greater than 1. For example, G({6,14,15,35}) is a 4-cycle. A set S is said to be connected if G(S) is a connected graph. The clutter density of S is defined to be Sum_{s in S} (omega(s) - 1) - omega(lcm(S)), where omega = A001221 and lcm is least common multiple. Then a z-forest is a strict integer partition with pairwise indivisible parts greater than 1 such that all connected components have clutter density -1.

			The a(17) = 11 z-forests together with the corresponding multiset systems:
       (17): {{7}}
     (15,2): {{2,3},{1}}
     (14,3): {{1,4},{2}}
     (13,4): {{6},{1,1}}
     (12,5): {{1,1,2},{3}}
     (11,6): {{5},{1,2}}
     (10,7): {{1,3},{4}}
      (9,8): {{2,2},{1,1,1}}
   (10,4,3): {{1,3},{1,1},{2}}
    (7,6,4): {{4},{1,2},{1,1}}
  (7,5,3,2): {{4},{3},{2},{1}}

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

Cf. A030019, A048143, A134954, A275307, A285572, A293510, A293993, A293994, A303362, A303837, A303838, A304118, A304382, A305078, 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];
Table[Length[Select[IntegerPartitions[n],Function[s,UnsameQ@@s&&And@@(Length[#]==1||zreeQ[#]&)/@Table[Select[s,Divisible[m,#]&],{m,zsm[s]}]&&Select[Tuples[s,2],UnsameQ@@#&&Divisible@@#&]=={}]]],{n,50}]

A305195 Number of z-blobs summing to n. Number of connected strict integer partitions of n, with pairwise indivisible parts, that cannot be capped by a z-tree.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, May 27 2018

nonn

Caps of a clutter are defined in the link, and the generalization to "multiclutters," where edges can be multisets, is straightforward.

			The a(30) = 2 z-blobs together with the corresponding multiset systems:
     (30): {{1,2,3}}
  (18,12): {{1,2,2},{1,1,2}}
The a(47) = 3 z-blobs together with the corresponding multiset systems:
        (47): {{15}}
  (21,14,12): {{2,4},{1,4},{1,1,2}}
  (20,15,12): {{1,1,3},{2,3},{1,1,2}}
The a(60) = 5 z-blobs together with the corresponding multiset systems:
           (60): {{1,1,2,3}}
        (42,18): {{1,2,4},{1,2,2}}
        (36,24): {{1,1,2,2},{1,1,1,2}}
     (30,18,12): {{1,2,3},{1,2,2},{1,1,2}}
  (21,15,14,10): {{2,4},{2,3},{1,4},{1,3}}
The a(67) = 7 z-blobs together with the corresponding multiset systems:
           (67): {{19}}
     (45,12,10): {{2,2,3},{1,1,2},{1,3}}
     (42,15,10): {{1,2,4},{2,3},{1,3}}
     (40,15,12): {{1,1,1,3},{2,3},{1,1,2}}
     (33,22,12): {{2,5},{1,5},{1,1,2}}
     (28,21,18): {{1,1,4},{2,4},{1,2,2}}
  (24,18,15,10): {{1,1,1,2},{1,2,2},{2,3},{1,3}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Cf. A030019, A048143, A275307, A285572, A293510, A303362, A303837, A303838, A304118, A304382, A304887, A305028, A305078, A305194.

A317101 Numbers whose prime multiplicities are pairwise indivisible.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 21, 22, 23, 25, 26, 27, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 46, 47, 49, 51, 53, 55, 57, 58, 59, 61, 62, 64, 65, 66, 67, 69, 70, 71, 72, 73, 74, 77, 78, 79, 81, 82, 83, 85, 86, 87

Offset: 1

Gus Wiseman, Aug 01 2018

nonn

			72 = 2^3 * 3^2 is in the sequence because 3 and 2 are pairwise indivisible.

Cf. A118914, A124010, A285572, A285573, A303362, A304713, A316475, A317102, A317616.

Select[Range[100],Select[Tuples[Last/@FactorInteger[#],2],And[UnsameQ@@#,Divisible@@#]&]=={}&]

A326082 Number of maximal sets of pairwise indivisible divisors of n.

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 2, 4, 3, 3, 2, 5, 2, 3, 3, 5, 2, 5, 2, 5, 3, 3, 2, 8, 3, 3, 4, 5, 2, 7, 2, 6, 3, 3, 3, 9, 2, 3, 3, 8, 2, 7, 2, 5, 5, 3, 2, 12, 3, 5, 3, 5, 2, 8, 3, 8, 3, 3, 2, 15, 2, 3, 5, 7, 3, 7, 2, 5, 3, 7, 2, 15, 2, 3, 5, 5, 3, 7, 2, 12, 5, 3, 2, 15, 3

Offset: 1

Gus Wiseman, Jun 05 2019

nonn

Depends only on prime signature.

The non-maximal case is A096827.

			The maximal sets of pairwise indivisible divisors of n = 1, 2, 4, 8, 12, 24, 30, 32, 36, 48, 60 are:
   1   1   1   1   1     1      1         1    1       1       1
       2   2   2   12    24     30        2    36      48      60
           4   4   2,3   2,3    5,6       4    2,3     2,3     2,15
               8   3,4   3,4    2,15      8    2,9     3,4     3,20
                   4,6   3,8    3,10      16   3,4     3,8     4,30
                         4,6    2,3,5     32   4,18    4,6     5,12
                         6,8    6,10,15        9,12    6,8     2,3,5
                         8,12                  12,18   3,16    3,4,5
                                               4,6,9   6,16    4,5,6
                                                       8,12    3,4,10
                                                       12,16   6,15,20
                                                       16,24   10,12,15
                                                               12,15,20
                                                               12,20,30
                                                               4,6,10,15

Cf. A001055, A051026, A067992, A096827, A143824, A285572, A285573, A303362, A305148, A305149, A316476, A325861, A326023, A326077.

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[Rest[Subsets[Divisors[n]]],stableQ[#,Divisible]&]]],{n,100}]

A327402 Quotient of n over the maximum stable divisor of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 1, 1, 1, 2, 1, 4, 3, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 1, 1, 2, 1, 4, 1, 2, 3, 5, 1, 6, 1, 4, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 7, 3, 2, 1, 4, 1, 2, 7, 1, 5, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 6, 1, 5, 1, 2, 1, 12, 1, 2, 3, 8, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 8, 3

Offset: 1

Gus Wiseman, Sep 15 2019

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. A number is stable if its distinct prime indices are pairwise indivisible. Stable numbers are listed in A316476.

			The stable divisors of 60 are {1, 2, 3, 4, 5, 15}, so a(60) = 60/15 = 4.

Antti Karttunen, Table of n, a(n) for n = 1..20000
Gus Wiseman, Sequences counting and encoding certain classes of multisets
Index entries for sequences related to prime indices in the factorization of n.

See link for additional cross-references.

Cf. A000005, A033273, A303362, A316476, A327403, A378442.

stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[n/Max[Select[Divisors[n],stableQ[PrimePi/@First/@FactorInteger[#],Divisible]&]],{n,100}]

A378442(n)={my(v=apply(primepi, factor(n)[, 1])); for(j=2, #v, for(i=1, j-1, if(v[j]%v[i]==0, return(0)))); 1}; \\ From the function "ok" in A316476 by Andrew Howroyd, Aug 26 2018
A327402(n) = fordiv(n,d,if(A378442(n/d),return(d))); \\ Antti Karttunen, Jan 28 2025

a(n) = n/A327393(n).

Data section extended to a(105) by Antti Karttunen, Jan 28 2025

A327403 Number of steps to reach a fixed point starting with n and repeatedly taking the quotient by the maximum stable divisor (A327393, A327402).

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2

Offset: 1

Gus Wiseman, Sep 15 2019

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. A number is stable if its distinct prime indices are pairwise indivisible. Stable numbers are listed in A316476. The maximum stable divisor of n is A327393(n).

			We have 798 -> 42 -> 6 -> 2 -> 1, so a(798) = 4.

Antti Karttunen, Table of n, a(n) for n = 1..20000
Gus Wiseman, Sequences counting and encoding certain classes of multisets
Index entries for sequences related to prime indices in the factorization of n.

See link for additional cross-references.
Positions of first appearance of each integer are A325782.
Cf. A000005, A303362, A323014, A327393, A327402.

stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[FixedPointList[#/Max[Select[Divisors[#],stableQ[PrimePi/@First/@FactorInteger[#],Divisible]&]]&,n]]-2,{n,100}]

A327403(n) = for(k=0,oo,my(nextn=A327402(n)); if(nextn==n,return(k)); n = nextn); \\ Antti Karttunen, Jan 28 2025

Data section extended to a(105) by Antti Karttunen, Jan 28 2025

A328678 Number of strict, pairwise indivisible, relatively prime integer partitions of n.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 2, 1, 2, 2, 4, 3, 5, 4, 5, 7, 10, 9, 12, 11, 14, 15, 22, 20, 25, 26, 32, 33, 44, 41, 54, 49, 62, 67, 80, 80, 100, 100, 118, 121, 152, 148, 179, 178, 210, 219, 267, 259, 316, 313, 363, 380, 449, 448, 529, 532, 619, 640, 745, 749, 867, 889

Offset: 1

Gus Wiseman, Oct 30 2019

nonn

Note that pairwise indivisibility implies strictness, but we include "strict" in the name in order to more clearly distinguish it from A328676 = "Number of relatively prime integer partitions of n whose distinct parts are pairwise indivisible".

			The a(1) = 1 through a(20) = 11 partitions (A..H = 10..20) (empty columns not shown):
  1  32  43  53  54  73   65  75   76  95   87   97   98    B7   A9    B9
         52      72  532  74  543  85  B3   B4   B5   A7    D5   B8    D7
                          83  732  94  743  D2   D3   B6    765  C7    H3
                          92       A3  752  654  754  C5    873  D6    875
                                   B2       753  853  D4    954  E5    965
                                                 952  E3    972  F4    974
                                                 B32  F2    B43  G3    A73
                                                      764   B52  H2    B54
                                                      A43   D32  865   B72
                                                      7532       964   D43
                                                                 B53   D52
                                                                 7543

The Heinz numbers of these partitions are the squarefree terms of A328677.
The non-strict case is A328676.
Pairwise indivisible partitions are A303362.
Strict, relatively prime partitions are A078374.
A ranking function using binary indices is A328671.
Cf. A000837, A285572, A285573, A304713, A305148, A316476, A328171.

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

Moebius transform of A303362.

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A318747 Number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and adjacent parts (including the last with the first part) being indivisible (either way).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A327394 Number of stable divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A305194 Number of z-forests summing to n. Number of strict integer partitions of n with pairwise indivisible parts and all connected components having clutter density -1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A305195 Number of z-blobs summing to n. Number of connected strict integer partitions of n, with pairwise indivisible parts, that cannot be capped by a z-tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A317101 Numbers whose prime multiplicities are pairwise indivisible.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A326082 Number of maximal sets of pairwise indivisible divisors of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327402 Quotient of n over the maximum stable divisor of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs