12345678910111213141516171819202122232425262728 |
- #!/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
|