This site is supported by donations to The OEIS Foundation.
User talk:Peter Luschny/P-Transform
From OeisWiki
G.f. and more efficient calculation
By considering a combinatorial interpretation for the binomial products, I was led to the form (ignoring the norm) .
Obviously this could equally be expressed as
This has two implications. Firstly, it suggests that it might be more natural to decompose this into two transformations: one which takes partial products of the original sequence, and one which maps to g.f. .
Secondly, it gives the alternative computation
def PartialPtransGF(n, f, norm = None): if n == 0: return [1] x = [1] for i in range(1, n+1): x.append(x[-1] * f(i)) psr.<y> = PowerSeriesRing(x[-1].parent(), default_prec = n+1) R = [0] A = psr(0).O(n+1) - sum(y^i * x[i] for i in range(1, n+1)) Apow = 1 for i in range(1, n+1): Apow *= A R.append(Apow[n]) return R if norm is None else [norm(n,k)*R[k] for k in (0..n)]
In my benchmarking this is considerably faster than PartialPtransRec, which is to be expected because it can use Karatsuba's algorithm to accelerate the polynomial multiplications. Peter J. Taylor (talk) 09:37, 9 July 2024 (EDT)