A338553 Number of integer partitions of n that are either constant or relatively prime.

1, 1, 2, 3, 5, 7, 10, 15, 20, 29, 37, 56, 68, 101, 122, 170, 213, 297, 352, 490, 587, 778, 948, 1255, 1488, 1953, 2337, 2983, 3585, 4565, 5393, 6842, 8123, 10088, 12015, 14865, 17534, 21637, 25527, 31085, 36701, 44583, 52262, 63261, 74175, 88936, 104305, 124754

Offset

0,3

Comments

The Heinz numbers of these partitions are given by A338555 = A000961 \/ A289509. The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.

Links

Table of n, a(n) for n=0..47.

Formula

For n > 0, a(n) = A000005(n) + A000837(n) - 1.

Example

The a(1) = 1 through a(7) = 15 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (21)   (22)    (32)     (33)      (43)
             (111)  (31)    (41)     (51)      (52)
                    (211)   (221)    (222)     (61)
                    (1111)  (311)    (321)     (322)
                            (2111)   (411)     (331)
                            (11111)  (2211)    (421)
                                     (3111)    (511)
                                     (21111)   (2221)
                                     (111111)  (3211)
                                               (4111)
                                               (22111)
                                               (31111)
                                               (211111)
                                               (1111111)

Mathematica

Table[Length[Select[IntegerPartitions[n], SameQ@@#||GCD@@#==1&]], {n, 0, 30}]

Crossrefs

A023022(n) + A059841(n) is the 2-part version.

A078374(n) + 1 is the strict case (n > 1).

A338554 counts the complement, with Heinz numbers A338552.

A338555 gives the Heinz numbers of these partitions.

A000005 counts constant partitions, with Heinz numbers A000961.

A000837 counts relatively prime partitions, with Heinz numbers A289509.

A282750 counts relatively prime partitions by sum and length.

Cf. A000010, A007360, A008284, A023023, A051424, A101271, A101391, A302698, A304712, A327516, A337664.

Sequence in context: A022475 A330937 A011972 * A272402 A321176 A240573

Adjacent sequences: A338550 A338551 A338552 * A338554 A338555 A338556

Keyword

nonn

Author

Gus Wiseman, Nov 03 2020

Status

approved