Partition function P: Difference between revisions
(Task to compute the number of partitions of a natural number.) |
(added an implementation in Julia) |
||
| Line 22: | Line 22: | ||
* [https://mathworld.wolfram.com/PartitionFunctionP.html Partition Function P] Mathworld entry for the Partition function. |
* [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. |
* [[wp:Partition_function_(number_theory)|Partition function (number theory)]] Wikipedia entry for the Partition function. |
||
=={{header|Julia}}== |
|||
===Recursive=== |
|||
<lang Julia>using Memoize |
|||
function partDiffDiff(n::Int)::Int |
|||
isodd(n) ? (n+1)÷2 : n+1 |
|||
end |
|||
@memoize function partDiff(n::Int)::Int |
|||
n<2 ? 1 : partDiff(n-1)+partDiffDiff(n-1) |
|||
end |
|||
@memoize function partitionsP(n::Int) |
|||
T=BigInt |
|||
if n<2 |
|||
one(T) |
|||
else |
|||
psum = zero(T) |
|||
for i ∈ 1:n |
|||
pd = partDiff(i) |
|||
if pd>n |
|||
break |
|||
end |
|||
sign = ((i-1)%4)<2 ? 1 : -1 |
|||
psum += sign*partitionsP(n-pd) |
|||
end |
|||
psum |
|||
end |
|||
end |
|||
n=6666 |
|||
@time println("p($n) = ", partitionsP(n))</lang> |
|||
{{out}} |
|||
<pre>p(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863 |
|||
0.405178 seconds (5.34 M allocations: 114.048 MiB, 13.34% gc time)</pre> |
|||
Revision as of 11:29, 28 October 2020
You are encouraged to solve this task according to the task description, using any language you may know.
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. For 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.
Julia
Recursive
<lang Julia>using Memoize
function partDiffDiff(n::Int)::Int
isodd(n) ? (n+1)÷2 : n+1
end
@memoize function partDiff(n::Int)::Int
n<2 ? 1 : partDiff(n-1)+partDiffDiff(n-1)
end
@memoize function partitionsP(n::Int)
T=BigInt
if n<2
one(T)
else
psum = zero(T)
for i ∈ 1:n
pd = partDiff(i)
if pd>n
break
end
sign = ((i-1)%4)<2 ? 1 : -1
psum += sign*partitionsP(n-pd)
end
psum
end
end
n=6666 @time println("p($n) = ", partitionsP(n))</lang>
- Output:
p(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863 0.405178 seconds (5.34 M allocations: 114.048 MiB, 13.34% gc time)