login
Number of partitions of n into distinct and pairwise relatively prime parts.
(Formerly M0264)
47

%I M0264 #33 Dec 31 2020 17:23:45

%S 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 45,55,65,69,66,64,75,86,100,113,107,106,122,145,165,174,167,162,179,

%U 222,253,255,255,255,273,328,373,376,369,377,406,476,553,569,537,529

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

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H 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 M. LeBrun & D. Hoey, <a href="/A007359/a007359.pdf">Emails</a>

%F a(n) = A051424(n)-A051424(n-2). - _Vladeta Jovovic_, Dec 11 2004

%e From _Gus Wiseman_, Sep 23 2019: (Start)

%e The a(1) = 1 through a(10) = 6 partitions (A = 10):

%e (1) (2) (3) (4) (5) (6) (7) (8) (9) (A)

%e (21) (31) (32) (51) (43) (53) (54) (73)

%e (41) (321) (52) (71) (72) (91)

%e (61) (431) (81) (532)

%e (521) (531) (541)

%e (721)

%e (End)

%t $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 Table[Length[Select[IntegerPartitions[n],Length[#]==1||UnsameQ@@#&&CoprimeQ@@Union[#]&]],{n,0,30}] (* _Gus Wiseman_, Sep 23 2019 *)

%Y Number of partitions of n into relatively prime parts = A000837.

%Y The non-strict case is A051424.

%Y Strict relatively prime partitions are A078374.

%Y Cf. A007359, A038348, A084422, A186974, A187106, A303140, A302569, A303362, A304714, A320426, A320436.

%K nonn,easy

%O 1,3

%A _N. J. A. Sloane_ and _Mira Bernstein_, following a suggestion from _Marc LeBrun_.

%E More precise definition from _Vladeta Jovovic_, Dec 11 2004

%E More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 13 2005