# OK to post homework
# RDB, 2022-04-02, HW18

read "C18.txt":
read "C19.txt":

# 2.

SeqCoStupid := proc(N)
    local G:
    G := [[0, 1, 1], [0, 0, 1]]:
    [seq(NuC(2 * v - 1, G), v=1..N)]:
end:

# 3.

SeqCoSmart := proc(N)
    local L:
    L := Zs(2 * N):
    [seq(L[2 * i + 1] / 2, i=0..N - 1)]:
end:

# SeqCoStupid(10) took 9.758 seconds.
# SeqCoSmart(10) took 0.185 seconds.

# 4.

lp := n -> evalf(2 * SeqCoSmart(n)[-1] / 6^(2 * n - 1)):

# lp(15) = 0.08479432144

# 6.

GQP1 := proc(L, p, n)
    local polys, i, data, poly:

    polys := []:
    for i from 1 to p do
        data := [seq(L[p * k + i], k=0..floor((nops(L) - i) / p))]:
        poly := GP(data, n):
        if poly = FAIL then
            return FAIL:
        fi:

        # GP(L, n) returns p such that L[n] = P(n) for 1 <= n <= nops(L).
        # So, we have L[pn + i] = data[n] = P(n) for 1 <= n <= nops(L).
        # If n = i mod p, then n = pk + i but k "starts" at 0 for n = 1. To fix
        # that, we'll use k + 1 = (n - i) / p + 1.
        polys := [op(polys), subs(n=(n-i)/p + 1, poly)]:
    od:

    polys:
end:

GQP := proc(L, n)
    local p, polys:
    for p from 1 to floor(nops(L) / 2) do
        polys := GQP1(L, p, n):
        if polys <> FAIL then
            return polys:
        fi:
    od:

    FAIL:
end: