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

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, 45, 55, 65, 69, 66, 64, 75, 86, 100, 113, 107, 106, 122, 145, 165, 174, 167, 162, 179, 222, 253, 255, 255, 255, 273, 328, 373, 376, 369, 377, 406, 476, 553, 569, 537, 529

Offset: 1

Author

N. J. A. Sloane and Mira Bernstein, following a suggestion from Marc LeBrun

Keywords

• nonn
• easy

Examples

			From _Gus Wiseman_, Sep 23 2019: (Start)
The a(1) = 1 through a(10) = 6 partitions (A = 10):
  (1)  (2)  (3)   (4)   (5)   (6)    (7)   (8)    (9)    (A)
            (21)  (31)  (32)  (51)   (43)  (53)   (54)   (73)
                        (41)  (321)  (52)  (71)   (72)   (91)
                                     (61)  (431)  (81)   (532)
                                           (521)  (531)  (541)
                                                         (721)
(End)
		

References

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

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 1..750 (terms 1..350 from Alois P. Heinz)
• M. LeBrun & D. Hoey, Emails

Crossrefs

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

The non-strict case is A051424.

Strict relatively prime partitions are A078374.

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

Programs

Mathematica

$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, #Jean-François Alcover, Mar 20 2014, after Alois P. Heinz *)
Table[Length[Select[IntegerPartitions[n],Length[#]==1||UnsameQ@@#&&CoprimeQ@@Union[#]&]],{n,0,30}] (* Gus Wiseman, Sep 23 2019 *)

Formula

a(n) = A051424(n)-A051424(n-2). - Vladeta Jovovic, Dec 11 2004

Extensions

More precise definition from Vladeta Jovovic, Dec 11 2004

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