Partition function P: Difference between revisions
→{{header|Phix}}
(Added Wren) |
|||
Line 161:
<pre>p(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
0.405178 seconds (5.34 M allocations: 114.048 MiB, 13.34% gc time)</pre>
=={{header|Phix}}==
Not exactly super-fast, but this sort of stuff is not really what Phix does best.
<lang Phix>function partDiffDiff(integer n)
return (n+1)/(1+and_bits(n,1))
end function
sequence pd = {1}
function partDiff(integer n)
while n>length(pd) do
pd &= pd[$] + partDiffDiff(length(pd))
end while
return pd[max(1,n)]
end function
include mpfr.e
sequence pn = {mpz_init(1)}
function partitionsP(integer n)
mpz res = mpz_init(1)
while n>length(pn) do
integer nn = length(pn)+1
mpz psum = mpz_init(0)
for i=1 to nn do
integer pd = partDiff(i)
if pd>nn then exit end if
integer sgn = iff(remainder(i-1,4)<2 ? 1 : -1)
mpz pnmpd = partitionsP(nn-pd)
if sgn=-1 then
mpz_sub(psum,psum,pnmpd)
else
mpz_add(psum,psum,pnmpd)
end if
end for
pn = append(pn,psum)
end while
return pn[max(1,n)]
end function
atom t0 = time()
integer n=6666
printf(1,"p(%d) = %s (%s)\n",{n,mpz_get_str(partitionsP(n)),elapsed(time()-t0)})</lang>
{{out}}
<pre>
p(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863 (2.1s)
</pre>
=={{header|REXX}}==
| |||