Partition function P: Difference between revisions
→{{header|jq}}: Recursive
m (added sum_partitions/1 for better readability) |
(→{{header|jq}}: Recursive) |
||
Line 677:
The user+sys time is 7m3s as the BigInt.jq library is written in jq.
== Recursive ==
{{trans|Julia}} with memoization
<lang jq>def partDiffDiff($n):
if ($n % 2) == 1 then ($n+1) / 2 else $n+1 end;
# in: {n, partDiffMemo}
# out: object with possibly updated memoization
def partDiff:
.n as $n
| if .partDiffMemo[$n] then .
elif $n<2 then .partDiffMemo[$n]=1
else ((.n=($n-1)) | partDiff)
| .partDiffMemo[$n] = .partDiffMemo[$n-1] + partDiffDiff($n-1)
end;
# in: {n, memo, partDiffMemo}
# where `.memo[i]` memoizes partitions(i)
# and `.partDiffMemo[i]` memoizes partDiff(i)
# out: object with possibly updated memoization
def partitionsM:
.n as $n
| if .memo[$n] then .
elif $n<2 then .memo[$n] = 1
else label $out
| foreach range(1; $n+2) as $i (.emit = false | .psum = 0;
if $i > $n then .emit = true
else ((.n = $i) | partDiff)
| .partDiffMemo[$i] as $pd
| if $pd > $n then .emit=true, break $out
else {psum, emit} as $local # for restoring relevant state
| ((.n = ($n-$pd)) | partitionsM)
| .memo[$n-$pd] as $increment
| . + $local # restore
| if (($i-1)%4)<2
then .psum += $increment
else .psum -= $increment
end
end
end;
select(.emit) )
| .memo[$n] = .psum
end ;
def partitionsP:
. as $n
| {n: $n, memo:[], partDiffMemo:[]}
| partitionsM
| .memo[$n];
</lang>
Using gojq, `6666 | partitionsP` produces
<pre>
193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
</pre>
=={{header|Julia}}==
| |||