35 lines
733 B
Text
35 lines
733 B
Text
local bigint = require "pluto:bigint"
|
|
require "table2"
|
|
|
|
local p = {}
|
|
local pd = {}
|
|
|
|
local part_diff_diff = |n| -> (n & 1 == 1) ? (n + 1) / 2 : n + 1
|
|
|
|
local function part_diff(n)
|
|
if n < 2 then return 1 end
|
|
pd[n] = pd[n-1] + part_diff_diff(n - 1)
|
|
return pd[n]
|
|
end
|
|
|
|
local function partitions_p(n)
|
|
if n < 2 then return end
|
|
local psum = bigint.new(0)
|
|
for i = 1, n do
|
|
local pdi = part_diff(i)
|
|
if pdi > n then break end
|
|
local sign = (i - 1) % 4 < 2 ? 1 : -1
|
|
psum += p[n - pdi] * sign
|
|
end
|
|
p[n] = psum
|
|
end
|
|
|
|
local N = 6666
|
|
p = table.rep(N, 0)
|
|
pd = table.rep(N, 0)
|
|
p[0] = bigint.new(1)
|
|
p[1] = p[0]
|
|
pd[0] = 1
|
|
pd[1] = 1
|
|
for n = 2, N do partitions_p(n) end
|
|
print($"p[{N}] = {p[N]}")
|