Hi

Update 3

Actually no, the below code is at least O(n^2), not O(N(logN)^2), back to 0, then :(.

Update 2

Finally, after some desperate struggling, I am able to do it (I feel so old for challenges already :()

import numpy as np


def catalan(n: int):
  f = np.zeros(n + 1).astype(int)
  g = np.zeros(n + 1).astype(int)
  f[0] = 1
  for i in range(n):
    two_pow = 1
    while True:
      ay = i + 1 - two_pow
      ax = max(0, ay - two_pow + 1)      

      bx = two_pow - 1
      by = min(i, bx + two_pow - 1)

      c = np.convolve(f[ax : ay + 1], f[bx : by + 1])
      g[i] += c[i - (ax + bx)]

      if ax == 0: break
      two_pow *= 2

    f[i + 1] = g[i]

  return f[:n]


print(catalan(12))

Update 1

Thanks to conqueror_of_tourist, the search term is Online FFT.

Unfortunately... it's quite beyond me to understand it. I have been reading and this is the best code I could draft but it's not working (returning 12 instead of 14). Anyone familiar, can you spot anything wrong? Thanks.

import numpy as np


def catalan(n: int):
  f = np.zeros(n + 1).astype(int)
  f[0] = 1
  for i in range(n - 1):
    f[i + 1] += f[i]
    f[i + 2] += f[i]
    two_pow = 2
    while i > 0 and i % two_pow == 0:
      a = f[i - two_pow : i]
      b = f[two_pow : min(n, two_pow * 2)]
      two_pow *= 2

      contrib = np.convolve(a, b)
      for j in range(min(len(contrib), n - i)):
        f[i + j + 1] += contrib[j]

  return f[:n]


print(catalan(10))

I am learning FFT. ChatGPT told me that FFT could assist in solving self-convolution form like Catalan number where the (n+1)-th element is some convolution of the first n elements. For example:

c[n + 1] = sum(c[i][n — i]) for i in 0..n

Unfortunately, no matter where I look (and how hard I press ChatGPT), I couldn't find a single website/book/paper detailing this approach.

My Question: Is it actually possible to compute the first n elements of a self-convolution form like Catalan using FFT in, for example, O(nlogn) or less than O(n^2)?

Thanks a lot