sidef-scripts/Math/partition_function.sf

#!/usr/bin/ruby

# A recursive algorithm for computing the partition p(n) function.

# See also:
#   https://rosettacode.org/wiki/Partition_function_P
#   https://en.wikipedia.org/wiki/Partition_(number_theory)#Partition_function

func partitionsP(n) {
    func (n) is cached {

        n <= 1 && return n

        var a = sum(1..floor((sqrt(24*n + 1) + 1)/6), {|k|
            (-1)**(k-1) * __FUNC__(n - ((k*(3*k - 1)) >> 1))
        })

        var b = sum(1..ceil((sqrt(24*n + 1) - 7)/6), {|k|
            (-1)**(k-1) * __FUNC__(n - ((k*(3*k + 1)) >> 1))
        })

        a + b
    }(n+1)
}

say partitionsP.map(0..20)  #=> [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627]
say partitionsP(200)        #=> 3972999029388