Count of relatively prime partitions

Question

The partitions of an integer N are all the combinations of integers smaller than or equal to N and higher than 0 which sum up to N.

A relatively prime partition is an integer partition, but whose elements are (overall) coprime; or in other words, there is no integer greater than 1 which divides all of the parts.

Task

Given an integer as input, your task is to output the count of relatively prime partitions it has. Rather not surprised that there is an OEIS sequence for this. The aim is to shorten your code as much as possible, with usual code golf rules.

Also, you don't have to worry about memory errors. Your algorithm must only theoretically work for an arbitrarily big values of N, but it is fine if your language has certain limitations. You can assume that N will always be at least 1.

Test cases and Example

Let's take 5 as an example. Its integer partitions are:

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

From this, the first 6 only are relatively prime partitions. Note that the last one (formed by the integer in question only) must not be taken into account as a relatively prime partition (except for N=1) because its GCD is N.

N -> Output

1  -> 1
2  -> 1
3  -> 2
4  -> 3
5  -> 6
6  -> 7
7  -> 14
8  -> 17
9  -> 27
10 -> 34

Answer 1

JavaScript (ES6), 130 120 bytes

f=(n,d=n)=>d&&(n%d?0:(M=n=>n%++k?k>n||M(n):n/k%k&&-M(n/k))(n/d,k=1)*(P=n=>!k|n<0?0:n?P(n,k--)+P(n-++k):1)(k=d))+f(n,d-1)

Demo

f=(n,d=n)=>d&&(n%d?0:(M=n=>n%++k?k>n||M(n):n/k%k&&-M(n/k))(n/d,k=1)*(P=n=>!k|n<0?0:n?P(n,k--)+P(n-++k):1)(k=d))+f(n,d-1)

for(n = 1; n <= 30; n++) {
  console.log('a(' + n + ') = ' + f(n))
}

How?

This is recursively computing:

     /                  \     /                   \
    |  (M = n =>         |   |  (P = n =>          |
    |    n % ++k ?       |   |    !k | n < 0 ?     |
    |      k > n ||      |   |      0              |
    |      M(n)          |   |    :                |
sum |    :               | * |      n ?            | for d in divisors(n)
    |      n / k % k &&  |   |        P(n, k--) +  |
    |      - M(n / k)    |   |        P(n - ++k)   |
    |  )(n / d, k = 1)   |   |      :              |
    |                    |   |        1            |
    |                    |   |  )(k = d)           |
     \                  /     \                   /
        Möbius(n / d)            npartitions(d)

Answer 2

Pyth, 7 bytes

/iM./Q1

Test suite.

Explanation

/iM./Q1  | Full program.
         |
   ./Q   | The integer partitions (./) of the evaluated input (Q).
 iM      | Get the GCD (i) of each (M).
/     1  | Count (/) the 1's (1).

Pyth's behaviour comes in handy, since mapping with a 2-argument function automatically folds the command on the list, and the GCD of a one-element list is the element itself, so we don't have to handle that separately.

Answer 3

Pari/GP, 39 bytes

This sequence (A000837) is the Möbius transform of the partition numbers (A000041).

n->sumdiv(n,d,moebius(n/d)*numbpart(d))

Try it online!

Answer 4

Wolfram Language (Mathematica), 35 bytes

Count[GCD@@@IntegerPartitions@#,1]&

Try it online!

This is my first Mathematica submission. Thanks to alephalpha for -4 bytes!

Answer 5

Jelly, 7 bytes

Œṗg/€ċ1

Try it online!

Answer 6

Swift, 202 185 bytes

Saved 17 bytes thanks to @Mr.Xcoder

func p(_ n:Int,_ m:[Int]=[])->[[Int]]{return 0<n ?(1...min(m.last ?? n,n)).flatMap{p(n-$0,m+[$0])}:[m]}
{n in n>1 ?p(n).filter{a in !(2...n).contains{m in !a.contains{$0%m>0}}}.count:1}

Try it online!

Explanation

func p(_ n:Int,_ m:[Int]=[])->[[Int]]{// Recursive helper function p where p(n, prefix) is
                                      // a list of all possiblie partitions of n
  return n > 0 ?                      // If n > 0:
    (1 ... min(m.last ?? n, n))       //   For i in range from 1 to min(n, last value in prefix):
      .flatMap{p(n - $0, m + [$0])}   //     Add p(n - i, prefix + i) to the return list
  :                                   // Else:
    [m]                               //   Return just the prefix
}                                      
{n in                                 // Main function:
  n > 1 ?                             // If n > 1:
    p(n).filter {a in                 //   Take the list of possible partitions of n where
      !(2...n).contains{m in          //   there is no integer m in the range from 2 to n where
        !a.contains{$0%m>0}           //   all elements in the partitioning divide m
      }
    }.count                           //   and return the length of the list
  :                                   // Else (if n == 1):
    1}                                //   Return 1