36 lines
1.8 KiB
Plaintext
36 lines
1.8 KiB
Plaintext
The [https://mathworld.wolfram.com/PartitionFunctionP.html 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 = <big>Σ</big>(4) = <big>Σ</big>(3,1) = <big>Σ</big>(2,2) = <big>Σ</big>(2,1,1) = <big>Σ</big>(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 [https://www.youtube.com/channel/UC1_uAIS3r8Vu6JjXWvastJg Mathologer] made the video, [https://www.youtube.com/watch?v=iJ8pnCO0nTY 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:
|
||
* [https://www.youtube.com/watch?v=iJ8pnCO0nTY The hardest "What comes next?" (Euler's pentagonal formula)] The explanatory video by Mathologer that makes this task a popular interest.
|
||
* [https://mathworld.wolfram.com/PartitionFunctionP.html Partition Function P] Mathworld entry for the Partition function.
|
||
* [[wp:Partition_function_(number_theory)|Partition function (number theory)]] Wikipedia entry for the Partition function.
|
||
|
||
|
||
;Related tasks:
|
||
* [[9 billion names of God the integer]]
|
||
|
||
<br><br>
|
||
|
||
|