login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A051424 Number of partitions of n into pairwise relatively prime parts. 50
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

REFERENCES

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..400

Temba Shonhiwa, Compositions with pairwise relatively prime summands within a restricted setting, Fibonacci Quart. 44 (2006), no. 4, 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: A163180 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 26 08:39 EDT 2020. Contains 334620 sequences. (Running on oeis4.)