cp's OEIS Frontend

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

%I A051424 #48 Jan 05 2025 19:51:36
%S A051424 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 A051424 153,171,191,211,236,266,301,335,367,399,442,485,542,598,649,704,771,
%U A051424 849,936,1023,1103,1185,1282,1407,1535,1662,1790,1917,2063,2245,2436
%N A051424 Number of partitions of n into pairwise relatively prime parts.
%H A051424 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 A051424 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 A051424 Temba Shonhiwa, <a href="https://web.archive.org/web/2024*/https://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 A051424 log a(n) ~ (2*Pi/sqrt(6)) sqrt(n/log n). - _Eric M. Schmidt_, Jul 04 2013
%F A051424 Apparently no formula or recurrence is known. - _N. J. A. Sloane_, Mar 05 2017
%e A051424 a(4) = 4 since all partitions of 4 consist of relatively prime numbers except 2+2.
%e A051424 The a(6) = 7 partitions with pairwise coprime parts: (111111), (21111), (3111), (321), (411), (51), (6). - _Gus Wiseman_, Apr 14 2018
%p A051424 with(numtheory):
%p A051424 b:= proc(n, i, s) option remember; local f;
%p A051424       if n=0 or i=1 then 1
%p A051424     elif i<2 then 0
%p A051424     else f:= factorset(i);
%p A051424          b(n, i-1, select(x->is(x<i), s))+`if`(i<=n and f intersect s={},
%p A051424          b(n-i, i-1, select(x->is(x<i), s union f)), 0)
%p A051424       fi
%p A051424     end:
%p A051424 a:= n-> b(n, n, {}):
%p A051424 seq(a(n), n=0..80);  # _Alois P. Heinz_, Mar 14 2012
%t A051424 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 A051424 (Haskell)
%o A051424 a051424 = length . filter f . partitions where
%o A051424    f [] = True
%o A051424    f (p:ps) = (all (== 1) $ map (gcd p) ps) && f ps
%o A051424    partitions n = ps 1 n where
%o A051424      ps x 0 = [[]]
%o A051424      ps x y = [t:ts | t <- [x..y], ts <- ps t (y - t)]
%o A051424 -- _Reinhard Zumkeller_, Dec 16 2013
%Y A051424 Number of partitions of n into relatively prime parts = A000837.
%Y A051424 Row sums of A282749.
%Y A051424 Cf. A000837, A007359, A007360, A051424, A289509, A298748, A302569, A302696, A302797.
%K A051424 nonn
%O A051424 0,3
%A A051424 _Hugo van der Sanden_
%E A051424 More precise definition from _Vladeta Jovovic_, Dec 11 2004