A337562 -id:A337562 - cp's OEIS frontend

A337695 Numbers k such that the distinct parts of the k-th composition in standard order (A066099) are not pairwise coprime, where a singleton is always considered coprime.

34, 40, 69, 70, 81, 88, 98, 104, 130, 138, 139, 141, 142, 160, 162, 163, 168, 177, 184, 197, 198, 209, 216, 226, 232, 260, 261, 262, 274, 276, 277, 278, 279, 282, 283, 285, 286, 288, 290, 296, 321, 324, 325, 326, 327, 328, 337, 344, 352, 354, 355, 360, 369

Offset: 1

Gus Wiseman, Sep 22 2020

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The sequence together with the corresponding compositions begins:
     34: (4,2)        163: (2,4,1,1)    277: (4,2,2,1)
     40: (2,4)        168: (2,2,4)      278: (4,2,1,2)
     69: (4,2,1)      177: (2,1,4,1)    279: (4,2,1,1,1)
     70: (4,1,2)      184: (2,1,1,4)    282: (4,1,2,2)
     81: (2,4,1)      197: (1,4,2,1)    283: (4,1,2,1,1)
     88: (2,1,4)      198: (1,4,1,2)    285: (4,1,1,2,1)
     98: (1,4,2)      209: (1,2,4,1)    286: (4,1,1,1,2)
    104: (1,2,4)      216: (1,2,1,4)    288: (3,6)
    130: (6,2)        226: (1,1,4,2)    290: (3,4,2)
    138: (4,2,2)      232: (1,1,2,4)    296: (3,2,4)
    139: (4,2,1,1)    260: (6,3)        321: (2,6,1)
    141: (4,1,2,1)    261: (6,2,1)      324: (2,4,3)
    142: (4,1,1,2)    262: (6,1,2)      325: (2,4,2,1)
    160: (2,6)        274: (4,3,2)      326: (2,4,1,2)
    162: (2,4,2)      276: (4,2,3)      327: (2,4,1,1,1)

Gus Wiseman, Statistics, classes, and transformations of standard compositions

A304712 counts the complement, with ordered version A337664.
A333228 ranks compositions whose distinct parts are pairwise coprime.
A335238 does not consider a singleton coprime unless it is (1).
A337600 counts 3-part partitions in the complement.
A000740 counts relatively prime compositions.
A051424 counts pairwise coprime or singleton partitions.
A101268 counts pairwise coprime or singleton compositions.
A327516 counts pairwise coprime partitions.
A333227 ranks pairwise coprime compositions.
A337461 counts pairwise coprime 3-part compositions.
A337561 counts pairwise coprime strict compositions.
A337665 counts compositions whose distinct parts are pairwise coprime.
A337666 ranks pairwise non-coprime compositions.
Cf. A007359, A007360, A087087, A302569, A302696, A304709, A305713, A335235, A337562, A337601, A337602, A337603.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],!(SameQ@@stc[#]||CoprimeQ@@Union[stc[#]])&]

A337983 Number of compositions of n into distinct parts, any two of which have a common divisor > 1.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 3, 1, 3, 3, 5, 1, 13, 1, 13, 7, 19, 1, 35, 1, 59, 15, 65, 1, 117, 5, 133, 27, 195, 1, 411, 7, 435, 67, 617, 17, 941, 7, 1177, 135, 1571, 13, 2939, 31, 3299, 375, 4757, 13, 6709, 43, 8813, 643, 11307, 61, 16427, 123, 24331, 1203, 30461, 67

Offset: 0

Gus Wiseman, Oct 06 2020

nonn

Number of pairwise non-coprime strict compositions of n.

			The a(2) = 1 through a(15) = 7 compositions (A..F = 10..15):
  2  3  4  5  6   7  8   9   A   B  C    D  E    F
              24     26  36  28     2A      2C   3C
              42     62  63  46     39      4A   5A
                             64     48      68   69
                             82     84      86   96
                                    93      A4   A5
                                    A2      C2   C3
                                    246     248
                                    264     284
                                    426     428
                                    462     482
                                    624     824
                                    642     842

A318717 is the unordered version.
A318719 is the version for Heinz numbers of partitions.
A337561 is the pairwise coprime instead of pairwise non-coprime version, or A337562 if singletons are considered coprime.
A337605*6 counts these compositions of length 3.
A337667 is the non-strict version, ranked by A337666.
A337696 ranks these compositions.
A051185 and A305843 (covering) count pairwise intersecting set-systems.
A101268 counts pairwise coprime or singleton compositions.
A200976 and A328673 are the unordered version.
A233564 ranks strict compositions.
A318749 is the version for factorizations, with non-strict version A319786.
A333228 ranks compositions whose distinct parts are pairwise coprime.
A335236 ranks compositions neither a singleton nor pairwise coprime.
A337462 counts pairwise coprime compositions.
A337694 lists numbers with no two relatively prime prime indices.
Cf. A082024, A284825, A302797, A305713, A319752, A327516, A333227, A335235, A336737, A337604.

stabQ[u_,Q_]:=And@@Not/@Q@@@Tuples[u,2];
Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],UnsameQ@@#&&stabQ[#,CoprimeQ]&]],{n,0,30}]

A282748 Triangle read by rows: T(n,k) is the number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_i, x_j) = 1 for all i != j (where 1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 4, 3, 4, 1, 1, 2, 9, 4, 5, 1, 1, 6, 3, 16, 5, 6, 1, 1, 4, 15, 4, 25, 6, 7, 1, 1, 6, 9, 28, 5, 36, 7, 8, 1, 1, 4, 21, 16, 45, 6, 49, 8, 9, 1, 1, 10, 9, 52, 25, 66, 7, 64, 9, 10, 1, 1, 4, 39, 16, 105, 36, 91, 8, 81, 10, 11, 1, 1, 12, 9, 100, 25, 186, 49, 120, 9, 100, 11, 12, 1, 1, 6, 45, 16, 205, 36, 301, 64, 153, 10, 121, 12, 13, 1

Offset: 1

N. J. A. Sloane, Mar 05 2017

See A101391 for the triangle T(n,k) = number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1,x_2,...,x_k) = 1 (2 <= k <= n).

			Triangle begins:
  1;
  1,  1;
  1,  2,  1;
  1,  2,  3,   1;
  1,  4,  3,   4,   1;
  1,  2,  9,   4,   5,   1;
  1,  6,  3,  16,   5,   6,  1;
  1,  4, 15,   4,  25,   6,  7,   1;
  1,  6,  9,  28,   5,  36,  7,   8,  1;
  1,  4, 21,  16,  45,   6, 49,   8,  9,   1;
  1, 10,  9,  52,  25,  66,  7,  64,  9,  10,  1;
  1,  4, 39,  16, 105,  36, 91,   8, 81,  10, 11,  1;
  1, 12,  9, 100,  25, 186, 49, 120,  9, 100, 11, 12, 1;
  ...
From _Gus Wiseman_, Nov 12 2020: (Start)
Row n = 6 counts the following compositions:
  (6)  (15)  (114)  (1113)  (11112)  (111111)
       (51)  (123)  (1131)  (11121)
             (132)  (1311)  (11211)
             (141)  (3111)  (12111)
             (213)          (21111)
             (231)
             (312)
             (321)
             (411)
(End)

Alois P. Heinz, Rows n = 1..200, flattened (first 100 rows from Chai Wah Wu)
Temba Shonhiwa, Compositions with pairwise relatively prime summands within a restricted setting, Fibonacci Quart. 44 (2006), no. 4, 316-323.

A072704 counts the unimodal instead of coprime version.
A087087 and A335235 rank these compositions.
A101268 gives row sums.
A101391 is the relatively prime instead of pairwise coprime version.
A282749 is the unordered version.
A000740 counts relatively prime compositions, with strict case A332004.
A007360 counts pairwise coprime or singleton strict partitions.
A051424 counts pairwise coprime or singleton partitions, ranked by A302569.
A097805 counts compositions by sum and length.
A178472 counts compositions with a common divisor.
A216652 and A072574 count strict compositions by sum and length.
A305713 counts pairwise coprime strict partitions.
A327516 counts pairwise coprime partitions, ranked by A302696.
A335235 ranks pairwise coprime or singleton compositions.
A337462 counts pairwise coprime compositions, ranked by A333227.
A337562 counts pairwise coprime or singleton strict compositions.
A337665 counts compositions whose distinct parts are pairwise coprime, ranked by A333228.
Cf. A000837, A007359, A302568, A337461, A337561, A337667.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{k}],Length[#]==1||CoprimeQ@@#&]],{n,10},{k,n}] (* Gus Wiseman, Nov 12 2020 *)

It seems that no general formula or recurrence is known, although Shonhiwa gives formulas for a few of the early diagonals.

A337696 Numbers k such that the k-th composition in standard order (A066099) is strict and pairwise non-coprime, meaning the parts are distinct and any two of them have a common divisor > 1.

Original entry on oeis.org

0, 2, 4, 8, 16, 32, 34, 40, 64, 128, 130, 160, 256, 260, 288, 512, 514, 520, 544, 640, 1024, 2048, 2050, 2052, 2056, 2082, 2088, 2176, 2178, 2208, 2304, 2560, 2568, 2592, 4096, 8192, 8194, 8200, 8224, 8226, 8232, 8320, 8704, 8706, 8832, 10240, 10248, 10368

Offset: 1

Gus Wiseman, Oct 06 2020

nonn

Differs from A291165 in having 1090535424, corresponding to the composition (6,10,15).

			The sequence together with the corresponding compositions begins:
       0: ()        512: (10)       2304: (3,9)
       2: (2)       514: (8,2)      2560: (2,10)
       4: (3)       520: (6,4)      2568: (2,6,4)
       8: (4)       544: (4,6)      2592: (2,4,6)
      16: (5)       640: (2,8)      4096: (13)
      32: (6)      1024: (11)       8192: (14)
      34: (4,2)    2048: (12)       8194: (12,2)
      40: (2,4)    2050: (10,2)     8200: (10,4)
      64: (7)      2052: (9,3)      8224: (8,6)
     128: (8)      2056: (8,4)      8226: (8,4,2)
     130: (6,2)    2082: (6,4,2)    8232: (8,2,4)
     160: (2,6)    2088: (6,2,4)    8320: (6,8)
     256: (9)      2176: (4,8)      8704: (4,10)
     260: (6,3)    2178: (4,6,2)    8706: (4,8,2)
     288: (3,6)    2208: (4,2,6)    8832: (4,2,8)

Gus Wiseman, Statistics, classes, and transformations of standard compositions

A318719 gives the Heinz numbers of the unordered version, with non-strict version A337694.
A337667 counts the non-strict version.
A337983 counts these compositions, with unordered version A318717.
A051185 counts intersecting set-systems, with spanning case A305843.
A200976 and A328673 count the unordered non-strict version.
A337462 counts pairwise coprime compositions.
A318749 counts pairwise non-coprime factorizations, with strict case A319786.
All of the following pertain to compositions in standard order (A066099):
- A000120 is length.
- A070939 is sum.
- A124767 counts runs.
- A233564 ranks strict compositions.
- A272919 ranks constant compositions.
- A333219 is Heinz number.
- A333227 ranks pairwise coprime compositions, or A335235 if singletons are considered coprime.
- A333228 ranks compositions whose distinct parts are pairwise coprime.
- A335236 ranks compositions neither a singleton nor pairwise coprime.
- A337561 is the pairwise coprime instead of pairwise non-coprime version, or A337562 if singletons are considered coprime.
- A337666 ranks the non-strict version.
Cf. A082024, A101268, A302797, A305713, A319752, A327040, A327516, A336737, A337599, A337604, A337605.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
stabQ[u_,Q_]:=And@@Not/@Q@@@Tuples[u,2];
Select[Range[0,1000],UnsameQ@@stc[#]&&stabQ[stc[#],CoprimeQ]&]

Intersection of A337666 and A233564.

cp's OEIS Frontend

A337695 Numbers k such that the distinct parts of the k-th composition in standard order (A066099) are not pairwise coprime, where a singleton is always considered coprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A337983 Number of compositions of n into distinct parts, any two of which have a common divisor > 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A282748 Triangle read by rows: T(n,k) is the number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_i, x_j) = 1 for all i != j (where 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A337696 Numbers k such that the k-th composition in standard order (A066099) is strict and pairwise non-coprime, meaning the parts are distinct and any two of them have a common divisor > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula