login
Number of partitions of n into pairwise relatively prime parts.
98

%I #46 Dec 31 2020 17:25:04

%S 1,1,2,3,4,6,7,10,12,15,18,23,27,33,38,43,51,60,70,81,92,102,116,134,

%T 153,171,191,211,236,266,301,335,367,399,442,485,542,598,649,704,771,

%U 849,936,1023,1103,1185,1282,1407,1535,1662,1790,1917,2063,2245,2436

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

%H Fausto A. C. Cariboni, <a href="/A051424/b051424.txt">Table of n, a(n) for n = 0..750</a> (terms 0..400 from Alois P. Heinz)

%H Eric Schmutz, <a href="https://doi.org/10.1016/0012-365X(90)90181-G">Partitions whose parts are pairwise relatively prime</a>, Discrete Math. 81(1) (1990), 87-89.

%H Temba Shonhiwa, <a href="http://www.fq.math.ca/Papers1/44-4/quarttemba04_2006.pdf">Compositions with pairwise relatively prime summands within a restricted setting</a>, Fibonacci Quart. 44(4) (2006), 316-323.

%F log a(n) ~ (2*Pi/sqrt(6)) sqrt(n/log n). - _Eric M. Schmidt_, Jul 04 2013

%F Apparently no formula or recurrence is known. - _N. J. A. Sloane_, Mar 05 2017

%e a(4) = 4 since all partitions of 4 consist of relatively prime numbers except 2+2.

%e The a(6) = 7 partitions with pairwise coprime parts: (111111), (21111), (3111), (321), (411), (51), (6). - _Gus Wiseman_, Apr 14 2018

%p with(numtheory):

%p b:= proc(n, i, s) option remember; local f;

%p if n=0 or i=1 then 1

%p elif i<2 then 0

%p else f:= factorset(i);

%p b(n, i-1, select(x->is(x<i), s))+`if`(i<=n and f intersect s={},

%p b(n-i, i-1, select(x->is(x<i), s union f)), 0)

%p fi

%p end:

%p a:= n-> b(n, n, {}):

%p seq(a(n), n=0..80); # _Alois P. Heinz_, Mar 14 2012

%t 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_ *)

%o (Haskell)

%o a051424 = length . filter f . partitions where

%o f [] = True

%o f (p:ps) = (all (== 1) $ map (gcd p) ps) && f ps

%o partitions n = ps 1 n where

%o ps x 0 = [[]]

%o ps x y = [t:ts | t <- [x..y], ts <- ps t (y - t)]

%o -- _Reinhard Zumkeller_, Dec 16 2013

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

%Y Row sums of A282749.

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

%K nonn

%O 0,3

%A _Hugo van der Sanden_

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