Partition function P: Difference between revisions
added an implementation in Julia
(Task to compute the number of partitions of a natural number.) |
(added an implementation in Julia) |
||
Line 22:
* [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.
=={{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>
| |||