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

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

Author

Gus Wiseman, Oct 06 2020

Keywords

• nonn

Comments

Number of pairwise non-coprime strict compositions of n.

Examples

			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
		

Crossrefs

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.

Programs

Mathematica

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