37 lines
1.0 KiB
Plaintext
37 lines
1.0 KiB
Plaintext
program partition_function;
|
|
loop for n in [666, 6666] do
|
|
show_partition_with_time(n);
|
|
end loop;
|
|
|
|
proc show_partition_with_time(n);
|
|
s := clock;
|
|
p := partition(n);
|
|
d := (clock - s) / 1000;
|
|
print("p(" + str n + ") = " + str p + " (" + str d + "s)");
|
|
end proc;
|
|
|
|
proc partition(n);
|
|
pn := [1,1];
|
|
loop for i in [3..n+2] do
|
|
pn(i) := 0;
|
|
loop init k := 1; step k +:= 1; do
|
|
penta := k * (3 * k-1) div 2;
|
|
if penta >= i-1 then quit; end if;
|
|
if k mod 2 = 1 then
|
|
pn(i) +:= pn(i-penta);
|
|
else
|
|
pn(i) -:= pn(i-penta);
|
|
end if;
|
|
penta +:= k;
|
|
if penta >= i-1 then quit; end if;
|
|
if k mod 2 = 1 then
|
|
pn(i) +:= pn(i-penta);
|
|
else
|
|
pn(i) -:= pn(i-penta);
|
|
end if;
|
|
end loop;
|
|
end loop;
|
|
return pn(n+2);
|
|
end proc;
|
|
end program;
|