cp's OEIS Frontend

A302698 Number of integer partitions of n into relatively prime parts that are all greater than 1.

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