user
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.

Example

```
 P(4) = 5   because   4 = Σ(4) = Σ(3,1) = Σ(2,2) = Σ(2,1,1) = Σ(1,1,1,1)

```

P(n) can be expressed as the recurrence relation:

```
 P(n) = P(n-1) +P(n-2) -P(n-5) -P(n-7) +P(n-12) +P(n-15) -P(n-22) -P(n-26) +P(n-35) +P(n-40) ...

```

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.

Task

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).

References

* The hardest "What comes next?" (Euler's pentagonal formula) The explanatory video by Mathologer that makes this task a popular interest.
* Partition Function P Mathworld entry for the Partition function.
* Partition function (number theory) Wikipedia entry for the Partition function.

Related tasks

* 9 billion names of God the integer
assistant
**Works with**: Rakudo version 2020.09

Not the fastest, but it gets the job done.

```
my @P = 1, { p(++$) } … *;
my @i = lazy [\+] flat 1, ( 1..* Z (1..*).map: * × 2 + 1 );
sub p ($n) { sum @P[$n X- @i] Z× (flat (1, 1, -1, -1) xx *) }

put @P[^26];
put @P[6666];

```

Output:

```
1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958
193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
```