A365382 - OEIS

A365382

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

%I #17 Sep 13 2023 14:16:53

%S 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,

%T 101,48,124,96,121,159,134,103,241,261,244,175,401,229,488,358,328

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

%e The a(11) = 2 through a(18) = 8 partitions:

%e (5,4) . (6,5) (6,5) (7,6) (7,5) (7,4) (7,5)

%e (7,3) (7,4) (8,5) (9,4) (7,6) (7,6) (8,7)

%e (7,5) (9,4) (9,5) (8,5) (10,7)

%e (8,3) (10,3) (11,3) (8,7) (11,4)

%e (9,5) (11,5)

%e (9,7) (12,5)

%e (10,3) (13,4)

%e (11,4) (7,5,5)

%e (11,5)

%e (13,3)

%e (7,4,4)

%e (10,3,3)

%t combsu[n_,y_]:=With[{s=Table[{k,i},{k,Union[y]},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];

%t Table[Length[Select[Join@@IntegerPartitions/@Range[n-1],GCD@@#==1&&combsu[n,#]=={}&]],{n,0,20}]

%o (Python)

%o from math import gcd

%o from sympy.utilities.iterables import partitions

%o def A365382(n):

%o a = {tuple(sorted(set(p))) for p in partitions(n)}

%o 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

%Y Relatively prime partitions are counted by A000837, ranks A289509.

%Y This is the relatively prime case of A365378.

%Y A000041 counts integer partitions, strict A000009.

%Y A008284 counts partitions by length, strict A008289.

%Y A116861 and A364916 count linear combinations of strict partitions.

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

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

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

%K nonn,more

%O 0,12

%A _Gus Wiseman_, Sep 08 2023

%E a(21)-a(45) from _Chai Wah Wu_, Sep 13 2023