A051424 Number of partitions of n into pairwise relatively prime parts.

1, 1, 2, 3, 4, 6, 7, 10, 12, 15, 18, 23, 27, 33, 38, 43, 51, 60, 70, 81, 92, 102, 116, 134, 153, 171, 191, 211, 236, 266, 301, 335, 367, 399, 442, 485, 542, 598, 649, 704, 771, 849, 936, 1023, 1103, 1185, 1282, 1407, 1535, 1662, 1790, 1917, 2063, 2245, 2436

Offset

0,3

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..750 (terms 0..400 from Alois P. Heinz)

Eric Schmutz, Partitions whose parts are pairwise relatively prime, Discrete Math. 81(1) (1990), 87-89.

Temba Shonhiwa, Compositions with pairwise relatively prime summands within a restricted setting, Fibonacci Quart. 44(4) (2006), 316-323.

Formula

log a(n) ~ (2*Pi/sqrt(6)) sqrt(n/log n). - Eric M. Schmidt, Jul 04 2013

Apparently no formula or recurrence is known. - N. J. A. Sloane, Mar 05 2017

Example

a(4) = 4 since all partitions of 4 consist of relatively prime numbers except 2+2.
The a(6) = 7 partitions with pairwise coprime parts: (111111), (21111), (3111), (321), (411), (51), (6). - Gus Wiseman, Apr 14 2018

Maple

with(numtheory):
b:= proc(n, i, s) option remember; local f;
      if n=0 or i=1 then 1
    elif i<2 then 0
    else f:= factorset(i);
         b(n, i-1, select(x->is(x<i), s))+`if`(i<=n and f intersect s={},
         b(n-i, i-1, select(x->is(x<i), s union f)), 0)
      fi
    end:
a:= n-> b(n, n, {}):
seq(a(n), n=0..80);  # Alois P. Heinz, Mar 14 2012

Mathematica

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, {}]; Table[a[n], {n, 0, 54}] (* Jean-François Alcover, Oct 03 2013, translated from Maple, after Alois P. Heinz *)

Prog

(Haskell)
a051424 = length . filter f . partitions where
   f [] = True
   f (p:ps) = (all (== 1) $ map (gcd p) ps) && f ps
   partitions n = ps 1 n where
     ps x 0 = [[]]
     ps x y = [t:ts | t <- [x..y], ts <- ps t (y - t)]
-- Reinhard Zumkeller, Dec 16 2013

Crossrefs

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

Row sums of A282749.

Cf. A000837, A007359, A007360, A051424, A289509, A298748, A302569, A302696, A302797.

Sequence in context: A341270 A091515 A036405 * A308632 A137606 A320224

Adjacent sequences: A051421 A051422 A051423 * A051425 A051426 A051427

Keyword

nonn

Author

Hugo van der Sanden

Extensions

More precise definition from Vladeta Jovovic, Dec 11 2004

Status

approved