Problem 739

Comments

It ended up being quite significant that they gave the first example of how the triangle works using a seed row of all 1’s. The left most values of each row in this triangle end up forming the Catalan numbers. I loved how that page started

This is probably the longest entry in the OEIS, and rightly so.

Cuz ho boy is that entry long! I was honestly surprised that I hadn’t stumbled upon it earlier with all these problems I’ve been completing.

The challenge in this problem was that we needed an answer using a Catalan transform. Basically a seed row of different values. That led me to this pdf on Catalan transforms also from oeis.org. In this document they give two ways to calculate a Catalan transform. The first way is what I have implemented here. The second was what I found myself doing initially, recursively calculating each line of the triangle until reaching the bottom row. That is incredible inefficient, at complexity \(O(n^2)\). However, this solution is linear, aka \(O(n)\). The biggest bottleneck in my final implementation is the speed of finding the modular inverse of each number below \(n\).

Runs in about 42 seconds with Pypy3.

Code

modulo = 1000000007

def series(l):
    a, b, s = 1, 3, []
    for _ in range(l):
        a, b = b, (a + b) % modulo
        s.append(a)
    return s

def inv(n):
    t, newt = 0, 1
    r, newr = modulo, n
    while newr:
        q = r // newr
        t, newt = newt, t - q * newt
        r, newr = newr, r - q * newr
    return t

def solve(n):

    fact = [1] * (2*n)
    for i in range(1, 2*n):
        fact[i] = (fact[i - 1] * i) % modulo

    total = 0
    ser = series(n - 1)
    const = (inv(fact[n - 2]) * inv(n - 1)) % modulo
    for k in range(n - 1):
        total += fact[n + k - 2] * inv(fact[k]) * \
                (n - k - 1) * ser[n - k - 2] * const

    return total % modulo

if __name__ == '__main__':
    import sys
    n = eval(sys.argv[1])
    print(solve(n))

Tests

import pytest
from problem import solve

_test_solve = (
        (8, 2663),
        (20, 742296999),
        (10**2, 130336284),
        (10**3, 537806289),
        (10**4, 304246173),
        (10**5, 587213414),
)

@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
    assert expect == solve(n)