Strict partitions of a positive integer

Question

OEIS A000009 counts the number of strict partitions of the integers. A strict partition of a nonnegative integer n is a set of positive integers (so no repetition is allowed, and order does not matter) that sum to n.

For example, 5 has three strict partitions: 5, 4,1, and 3,2.

10 has ten partitions:

10
9,1
8,2
7,3
6,4
7,2,1
6,3,1
5,4,1
5,3,2
4,3,2,1

Challenge

Given a nonnegative integer n<1000, output the number of strict partitions it has.

Test cases:

0 -> 1

42 -> 1426

Here is a list of the strict partition numbers from 0 to 55, from OEIS:

[1,1,1,2,2,3,4,5,6,8,10,12,15,18,22,27,32,38,46,54,64,76,89,104,122,142,165,192,222,256,296,340,390,448,512,585,668,760,864,982,1113,1260,1426,1610,1816,2048,2304,2590,2910,3264,3658,4097,4582,5120,5718,6378]

This is code-golf, so the shortest solution in bytes wins.

Answer 1

Pyth, 7 bytes

l{I#./Q

Try it online. Test suite.

• Take the input (Q).
• Find its partitions (./).
• Filter it (#) on uniquify ({) not changing (I) the partition. This removes partitions with duplicates.
• Find the result's length (l).

Answer 2

Mathematica, 11 bytes

PartitionsQ

---

Test case

PartitionsQ@Range[10]
(* {1,1,2,2,3,4,5,6,8,10} *)

Answer 3

Python 2, 49 bytes

f=lambda n,k=1:n/k and f(n-k,k+1)+f(n,k+1)or n==0

The recursion branches at every potential summand k from 1 to n to decide whether it should be included. Each included summand is subtracted from the desired sum n, and at the end, if n=0 remains, that path is counted.

Answer 4

Haskell, 39 bytes

f n=sum[1|x<-mapM(:[0])[1..n],sum x==n]

The function (:[0]) converts a number k to the list [k,0]. So,

mapM(:[0])[1..n]

computes the Cartesian product of [1,0],[2,0],...,[n,0], which gives all subsets of [1..n] with 0's standing for omitted elements. The strict partitions of n correspond to such lists with sum n. Such elements are counted by a list comprehension, which is shorter than length.filter.

Answer 5

ES6, 64 bytes

f=(n,k=0)=>[...Array(n)].reduce((t,_,i)=>n-i>i&i>k?t+f(n-i,i):t,1)

Works by recursive trial subtraction. k is the number that was last subtracted, and the next number to be subtracted must be larger (but not so large that an even larger number cannot be subtracted). 1 is added because you can always subtract n itself. (Also since this is recursive I have to take care that all of my variables are local.)

Answer 6

Python, 68 bytes

p=lambda n,d=0:sum(p(n-k,n-2*k+1)for k in range(1,n-d+1))if n else 1

Just call the anonymous function passing the nonnegative integer n as argument... and wait the end of the universe.

Answer 7

05AB1E, 5 bytes

LæOQO

Try it online!

Note: this is extremely slow and will timeout for inputs greater than about 20.

Explanation:

L         # range 1..input
 æ        # list of subsets
  O       # sum each subset
   Q      # equal? (1 for each sum that equals the input, 0 otherwise)
    O     # sum the booleans

Answer 8

Haskell, 58 bytes

import Data.List
h x=sum[1|i<-subsequences[1..x],sum i==x]

Usage example: map h [0..10] -> [1,1,1,2,2,3,4,5,6,8,10].

It's a simple brute-force approach. Check the sums of all subsequences of 1..x. This works for x == 0, too, because all subsequences of [1..0] are [[]] and the sum of [] is 0.

Answer 9

Haskell, 43 bytes

0%0=1
_%0=0
n%k=n%(k-1)+(n-k)%(k-1)
f n=n%n

The binary function n%k counts the number of strict partitions of n into parts with a maximum part k, so the desired function is f n=n%n. Each value k can be included, which decreases n by k, or excluded, and either way the new maximum k is one lower, giving the recursion n%k=n%(k-1)+(n-k)%(k-1).

Answer 10

Vyxal l, 24 bits^v2, 3 bytes

Ṅ'Þu

Try it Online!

Vyxal forever

Answer 11

Julia, 53 bytes

n->endof(collect(filter(p->p==∪(p),partitions(n))))

This is an anonymous function that accepts an integer and returns an integer. To call it, assign it to a variable.

We get the integer partitions using partitions, filter to only those with distinct summands, collect into an array, and find the last index (i.e. the length) using endof.

Answer 12

05AB1E, 8 bytes

ÅœʒDÙQ}g

Try it online or verify all test cases.

Explanation:

Ŝ          # Get all integer partitions of the (implicit) input
            #  i.e. 5 → [[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3],[5]]
  ʒ   }     # Filter by:
   D        #  Duplicate the current partition
    Ù       #  Uniquify (removing any duplicated values from) this copied partition
            #   i.e. [1,1,1,1,1] → [1]
            #   i.e. [1,4] → [1,4]
     Q      #  Check if it's still the same
            #   i.e. [1,1,1,1,1] and [1] → 0 (falsey)
            #   i.e. [1,4] and [1,4] → 1 (truthy)
       g    # Then take the length of the filtered list (and implicitly output it)
            #  i.e. [[1,4],[2,5],[5]] → 3