Problem Statement

The Partition Function P is the function P(n), where n∈ℤ, defined as the number of distinct ways in which n can be expressed as the sum of non-increasing positive integers.

P(n) can be expressed as the recurrence relation: The successive numbers in the above equation have the differences:   1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, 15, 8 ... This task may be of popular interest because Mathologer made the video, The hardest "What comes next?" (Euler's pentagonal formula), where he asks the programmers among his viewers to calculate P(666). The video was viewed more than 100,000 times in the first couple of weeks after its release. In Wolfram Language, this function has been implemented as PartitionsP.

Write a function which returns the value of PartitionsP(n). Solutions can be iterative or recursive. Bonus task: show how long it takes to compute PartitionsP(6666).

Let's start with the solution:

import sequtils, strformat, times
import bignum

func partitions(n: int): Int =
  var p = newSeqWith(n + 1, newInt())
  p[0] = newInt(1)
  for i in 1..n:
    var k = 1
    while true:
      var j = k * (3 * k - 1) div 2
      if j > i: break
      if (k and 1) != 0:
        inc p[i], p[i - j]
      else:
        dec p[i], p[i - j]
      j = k * (3 * k + 1) div 2
      if j > i: break
      if (k and 1) != 0:
        inc p[i], p[i - j]
      else:
        dec p[i], p[i - j]
      inc k
  result = p[n]

let t0 = cpuTime()
echo partitions(6666)
echo &"Elapsed time: {(cpuTime() - t0) * 1000:.2f} ms"