Но — если замкнутой формулы нет, то как можно (при желании) вычислять p(n) при большом n? Скажем, если перебор всех
p(100)=190569292
разбиений числа n=100 ещё можно поручить компьютеру, то перебирать все
p(1000)=24061467864032622473692149727991
разбиения числа n=1000 кажется не очень продуктивной идеей.

Один "технический" способ решения этого вопроса — это находить больше. А именно, пусть p_k(n) — число разбиений n в сумму (невозрастающих) слагаемых, которые все не превосходят данного k. Тогда, с одной стороны, p(n)=p_n(n), а с другой — числа p_k(n) уже несложно ищутся рекурсивно, когда мы перебираем варианты для самого большого слагаемого:
p_k(n) = \sum_{j=1}^k p_j(n-j).