%I #28 May 10 2021 07:40:34
%S 0,0,0,0,1,0,3,2,5,4,13,7,23,18,32,33,65,50,104,92,148,153,252,226,
%T 376,376,544,570,846,821,1237,1276,1736,1869,2552,2643,3659,3887,5067,
%U 5509,7244,7672,10086,10909,13756,15168,19195,20735,26237,28708,35418,39207
%N Number of integer partitions of n into relatively prime parts that are all greater than 1.
%C Two or more numbers are relatively prime if they have no common divisor other than 1. A single number is not considered relatively prime unless it is equal to 1 (which is impossible in this case).
%C The Heinz numbers of these partitions are given by A302697.
%H Alois P. Heinz, <a href="/A302698/b302698.txt">Table of n, a(n) for n = 1..1000</a>
%F a(n) = A002865(n) - A018783(n).
%e The a(5) = 1 through a(12) = 7 partitions (empty column indicated by dot):
%e (32) . (43) (53) (54) (73) (65) (75)
%e (52) (332) (72) (433) (74) (543)
%e (322) (432) (532) (83) (552)
%e (522) (3322) (92) (732)
%e (3222) (443) (4332)
%e (533) (5322)
%e (542) (33222)
%e (632)
%e (722)
%e (3332)
%e (4322)
%e (5222)
%e (32222)
%p b:= proc(n, i, g) option remember; `if`(n=0, `if`(g=1, 1, 0),
%p `if`(i<2, 0, b(n, i-1, g)+b(n-i, min(n-i, i), igcd(g, i))))
%p end:
%p a:= n-> b(n$2, 0):
%p seq(a(n), n=1..60); # _Alois P. Heinz_, Apr 12 2018
%t Table[Length[Select[IntegerPartitions[n],FreeQ[#,1]&&GCD@@#===1&]],{n,30}]
%t (* Second program: *)
%t b[n_, i_, g_] := b[n, i, g] = If[n == 0, If[g == 1, 1, 0], If[i < 2, 0, b[n, i - 1, g] + b[n - i, Min[n - i, i], GCD[g, i]]]];
%t a[n_] := b[n, n, 0];
%t Array[a, 60] (* _Jean-François Alcover_, May 10 2021, after _Alois P. Heinz_ *)
%Y A000837 is the version allowing 1's.
%Y A002865 does not require relative primality.
%Y A302697 gives the Heinz numbers of these partitions.
%Y A337450 is the ordered version.
%Y A337451 is the ordered strict version.
%Y A337452 is the strict version.
%Y A337485 is the pairwise coprime instead of relatively prime version.
%Y A000740 counts relatively prime compositions.
%Y A078374 counts relatively prime strict partitions.
%Y A212804 counts compositions with no 1's.
%Y A291166 appears to rank relatively prime compositions.
%Y A332004 counts strict relatively prime compositions.
%Y A337561 counts pairwise coprime strict compositions.
%Y A338332 is the case of length 3, with strict case A338333.
%Y Cf. A007359, A018783, A051424, A101268, A289508, A289509, A302568, A337563, A337984, A338468.
%K nonn
%O 1,7
%A _Gus Wiseman_, Apr 11 2018
%E Extended by _Gus Wiseman_, Oct 29 2020