Partition function P: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|FreeBASIC}}: fix then integer version and added then big number version) |
m (→{{header|Wren}}: Minor tidy) |
||
| (36 intermediate revisions by 16 users not shown) | |||
Line 3:
The [https://mathworld.wolfram.com/PartitionFunctionP.html Partition Function P]
Line 15:
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
In Wolfram Language, this function has been implemented as PartitionsP.
Line 41:
{{trans|Python: Alternative}}
<
V p = [BigInt(1)] [+] [BigInt(0)] * n
L(i) 1 .. n
Line 67:
V start = time:perf_counter()
print(partitions(6666))
print(time:perf_counter() - start)</
{{out}}
Line 78:
=={{header|C}}==
{{libheader|GMP}}
<
#include <stdlib.h>
#include <stdio.h>
Line 114:
(double)(clock() - start) / (double)CLOCKS_PER_SEC);
return 0;
}</
{{out}}
Line 121:
Elapsed time: 0.0136 seconds
</pre>
=={{header|C#|CSharp}}==
This can also be done using BigIntegers, but will take around five times longer. Since only adding and subtracting are required, some simple routines can be created to handle the tabulations. Also note that detecting odd and even numbers on each loop iteration is avoided by coding four increments per loop.
<syntaxhighlight lang="csharp">using System;
class Program {
const long Lm = (long)1e18;
const string Fm = "D18";
// provides 5 x 18 = 90 decimal digits
struct LI { public long lo, ml, mh, hi, tp; }
static void inc(ref LI d, LI s) { // d += s
if ((d.lo += s.lo) >= Lm) { d.ml++; d.lo -= Lm; }
if ((d.ml += s.ml) >= Lm) { d.mh++; d.ml -= Lm; }
if ((d.mh += s.mh) >= Lm) { d.hi++; d.mh -= Lm; }
if ((d.hi += s.hi) >= Lm) { d.tp++; d.hi -= Lm; }
d.tp += s.tp;
}
static void dec(ref LI d, LI s) { // d -= s
if ((d.lo -= s.lo) < 0) { d.ml--; d.lo += Lm; }
if ((d.ml -= s.ml) < 0) { d.mh--; d.ml += Lm; }
if ((d.mh -= s.mh) < 0) { d.hi--; d.mh += Lm; }
if ((d.hi -= s.hi) < 0) { d.tp--; d.hi += Lm; }
d.tp -= s.tp;
}
static LI set(long s) { LI d;
d.lo = s; d.ml = d.mh = d.hi = d.tp = 0; return d; }
static string fmt(LI x) { // returns formatted string value of x
if (x.tp > 0) return x.tp.ToString() + x.hi.ToString(Fm) + x.mh.ToString(Fm) + x.ml.ToString(Fm) + x.lo.ToString(Fm);
if (x.hi > 0) return x.hi.ToString() + x.mh.ToString(Fm) + x.ml.ToString(Fm) + x.lo.ToString(Fm);
if (x.mh > 0) return x.mh.ToString() + x.ml.ToString(Fm) + x.lo.ToString(Fm);
if (x.ml > 0) return x.ml.ToString() + x.lo.ToString(Fm);
return x.lo.ToString();
}
static LI partcount(int n) {
var P = new LI[n + 1]; P[0] = set(1);
for (int i = 1; i <= n; i++) {
int k = 0, d = -2, j = i;
LI x = set(0);
while (true) {
if ((j -= (d += 3) -k) >= 0) inc(ref x, P[j]); else break;
if ((j -= ++k) >= 0) inc(ref x, P[j]); else break;
if ((j -= (d += 3) -k) >= 0) dec(ref x, P[j]); else break;
if ((j -= ++k) >= 0) dec(ref x, P[j]); else break;
}
P[i] = x;
}
return P[n];
}
static void Main(string[] args) {
var sw = System.Diagnostics.Stopwatch.StartNew ();
var res = partcount(6666); sw.Stop();
Console.Write("{0} {1} ms", fmt(res), sw.Elapsed.TotalMilliseconds);
}
}</syntaxhighlight>
{{out}}
<pre>193655306161707661080005073394486091998480950338405932486880600467114423441282418165863 12.9365 ms</pre>
Timing from Tio.run.
=={{header|C++}}==
===GMP version===
{{libheader|GMP}}
<
#include <iostream>
#include <vector>
Line 162 ⟶ 228:
std::cout << result << '\n';
std::cout << "elapsed time: " << ms.count() << " milliseconds\n";
}</
{{out}}
Line 169 ⟶ 235:
elapsed time: 8.99497 milliseconds
</pre>
===Non GMP version===
{{trans|C#}}
<syntaxhighlight lang="cpp">#include <chrono>
#include <iostream>
using namespace std;
using namespace chrono;
const long long Lm = (long)1e18;
const int Fm = 18;
struct LI { long long lo, ml, mh, hi, tp; };
LI set(long long s) { LI d;
d.lo = s; d.ml = d.mh = d.hi = d.tp = 0; return d; }
void inc(LI& d, LI s) { // d += s
if ((d.lo += s.lo) >= Lm) { d.ml++; d.lo -= Lm; }
if ((d.ml += s.ml) >= Lm) { d.mh++; d.ml -= Lm; }
if ((d.mh += s.mh) >= Lm) { d.hi++; d.mh -= Lm; }
if ((d.hi += s.hi) >= Lm) { d.tp++; d.hi -= Lm; }
d.tp += s.tp;
}
void dec(LI& d, LI s) { // d -= s
if ((d.lo -= s.lo) < 0) { d.ml--; d.lo += Lm; }
if ((d.ml -= s.ml) < 0) { d.mh--; d.ml += Lm; }
if ((d.mh -= s.mh) < 0) { d.hi--; d.mh += Lm; }
if ((d.hi -= s.hi) < 0) { d.tp--; d.hi += Lm; }
d.tp -= s.tp;
}
inline string sf(long long n) {
int len = Fm;
string result(len--, '0');
for (long long i = n; len >= 0 && i > 0; --len, i /= 10)
result[len] = '0' + i % 10;
return result;
}
string fmt(LI x) { // returns formatted string value of x
if (x.tp > 0) return to_string(x.tp) + sf(x.hi) + sf(x.mh) + sf(x.ml) + sf(x.lo);
if (x.hi > 0) return to_string(x.hi) + sf(x.mh) + sf(x.ml) + sf(x.lo);
if (x.mh > 0) return to_string(x.mh) + sf(x.ml) + sf(x.lo);
if (x.ml > 0) return to_string(x.ml) + sf(x.lo);
return to_string(x.lo);
}
LI partcount(int n) { LI p[n + 1]; p[0] = set(1);
for (int i = 1; i <= n; i++) {
int k = 0, d = -2, j = i; LI x = set(0); while (true) {
if ((j -= (d += 3) - k) >= 0) inc(x, p[j]); else break;
if ((j -= ++k) >= 0) inc(x, p[j]); else break;
if ((j -= (d += 3) - k) >= 0) dec(x, p[j]); else break;
if ((j -= ++k) >= 0) dec(x, p[j]); else break;
} p[i] = x; } return p[n]; }
int main() {
auto start = steady_clock::now();
auto result = partcount(6666);
auto end = steady_clock::now();
duration<double, milli> ms(end - start);
cout << fmt(result) << " " << ms.count() << " ms";
}</syntaxhighlight>
{{out}}
Timing from Tio.run, but execution time can't be directly compared to the GMP version, as GMP isn't accessible at Tio.run.
<pre>193655306161707661080005073394486091998480950338405932486880600467114423441282418165863 7.32706 ms</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
Line 174 ⟶ 309:
{{libheader| System.Diagnostics}}
{{Trans|Go}}
<syntaxhighlight lang="delphi">
program Partition_function_P;
Line 243 ⟶ 378:
writeln('Took ', stopwatch.ElapsedMilliseconds, 'ms');
Readln;
end.</
{{out}}
<pre>p[6666] = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
Took 131ms</pre>
=={{header|Elixir}}==
Loosely based on the Erlang version.
<syntaxhighlight lang="elixir">
use Bitwise, skip_operators: true
defmodule Partition do
def init(), do:
:ets.new :pN, [:set, :named_table, :private]
def gpentagonals(), do: Stream.unfold {1, 0}, &next/1
defp next({m, n}) do
a = case rem m, 2 do
0 -> div m, 2
1 -> m
end
{n, {m + 1, n + a}}
end
def p(0), do: 1
def p(n) do
case :ets.lookup :pN, n do
[{^n, val}] -> val
[] ->
{val, _} = gpentagonals()
|> Stream.drop(1)
|> Stream.take_while(fn m -> m <= n end)
|> Stream.map(fn g -> p(n - g) end)
|> Enum.reduce({0, 0},
fn n, {a, sgn} -> {
a + (if sgn < 2, do: n, else: -n),
band(sgn + 1, 3)
}
end)
:ets.insert :pN, {n, val}
val
end
end
end
Partition.init
IO.puts Partition.p 6666
</syntaxhighlight>
{{Out}}
<pre>
$ time ./partition6666.ex
193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
real 0m1.106s
user 0m1.191s
sys 0m0.116s
</pre>
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">
-mode(compile).
Line 262 ⟶ 449:
[] ->
Terms = [p(N - G) || G <- gpentagonals(N)],
Pn = sum_partitions(Terms
ets:insert(pN, {N, Pn}),
Pn
end.
sum_partitions(Terms) -> sum_partitions(Terms, 0, 0).
sum_partitions([], _, Sum) -> Sum;
sum_partitions([N|Ns], Sgn, Sum) ->
Line 285 ⟶ 473:
true -> gpentagonals(M + 1, Max, [GP|Ps])
end.
</syntaxhighlight>
{{Out}}
<pre>
Line 295 ⟶ 483:
sys 0m0.080s
</pre>
=={{header|F_Sharp|F#}}==
An implementation of the formula in the task description. P(123456) is included for comparison with the largest value in the related task.
<
// PartionP: Nigel Galloway. April 12th., 2021
let pP g=let rec fN i g e l=seq{yield(l,e+i);yield(-l,e+i+g);yield! fN(i+1)(g+2)(e+i+g)(-l)}
let N,G=Array.create(g+1) 1I,seq{yield (1I,1);yield! fN 1 3 1 1I}|>Seq.takeWhile(fun(_,n)->n<=g)|>List.ofSeq
seq{2..g}|>Seq.iter(fun p->N.[p]<-G|>List.takeWhile(fun(_,n)->n<=p)|>Seq.fold(fun Σ (n,g)->Σ+n*N.[p-g]) 0I); N.[g]
printfn "666->%A\n\n6666->%A\n\n123456->%A" (pP 666)
</syntaxhighlight>
{{out}}
<pre>
Line 316 ⟶ 505:
=={{header|Factor}}==
{{works with|Factor|0.99 2020-08-14}}
<
! Compute the nth pentagonal number.
Line 338 ⟶ 527:
: partitions ( m -- n )
[ seq swap [ <= ] curry lwhile list>array ]
[ V{ 1 } clone swap [ step ] times last nip ] bi ;</
{{out}}
<pre>
Line 352 ⟶ 541:
===Unsiged 64bit version===
{{trans|Python}}
<
' if n > 416, the result becomes to large for a unsigned 64bit integer
Dim As ULongInt p(n)
Line 388 ⟶ 577:
Print !"\n\ndone"
Sleep</
{{out}}
<pre>PartitionsP: 1 1 2 3 5 7 11 15 22 30 42 56 77</pre>
Line 395 ⟶ 584:
{{libheader|GMP}}
[https://rosettacode.org/wiki/9_billion_names_of_God_the_integer#FreeBASIC From the 9_billion_names_of_God_the_integer entry]
<
' compile with: fbc -s console
Line 457 ⟶ 646:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>PartitionsP(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
time = 32.97 ms</pre>
=={{header|Frink}}==
Frink has a built-in function for counting partitions that uses Euler's pentagonal method. It works for arbitrarily-large integers and caches results.
<syntaxhighlight lang="frink">println[partitionCount[6666]]</syntaxhighlight>
{{out}}
<pre>
193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
</pre>
=={{header|Go}}==
{{trans|Julia}}
I also tried using Euler's generating function but it was about 20 times slower than this version.
<
import (
Line 523 ⟶ 720:
fmt.Printf("p[%d)] = %d\n", N, p[N])
fmt.Printf("Took %s\n", time.Since(start))
}</
{{out}}
Line 532 ⟶ 729:
=={{header|Java}}==
<
public class PartitionFunction {
Line 567 ⟶ 764:
return p[n];
}
}</
{{out}}
Line 574 ⟶ 771:
elapsed time: 59 milliseconds
</pre>
=={{header|JavaScript}}==
<syntaxhighlight lang="javascript">
function p(n){
var a = new Array(n+1)
a[0] = 1n
for (let i = 1; i <= n; i++){
a[i] = 0n
for (let k = 1, s = 1; s <= i;){
a[i] += (k & 1 ? a[i-s]:-a[i-s])
k > 0 ? (s += k, k = -k):(k = -k+1, s = k*(3*k-1)/2)
}
}
return a[n]
}
var t = Date.now()
console.log("p(6666) = " + p(6666))
console.log("Computation time in ms: ", Date.now() - t)
</syntaxhighlight>
{{out}}
<pre>
p(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
Computation time in ms: 26
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">{-# LANGUAGE DeriveFunctor #-}
------------------------------------------------------------
-- memoization utilities
data Memo a = Node a (Memo a) (Memo a)
deriving (Functor)
memo :: Integral a => Memo p -> a -> p
memo (Node a l r) n
| n == 0 = a
| odd n = memo l (n `div` 2)
| otherwise = memo r (n `div` 2 - 1)
nats :: Memo Int
nats =
Node
0
((+ 1) . (* 2) <$> nats)
((* 2) . (+ 1) <$> nats)
------------------------------------------------------------
-- calculating partitions
partitions :: Memo Integer
partitions = partitionP <$> nats
partitionP :: Int -> Integer
partitionP n
| n < 2 = 1
| otherwise = sum $ zipWith (*) signs terms
where
terms =
[ memo partitions (n - i)
| i <- takeWhile (<= n) ofsets
]
signs = cycle [1, 1, -1, -1]
ofsets :: [Int]
ofsets = scanl1 (+) $ mix [1, 3 ..] [1, 2 ..]
where
mix a b = concat $ zipWith (\x y -> [x, y]) a b
main :: IO ()
main = print $ partitionP 6666</syntaxhighlight>
<pre>*Main> partitionP <$> [1..10]
[1,2,3,5,7,11,15,22,30,42]
*Main> partitionP 100
190569292
*Main> partitionP 1000
24061467864032622473692149727991
*Main> partitionP 6666
193655306161707661080005073394486091998480950338405932486880600467114423441282418165863</pre>
=={{header|J}}==
Solution stolen [https://code.jsoftware.com/wiki/Essays/Partitions#The_Number_of_Partitions verbatim from the J Wiki]. Note the use of memoization (M.) for efficiency:
<syntaxhighlight lang="j"> pn =: -/@(+/)@:($:"0)@rec ` (x:@(0&=)) @. (0>:]) M.
rec=: - (-: (*"1) _1 1 +/ 3 * ]) @ (>:@i.@>.@%:@((2%3)&*))</syntaxhighlight>
{{out}}
<pre> pn 6
11
pn 66
2323520
pn 666
11956824258286445517629485
pn 6666
193655306161707661080005073394486091998480950338405932486880600467114423441282418165863</pre>
=={{header|jq}}==
Translation of: Python:Alternative
<syntaxhighlight lang="jq">def partitions($n):
def div2: (. - (.%2)) / 2;
reduce range(1; $n + 1) as $i ( {p: ([1] + [range(0;$n)|0])};
. + {k: 0, stop: false}
| until(.stop;
.k += 1
| (((.k * (3*.k - 1)) | div2) ) as $j
| if $j > $i then .stop=true
else if (.k % 2) == 1
then .p[$i] = .p[$i] + .p[$i - $j]
else .p[$i] = .p[$i] - .p[$i - $j]
end
| (((.k * (3*.k + 1)) | div2)) as $j
| if $j > $i then .stop=true
elif (.k % 2) == 1
then .p[$i] = .p[$i] + .p[$i - $j]
else .p[$i] = .p[$i] - .p[$i - $j]
end
end ))
| .p[$n] ;
[partitions(range(1;15))]</syntaxhighlight>
{{out}}
<pre>[1,2,3,5,7,11,15,22,30,42,56,77,101,135]</pre>
Using gojq 0.12.11, `partitions(6666)` yields (in about 12 minutes (u+s) on a 3GHz machine):
193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
The integer precision of the C implementation of jq is insufficient for computing ``partitions(6666)``, but as a test
of the BigInt.jq library for jq, here are the results of using it in conjunction
with a trivially-modified version of the ''partitions'' implementation above. That is, after
modifying the lines that refer to "p" (or ".p"), we see that ''partitions(6666)'' yields:
"193655306161707661080005073394486091998480950338405932486880600467114423441282418165863"
Curiously, the u+s time is 7m3s, which is significantly less than the above-mentioned gojq time, even though the BigInt library is written in jq.
=== Recursive ===
{{trans|Julia}} with memoization
<syntaxhighlight 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];
# Stretch goal:
6666 | partitionsP
</syntaxhighlight>
Using gojq, the above program takes 41.35 seconds (u+s) on a 3GHz Mac Mini to produce:<pre>
193655306161707661080005073394486091998480950338405932486880600467114423441282418165863</pre>
=={{header|Julia}}==
===Recursive===
<
function partDiffDiff(n::Int)::Int
Line 609 ⟶ 1,008:
n=6666
@time println("p($n) = ", partitionsP(n))</
{{out}}
<pre>p(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
0.260310 seconds (3.58 M allocations: 77.974 MiB, 8.54% gc time)</pre>
=={{header|Lingo}}==
Lingo natively only supports 32 bit integers, so P(6666) would be way too big.
<syntaxhighlight lang="lingo">-- returns number of partitions of n
on partitions(n, res_table)
if n < 2 then return 1
if voidP(res_table) then
res_table = []
res_table[n] = 0
else if res_table[n] then
return res_table[n]
end if
res = 0
i = 0
param = 1
repeat while param <= n
if i mod 4 < 2 then
res = res + partitions(n - param, res_table)
else
res = res - partitions(n - param, res_table)
end if
if i mod 2 then
param = param + i + 2
else
param = param + i / 2 + 1
end if
i = i + 1
end repeat
res_table[n] = res
return res
end</syntaxhighlight>
{{out}}
<pre>
ms = _system.milliseconds
put "P(121):", partitions(121)
put "Time (ms):", _system.milliseconds - ms
-- P(121): 2056148051
-- Time (ms): 3
</pre>
=={{header|Maple}}==
<
option remember;
local k,s:=0,m;
Line 645 ⟶ 1,082:
combinat[numbpart](1000);
# 24061467864032622473692149727991</
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
PartitionsP[666]
PartitionsP[6666]</
{{out}}
<pre>{1,2,3,5,7,11,15,22,30,42,56,77,101,135,176}
Line 659 ⟶ 1,096:
{{trans|C++}}
{{libheader|bignum}}
<
import bignum
Line 685 ⟶ 1,122:
let t0 = cpuTime()
echo partitions(6666)
echo &"Elapsed time: {(cpuTime() - t0) * 1000:.2f} ms"</
{{out}}
Line 692 ⟶ 1,129:
=={{header|Perl}}==
<
use warnings;
no warnings qw(recursion);
Line 720 ⟶ 1,157:
print partitionsP($_) . ' ' for 0..25; print "\n";
print partitionsP(6666) . "\n";</
{{out}}
<pre>1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958
Line 729 ⟶ 1,166:
{{libheader|Phix/mpfr}}
Not exactly super-fast, but this sort of stuff is not really what Phix does best.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">partDiffDiff</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
Line 770 ⟶ 1,207:
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">6666</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"p(%d) = %s (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">partitionsP</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span>
<!--</
{{out}}
<pre>
Line 777 ⟶ 1,214:
=={{header|Picat}}==
<
/* Picat 3.0#5 */
/* Author: Hakan Kjellerstrand */
Line 804 ⟶ 1,241:
CPU time 0.206 seconds.
</syntaxhighlight>
=={{header|PicoLisp}}==
Based on the Erlang implementation.
<syntaxhighlight lang="picolisp">
(de gpentagonals (Max)
(make
(let (N 0 M 1)
(loop
(inc 'N (if (=0 (& M 1)) (>> 1 M) M))
(T (> N Max))
(link N)
(inc 'M)))))
(de p (N)
(cache '(NIL) N
(if (=0 N)
1
(let (Sum 0 Sgn 0)
(for G (gpentagonals N)
((if (< Sgn 2) 'inc 'dec) 'Sum (p (- N G)))
(setq Sgn (& 3 (inc Sgn))))
Sum))))
</syntaxhighlight>
{{Out}}
<pre>
: (bench (p 6666))
0.959 sec
-> 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
</pre>
=={{header|Prolog}}==
<
/* SWI-Prolog 8.3.21 */
/* Author: Jan Burse */
Line 823 ⟶ 1,289:
X = 1936553061617076610800050733944860919984809503384
05932486880600467114423441282418165863.
</syntaxhighlight>
=={{header|Python}}==
Line 829 ⟶ 1,295:
This follows the algorithm from the Mathloger video closely
<
def posd():
Line 879 ⟶ 1,345:
print(" pos_gen:", list(islice(pos_gen(), 10)))
print(" plus_minus:", list(islice(plus_minus(), 15)))
print("\nPartitions:", [part(x) for x in range(15)])</
{{out}}
Line 900 ⟶ 1,366:
====Python: Mathloger video prime generator====
Add the following code after that above
<
"Prime number generator from the partition machine"
p = [1]
Line 917 ⟶ 1,383:
yield p
print("\nPrimes:", list(islice(par_primes(), 15)))</
{{Out}}
Line 924 ⟶ 1,390:
===Python: Alternative===
{{trans|C++}}
<
Line 953 ⟶ 1,419:
if __name__ == '__main__':
print("\nPartitions:", [partitions(x) for x in range(15)])</
{{out}}
Line 966 ⟶ 1,432:
215 ms ± 1.84 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
</pre>
=={{header|Quackery}}==
<code>0 partitions</code> returns <code>1</code> as per [https://oeis.org/A000041 oeis.org/A000041 (Partitions of n)].
This is a naive recursive solution, so computing the partitions of 6666 would take a hideously long time.
<syntaxhighlight lang="Quackery"> [ 1 swap
dup 0 = iff drop done
[ 2dup = iff [ 2drop 1 ] done
2dup > iff [ 2drop 0 ] done
2dup dip 1+ recurse
unrot over - recurse + ] ] is partitions ( n --> n )
say "Partitions of 0 to 29" cr
30 times [ i^ partitions echo sp ]
</syntaxhighlight>
{{out}}
<pre>Partitions of 0 to 29
1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958 2436 3010 3718 4565
</pre>
=={{header|Racket}}==
Backwards range was used to get responsive feedback for progress.
<syntaxhighlight lang="racket">#lang racket
(require math/number-theory)
(define σ
(let ((memo (make-hash)))
(λ (z)
(hash-ref! memo z
(λ () (apply + (divisors z)))))))
(define p
(let ((memo (make-hash '((0 . 1)))))
(λ (n)
(hash-ref!
memo n
(λ ()
(let ((r (if (zero? n) 1
(/ (for/sum ((k (in-range (sub1 n) -1 -1)))
(* (σ (- n k))
(p k)))
n))))
(when (zero? (modulo n 1000)) (displayln (cons n r) (current-error-port)))
r))))))
(map p (range 1 30))
(p 666)
(p 1000)
(p 10000)</syntaxhighlight>
{{out}}
<pre>'(1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958 2436 3010 3718 4565)
11956824258286445517629485
(1000 . 24061467864032622473692149727991)
24061467864032622473692149727991
(2000 . 4720819175619413888601432406799959512200344166)
(3000 . 496025142797537184410324879054927095334462742231683423624)
(4000 . 1024150064776551375119256307915896842122498030313150910234889093895)
(5000 . 169820168825442121851975101689306431361757683049829233322203824652329144349)
(6000 . 4671727531970209092971024643973690643364629153270037033856605528925072405349246129)
(7000 . 32856930803440615786280925635924166861950151574532240659699032157432236394374450791229199)
(8000 . 78360264351568349490593145013364599719010769352985864331118600209417827764524450990388402844164)
(9000 . 77133638117808884907320791427403134961639798322072034262647713694605367979684296948790335590435626459)
(10000 . 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144)
36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144</pre>
=={{header|Raku}}==
{{works with|Rakudo|2020.09}}
Not the fastest, but it gets the job done.
<syntaxhighlight lang="raku"
my @i = lazy [\+] flat 1, (
sub p ($n) { sum @P[$n X- @i
put @P[^26];
put @P[6666];</
{{out}}
<pre>1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958
Line 981 ⟶ 1,520:
=={{header|REXX}}==
=== version 1 ===
<syntaxhighlight lang="rexx">/*REXX program calculates and displays a specific value (or a range of) partitionsP(N).*/
numeric digits 1000 /*able to handle some ginormous numbers*/
parse arg lo hi . /*obtain optional arguments from the CL*/
Line 988 ⟶ 1,528:
if hi=='' | hi=="," then hi= lo /* " " " " " " */
@.= 0; @.0= 1; @.1= 1; @.2= 2; @.3= 3; @.4= 5 /*assign default value and low values. */
!.= @.; !.1= 1; !.3= 1; !.5= 1; !.7= 1; !.9= 1 /*assign default value and even digits.*/
w= length( commas(hi) ) /*W: is used for aligning the index. */
Line 997 ⟶ 1,538:
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
partP: procedure expose @. !.; parse arg n
if @.n\==0 then return @.n /*Is it already computed? Return it. */
#= 0 /*initialize part P number.*/
do k=1 for n; z= n - (k*3 - 1) * k % 2
if z<0 then leave /*Is Z negative? Then leave.*/
if @.z==0 then x= partP(z) /*use recursion if not known.*/
Line 1,011 ⟶ 1,552:
else #= # - (x + y) /*Even? " subtract " " " */
end /*k*/
@.n= #;
{{out|output|text= when using the input of: <tt> 6666 </tt>}}
<pre>
Line 1,020 ⟶ 1,561:
66,666 931,283,431,869,095,717,238,416,063,534,148,471,363,928,685,651,267,074,563,360,050,977,549,251,436,058,076,515,262,033,789,845,457,356,081,278,451,246,751,375,974,038,318,319,810,923,102,769,109,446,980,055,567,090,089,060,954,748,065,131,666,952,830,623,286,286,824,837,240,058,805,177,319,865,230,913,417,587,625,830,803,675,380,262,765,598,632,742,903,192,085,254,824,621
</pre>
=== version 2 ===
This REXX version is about '''25%''' faster than REXX version 1.
The biggest part of the improvement was using the expression '''k+k+k''' instead of '''k*3'''.
<syntaxhighlight lang="rexx">/*REXX program calculates and displays a specific value (or a range of) partitionsP(N).*/
numeric digits 1000 /*able to handle some ginormous numbers*/
parse arg lo hi . /*obtain optional arguments from the CL*/
if lo=='' | lo=="," then lo= 0 /*Not specified? Then use the default.*/
if hi=='' | hi=="," then hi= lo /* " " " " " " */
@.= 0; @.0= 1; @.1= 1; @.2= 2; @.3= 3; @.4= 5 /*default values for some low numbers. */
!.= @.; !.1= 1; !.3= 1; !.5= 1; !.7= 1; !.9= 1 /* " " " all the 1─digit #s*/
w= length( commas(hi) ) /*W: is used for aligning the index. */
do j=lo to hi /*compute a range of partitionsP. */
say right( commas(j), w) ' ' commas( partP(j) )
end /*j*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
partP: procedure expose @. !.; parse arg n /*obtain number (index) for computation*/
if @.n\==0 then return @.n /*Is it already computed? Return it. */
#= 0 /*initialize part P number.*/
do k=1 for n; z= n - (k+k+k - 1) * k % 2 /*compute the partition P num*/
if z<0 then leave /*Is Z negative? Then leave.*/
if @.z==0 then x= partP(z) /*use recursion if not known.*/
else x= @.z /*use the pre─computed number*/
z= z - k /*subtract index (K) from Z. */
if z<0 then y= 0 /*Is Z negative? Then set Y=0*/
else if @.z==0 then y= partP(z) /*use recursion if not known.*/
else y= @.z /*use the pre─computed number*/
parse var k '' -1 _ /*obtain K's last decimal dig*/
if !._ then #= # + x + y /*Odd? Then sum X and Y.*/
else #= # - (x + y) /*Even? " subtract " " " */
end /*k*/
@.n= #; return # /*define and return partitionsP of N. */</syntaxhighlight>
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}}
=== version 3 ===
This REXX version is about '''90%''' faster than REXX version 1.
The biggest part of the improvement was using memoization of the expressions ('''k+k+k - 1) * k % 2''' for all values of (positive) '''k''' up to '''hi'''.
<syntaxhighlight lang="rexx">/*REXX program calculates and displays a specific value (or a range of) partitionsP(N).*/
numeric digits 1000 /*able to handle some ginormous numbers*/
parse arg lo hi . /*obtain optional arguments from the CL*/
if lo=='' | lo=="," then lo= 0 /*Not specified? Then use the default.*/
if hi=='' | hi=="," then hi= lo /* " " " " " " */
@.= 0; @.0= 1; @.1= 1; @.2= 2; @.3= 3; @.4= 5 /*default values for some low numbers. */
!.= @.; !.1= 1; !.3= 1; !.5= 1; !.7= 1; !.9= 1 /* " " " all the 1─digit #s*/
w= length( commas(hi) ) /*W: is used for aligning the index. */
do i=1 for hi; a.i= (i+i+i - 1) * i % 2 /*calculate HI expressions (for partP).*/
end /*i*/
do j=lo to hi /*compute a range of partitionsP. */
say right( commas(j), w) ' ' commas( partP(j) )
end /*j*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
partP: procedure expose @. !. a.; parse arg n /*obtain number (index) for computation*/
if @.n\==0 then return @.n /*Is it already computed? Return it. */
#= 0 /*initialize part P number.*/
do k=1 for n; z= n - a.k /*compute the partition P num*/
if z<0 then leave /*Is Z negative? Then leave.*/
if @.z==0 then x= partP(z) /*use recursion if not known.*/
else x= @.z /*use the pre─computed number*/
z= z - k /*subtract index (K) from Z. */
if z<0 then y= 0 /*Is Z negative? Then set Y=0*/
else if @.z==0 then y= partP(z) /*use recursion if not known.*/
else y= @.z /*use the pre─computed number*/
parse var k '' -1 _ /*obtain K's last decimal dig*/
if !._ then #= # + x + y /*Odd? Then sum X and Y.*/
else #= # - (x + y) /*Even? " subtract " " " */
end /*k*/
@.n= #; return # /*define and return partitionsP of N. */</syntaxhighlight>
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br><br>
=={{header|Rust}}==
<
// rug = "1.11"
Line 1,067 ⟶ 1,686:
println!("P({}) = {}", n, result);
println!("elapsed time: {} microseconds", time.as_micros());
}</
{{out}}
Line 1,078 ⟶ 1,697:
Built-in:
<
User-defined:
<
func (n) is cached {
Line 1,103 ⟶ 1,722:
say partitionsP(6666)
say ("Took %.4f seconds" % Time.micro-t)</
{{out}}
Line 1,111 ⟶ 1,730:
Took 24.5225 seconds
</pre>
=={{header|Swift}}==
{{trans|Rust}}
Using AttaSwift's BigInt library.
<syntaxhighlight lang="swift">import BigInt
func partitions(n: Int) -> BigInt {
var p = [BigInt(1)]
for i in 1...n {
var num = BigInt(0)
var k = 1
while true {
var j = (k * (3 * k - 1)) / 2
if j > i {
break
}
if k & 1 == 1 {
num += p[i - j]
} else {
num -= p[i - j]
}
j += k
if j > i {
break
}
if k & 1 == 1 {
num += p[i - j]
} else {
num -= p[i - j]
}
k += 1
}
p.append(num)
}
return p[n]
}
print("partitions(6666) = \(partitions(n: 6666))")</syntaxhighlight>
{{out}}
<pre>partitions(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863</pre>
=={{header|Wren}}==
Line 1,116 ⟶ 1,791:
{{libheader|Wren-big}}
Although it may not look like it, this is actually a decent time for Wren which is interpreted and the above module is written entirely in Wren itself.
<
var p = []
Line 1,151 ⟶ 1,826:
for (n in 2..N) partitionsP.call(n)
System.print("p[%(N)] = %(p[N])")
System.print("Took %(System.clock - start) seconds")</
{{out}}
| |||