login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A051424 Number of partitions of n into pairwise relatively prime parts. 47
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 * A137606 A320224 A239468

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 April 23 02:15 EDT 2019. Contains 322380 sequences. (Running on oeis4.)