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]}")