

The Partition Function P, often notated P(n) is the number of solutions where n∈ℤ can be expressed as the sum of a set of 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 has been viewed more than 100,000 times in the first couple of weeks since 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




/*REXX program calculates and displays a specific value (or a range of)  partitionsP(N).*/
numeric digits 1000                              /*able to handle some ginormous numbers*/
parse arg lo hi .                                /*obtain optional arguments from the CL*/
if lo=='' | lo==","  then lo=  0                 /*Not specified?  Then use the default.*/
if hi=='' | hi==","  then hi= lo                 /* "      "         "   "   "     "    */
@.= 0;    @.0= 1; @.1= 1; @.2= 2; @.3= 3; @.4= 5 /*assign default value and low values. */
!.= @.;   !.1= 1; !.3= 1; !.5= 1; !.7= 1; !.9= 1 /*assign default value and even digits.*/
w= length( commas(hi) )                          /*W:  is used for aligning the index.  */
 
       do j=lo  to hi                            /*compute a range of  partitionsP.     */
       say right( commas(j), w)    ' '     commas( partP(j) )
       end   /*j*/
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?;  do jc=length(?)-3  to 1  by -3; ?=insert(',', ?, jc); end;  return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
partP:  procedure expose @. !.;  parse arg n     /*obtain number (index) for computation*/
        if @.n\==0  then return @.n              /*Is it already computed?   Return it. */
        #= 0                                               /*initialize part  P  number.*/
               do k=1  for n;  z= n  -  (k*3 - 1) * k % 2  /*compute the partition P num*/
               if z<0  then leave                          /*Is Z negative?  Then leave.*/
               if @.z==0  then x= partP(z)                 /*use recursion if not known.*/
                          else x= @.z                      /*use the pre─computed number*/
               z= z - k                                    /*subtract index (K) from Z. */
               if z<0     then y= 0                        /*Is Z negative? Then set Y=0*/
                          else if @.z==0  then y= partP(z) /*use recursion if not known.*/
                                          else y= @.z      /*use the pre─computed number*/
               if k//2    then #= # +  x + y               /*Odd? Then   sum    X and Y.*/
                          else #= # - (x + y)              /*Even?  "  subtract "  "  " */
               end   /*k*/
        @.n= #;                   return #       /*define and return partitionsP of  N. */