A365382 Number of relatively prime integer partitions with sum < n that cannot be linearly combined using nonnegative coefficients to obtain n.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 4, 4, 2, 4, 12, 8, 20, 11, 14, 26, 43, 19, 38, 53, 51, 48, 101, 48, 124, 96, 121, 159, 134, 103, 241, 261, 244, 175, 401, 229, 488, 358, 328

Offset: 0

Author

Gus Wiseman, Sep 08 2023

Keywords

• nonn
• more

Examples

			The a(11) = 2 through a(18) = 8 partitions:
  (5,4)  .  (6,5)  (6,5)   (7,6)  (7,5)   (7,4)     (7,5)
  (7,3)     (7,4)  (8,5)   (9,4)  (7,6)   (7,6)     (8,7)
            (7,5)  (9,4)          (9,5)   (8,5)     (10,7)
            (8,3)  (10,3)         (11,3)  (8,7)     (11,4)
                                          (9,5)     (11,5)
                                          (9,7)     (12,5)
                                          (10,3)    (13,4)
                                          (11,4)    (7,5,5)
                                          (11,5)
                                          (13,3)
                                          (7,4,4)
                                          (10,3,3)
		

Crossrefs

Relatively prime partitions are counted by A000837, ranks A289509.

This is the relatively prime case of A365378.

A000041 counts integer partitions, strict A000009.

A008284 counts partitions by length, strict A008289.

A116861 and A364916 count linear combinations of strict partitions.

A364350 counts combination-free strict partitions, non-strict A364915.

A364839 counts combination-full strict partitions, non-strict A364913.

Cf. A007359, A289508, A364345, A365073, A365312, A365379, A365380, A365383.

Programs

Mathematica

combsu[n_,y_]:=With[{s=Table[{k,i},{k,Union[y]},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Join@@IntegerPartitions/@Range[n-1],GCD@@#==1&&combsu[n,#]=={}&]],{n,0,20}]

Python

from math import gcd
from sympy.utilities.iterables import partitions
def A365382(n):
    a = {tuple(sorted(set(p))) for p in partitions(n)}
    return sum(1 for m in range(1,n) for b in partitions(m) if gcd(*b.keys()) == 1 and not any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023

Extensions

a(21)-a(45) from Chai Wah Wu, Sep 13 2023