70 lines
1.2 KiB
Plaintext
70 lines
1.2 KiB
Plaintext
program Partition_function_P;
|
|
|
|
{$APPTYPE CONSOLE}
|
|
|
|
uses
|
|
System.SysUtils,
|
|
Velthuis.BigIntegers,
|
|
System.Diagnostics;
|
|
|
|
var
|
|
p: TArray<BigInteger>;
|
|
pd: TArray<Integer>;
|
|
|
|
function PartiDiffDiff(n: Integer): Integer;
|
|
begin
|
|
if n and 1 = 1 then
|
|
exit((n + 1) div 2);
|
|
Result := n + 1;
|
|
end;
|
|
|
|
function partDiff(n: Integer): Integer;
|
|
begin
|
|
if n < 2 then
|
|
exit(1);
|
|
|
|
pd[n] := pd[n - 1] + PartiDiffDiff(n - 1);
|
|
Result := pd[n];
|
|
end;
|
|
|
|
procedure partitionP(n: Integer);
|
|
begin
|
|
if n < 2 then
|
|
exit;
|
|
|
|
var psum: BigInteger := 0;
|
|
for var i := 1 to n do
|
|
begin
|
|
var pdi := partDiff(i);
|
|
if pdi > n then
|
|
Break;
|
|
|
|
var sign: Int64 := -1;
|
|
|
|
if (i - 1) mod 4 < 2 then
|
|
sign := 1;
|
|
|
|
var t: BigInteger := BigInteger(p[n - pdi]) * BigInteger(sign);
|
|
psum := psum + t;
|
|
end;
|
|
p[n] := psum;
|
|
end;
|
|
|
|
begin
|
|
var stopwatch := TStopwatch.Create;
|
|
const n = 6666;
|
|
SetLength(p, n + 1);
|
|
SetLength(pd, n + 1);
|
|
stopwatch.Start;
|
|
p[0] := 1;
|
|
pd[0] := 1;
|
|
p[1] := 1;
|
|
pd[1] := 1;
|
|
for var i := 2 to n do
|
|
partitionP(i);
|
|
stopwatch.Stop;
|
|
writeln(format('p[%d] = %s', [n, p[n].ToString]));
|
|
writeln('Took ', stopwatch.ElapsedMilliseconds, 'ms');
|
|
Readln;
|
|
end.
|