cp's OEIS Frontend

A007360 Number of partitions of n into distinct and pairwise relatively prime parts.

%I A007360 M0264 #37 Jul 08 2025 17:03:44
%S A007360 1,1,2,2,3,3,4,5,5,6,8,9,10,11,10,13,17,19,21,22,21,24,32,37,37,38,40,
%T A007360 45,55,65,69,66,64,75,86,100,113,107,106,122,145,165,174,167,162,179,
%U A007360 222,253,255,255,255,273,328,373,376,369,377,406,476,553,569,537,529
%N A007360 Number of partitions of n into distinct and pairwise relatively prime parts.
%D A007360 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007360 Fausto A. C. Cariboni, <a href="/A007360/b007360.txt">Table of n, a(n) for n = 1..750</a> (terms 1..350 from Alois P. Heinz)
%H A007360 M. LeBrun & D. Hoey, <a href="/A007359/a007359.pdf">Emails</a>
%F A007360 a(n) = A051424(n)-A051424(n-2). - _Vladeta Jovovic_, Dec 11 2004
%e A007360 From _Gus Wiseman_, Sep 23 2019: (Start)
%e A007360 The a(1) = 1 through a(10) = 6 partitions (A = 10):
%e A007360   (1)  (2)  (3)   (4)   (5)   (6)    (7)   (8)    (9)    (A)
%e A007360             (21)  (31)  (32)  (51)   (43)  (53)   (54)   (73)
%e A007360                         (41)  (321)  (52)  (71)   (72)   (91)
%e A007360                                      (61)  (431)  (81)   (532)
%e A007360                                            (521)  (531)  (541)
%e A007360                                                          (721)
%e A007360 (End)
%t A007360 $RecursionLimit = 1000; b[n_, i_, s_] := b[n, i, s] = Module[{f}, If[n == 0 || i == 1, 1, If[i<2, 0, f = FactorInteger[i][[All, 1]]; b[n, i-1, Select[s, #<i&]] + If[i <= n && f ~Intersection~ s == {}, b[n-i, i-1, Select[s ~Union~ f, #<i&]], 0]]]]; a[n_] := b[n, n, {}] - b[n-2, n-2, {}]; Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, Mar 20 2014, after _Alois P. Heinz_ *)
%t A007360 Table[Length[Select[IntegerPartitions[n],Length[#]==1||UnsameQ@@#&&CoprimeQ@@Union[#]&]],{n,0,30}] (* _Gus Wiseman_, Sep 23 2019 *)
%Y A007360 Number of partitions of n into relatively prime parts = A000837.
%Y A007360 The non-strict case is A051424.
%Y A007360 Strict relatively prime partitions are A078374.
%Y A007360 Cf. A007359, A038348, A084422, A186974, A187106, A303140, A302569, A303362, A304714, A320426, A320436.
%K A007360 nonn,easy
%O A007360 1,3
%A A007360 _N. J. A. Sloane_ and _Mira Bernstein_, following a suggestion from _Marc LeBrun_
%E A007360 More precise definition from _Vladeta Jovovic_, Dec 11 2004
%E A007360 More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 13 2005