|
%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
|
