Are you sure it's the inverse function which is slow? Just looking at the command
f = prod((1 - x^n)^a(n) for n in (1..size)) + O(x^size) I would guess that first the gigantic product is computed, and only then would the resulting polynomial be truncated by the O(x^size) part. Maybe try to alter that via: f = prod((1 - x^n + O(x^size))^a(n) for n in (1..size)) On Tuesday, November 10, 2020 at 4:07:12 PM UTC-5 Peter Luschny wrote: > Hi all, > > I wanted to implement the Euler Transformation. > https://oeis.org/wiki/Euler_transform > My first attempt was: > > def EulerTransform(size, a): > R.<x> = ZZ[[]] > f = prod((1 - x^n)^a(n) for n in (1..size)) + O(x^size) > return f.inverse().list() > > print(EulerTransform(6, lambda n: factorial(n))) > > Now try this with size = 30. I have no idea how long this > takes because after 3 years I turned the computer off. > > Am I doing something fundamentally wrong, or is f.inverse() > hopelessly slow? > > You can of course implement it differently, but that's not my > question. For those who are interested in the transformation > here the fast variant: > > def EulerTrans(a): > @cached_function > def b(n): > if n == 0: return 1 > s = sum(sum(d*a(d) for d in divisors(j))*b(n-j) for j in (1..n)) > return s//n > return b > > b = EulerTrans(lambda n: factorial(n)) > print([b(n) for n in range(30)]) > > Thanks > > > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/eb26f117-fe6c-4cbd-94c4-5b63f374500en%40googlegroups.com.
