Lazy Power Series

This file provides an implementation of lazy univariate power series, which uses the stream class for its internal data structure. The lazy power series keep track of their approximate order as much as possible without forcing the computation of any additional coefficients. This is required for recursively defined power series.

This code is based on the work of Ralf Hemmecke and Martin Rubey’s Aldor-Combinat, which can be found at http://www.risc.uni-linz.ac.at/people/hemmecke/aldor/combinat/index.html. In particular, the relevant section for this file can be found at http://www.risc.uni-linz.ac.at/people/hemmecke/AldorCombinat/combinatse9.html.

class sage.combinat.species.series.LazyPowerSeries(A, stream=None, order=None, aorder=None, aorder_changed=True, is_initialized=False, name=None)

Bases: sage.structure.element.AlgebraElement

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: f = L()
sage: loads(dumps(f))
Uninitialized lazy power series

add(y)

EXAMPLES: Test Plus 1

sage: from sage.combinat.species.series import *
sage: from sage.combinat.species.stream import Stream
sage: L = LazyPowerSeriesRing(QQ)
sage: gs0 = L([0])
sage: gs1 = L([1])
sage: sum1 = gs0 + gs1
sage: sum2 = gs1 + gs1
sage: sum3 = gs1 + gs0
sage: [gs0.coefficient(i) for i in range(11)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
sage: [gs1.coefficient(i) for i in range(11)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sage: [sum1.coefficient(i) for i in range(11)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sage: [sum2.coefficient(i) for i in range(11)]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
sage: [sum3.coefficient(i) for i in range(11)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Test Plus 2

sage: gs1 = L([1,2,4,8,0])
sage: gs2 = L([-1, 0,-1,-9,22,0])
sage: sum = gs1 + gs2
sage: sum2 = gs2 + gs1
sage: [ sum.coefficient(i) for i in range(5) ]
[0,  2, 3, -1, 22]
sage: [ sum.coefficient(i) for i in range(5, 11) ]
[0, 0, 0, 0, 0, 0]
sage: [ sum2.coefficient(i) for i in range(5) ]
[0,  2, 3, -1, 22]
sage: [ sum2.coefficient(i) for i in range(5, 11) ]
[0, 0, 0, 0, 0, 0]

coefficient(n)

Return the coefficient of xn in self.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: f = L(ZZ)
sage: [f.coefficient(i) for i in range(5)]
[0, 1, -1, 2, -2]

coefficients(n)

Return the first n coefficients of self.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: f = L([1,2,3,0])
sage: f.coefficients(5)
[1, 2, 3, 0, 0]

compose(y)

Return the composition of this power series and the power series y.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: s = L([1])
sage: t = L([0,0,1])
sage: u = s(t)
sage: u.coefficients(11)
[1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Test Compose 2

sage: s = L([1])
sage: t = L([0,0,1,0])
sage: u = s(t)
sage: u.aorder
0
sage: u.order
Unknown series order
sage: u.coefficients(10)
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
sage: u.aorder
0
sage: u.order
0

Test Compose 3 s = 1/(1-x), t = x/(1-x) s(t) = (1-x)/(1-2x)

sage: s = L([1])
sage: t = L([0,1])
sage: u = s(t)
sage: u.coefficients(14)
[1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]

composition(y)

Return the composition of this power series and the power series y.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: s = L([1])
sage: t = L([0,0,1])
sage: u = s(t)
sage: u.coefficients(11)
[1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Test Compose 2

sage: s = L([1])
sage: t = L([0,0,1,0])
sage: u = s(t)
sage: u.aorder
0
sage: u.order
Unknown series order
sage: u.coefficients(10)
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
sage: u.aorder
0
sage: u.order
0

Test Compose 3 s = 1/(1-x), t = x/(1-x) s(t) = (1-x)/(1-2x)

sage: s = L([1])
sage: t = L([0,1])
sage: u = s(t)
sage: u.coefficients(14)
[1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]

compute_aorder(*args, **kwargs)

The default compute_aorder does nothing.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: a = L(1)
sage: a.compute_aorder() is None
True

compute_coefficients(i)

Computes all the coefficients of self up to i.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: a = L([1,2,3])
sage: a.compute_coefficients(5)
sage: a
1 + 2*x + 3*x^2 + 3*x^3 + 3*x^4 + 3*x^5 + ...

define(x)

EXAMPLES: Test Recursive 0

sage: L = LazyPowerSeriesRing(QQ)
sage: one = L(1)
sage: monom = L.gen()
sage: s = L()
sage: s._name = 's'
sage: s.define(one+monom*s)
sage: s.aorder
0
sage: s.order
Unknown series order
sage: [s.coefficient(i) for i in range(6)]
[1, 1, 1, 1, 1, 1]

Test Recursive 1

sage: s = L()
sage: s._name = 's'
sage: s.define(one+monom*s*s)
sage: s.aorder
0
sage: s.order
Unknown series order
sage: [s.coefficient(i) for i in range(6)]
[1, 1, 2, 5, 14, 42]

Test Recursive 1b

sage: s = L()
sage: s._name = 's'
sage: s.define(monom + s*s)
sage: s.aorder
1
sage: s.order
Unknown series order
sage: [s.coefficient(i) for i in range(7)]
[0, 1, 1, 2, 5, 14, 42]

Test Recursive 2

sage: s = L()
sage: s._name = 's'
sage: t = L()
sage: t._name = 't'
sage: s.define(one+monom*t*t*t)
sage: t.define(one+monom*s*s)
sage: [s.coefficient(i) for i in range(9)]
[1, 1, 3, 9, 34, 132, 546, 2327, 10191]
sage: [t.coefficient(i) for i in range(9)]
[1, 1, 2, 7, 24, 95, 386, 1641, 7150]

Test Recursive 2b

sage: s = L()
sage: s._name = 's'
sage: t = L()
sage: t._name = 't'
sage: s.define(monom + t*t*t)
sage: t.define(monom + s*s)
sage: [s.coefficient(i) for i in range(9)]
[0, 1, 0, 1, 3, 3, 7, 30, 63]
sage: [t.coefficient(i) for i in range(9)]
[0, 1, 1, 0, 2, 6, 7, 20, 75]

Test Recursive 3

sage: s = L()
sage: s._name = 's'
sage: s.define(one+monom*s*s*s)
sage: [s.coefficient(i) for i in range(10)]
[1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675]

derivative()

EXAMPLES:

sage: from sage.combinat.species.stream import Stream
sage: L = LazyPowerSeriesRing(QQ)
sage: one = L(1)
sage: monom = L.gen()
sage: s = L([1])
sage: u = s.derivative()
sage: u.coefficients(10)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

sage: s = L()
sage: s._name = 's'
sage: s.define(one+monom*s*s)
sage: u = s.derivative()
sage: u.coefficients(5) #[1*1, 2*2, 3*5, 4*14, 5*42]
[1, 4, 15, 56, 210]

sage: s = L([1])
sage: t = L([0,1])
sage: u = s(t).derivative()
sage: v = (s.derivative().compose(t))*t.derivative()
sage: u.coefficients(11)
[1, 4, 12, 32, 80, 192, 448, 1024, 2304, 5120, 11264]
sage: v.coefficients(11)
[1, 4, 12, 32, 80, 192, 448, 1024, 2304, 5120, 11264]

sage: s = L(); s._name='s'
sage: t = L(); t._name='t'
sage: s.define(monom+t*t*t)
sage: t.define(monom+s*s)
sage: u = (s*t).derivative()
sage: v = s.derivative()*t + s*t.derivative()
sage: u.coefficients(10)
[0, 2, 3, 4, 30, 72, 133, 552, 1791, 4260]
sage: v.coefficients(10)
[0, 2, 3, 4, 30, 72, 133, 552, 1791, 4260]
sage: u.coefficients(10) == v.coefficients(10)
True

sage: f = L._new_initial(2, Stream([0,0,4,5,6,0]))
sage: d = f.derivative()
sage: d.get_aorder()
1
sage: d.coefficients(5)
[0, 8, 15, 24, 0]

div(other)

Divide this power series by other.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: x = L.gen()

Fibonacci numbers:

sage: b = x / (1-x-x^2); b.compute_coefficients(10); b
x + x^2 + 2*x^3 + 3*x^4 + 5*x^5 + 8*x^6
+ 13*x^7 + 21*x^8 + 34*x^9 + 55*x^10 + O(x^11)

exponential()

get_aorder()

Return the approximate order of self.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: a = L.gen()
sage: a.get_aorder()
1

get_order()

Return the order of self.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: a = L.gen()
sage: a.get_order()
1

get_stream()

Return self’s underlying Stream object.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: a = L.gen()
sage: s = a.get_stream()
sage: [s[i] for i in range(5)]
[0, 1, 0, 0, 0]

initialize_coefficient_stream(compute_coefficients)

Initializes the coefficient stream.

INPUT: compute_coefficients

integral(integration_constant=0)

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: zero = L(0)
sage: s = zero
sage: t = s.integral()
sage: t.is_zero()
True

sage: s = zero
sage: t = s.integral(1)
sage: t.coefficients(6)
[1, 0, 0, 0, 0, 0]
sage: t._stream.is_constant()
True

sage: s = L.term(1, 0)
sage: t = s.integral()
sage: t.coefficients(6)
[0, 1, 0, 0, 0, 0]
sage: t._stream.is_constant()
True

sage: s = L.term(1,0)
sage: t = s.integral(1)
sage: t.coefficients(6)
[1, 1, 0, 0, 0, 0]
sage: t._stream.is_constant()
True

sage: s = L.term(1, 4)
sage: t = s.integral()
sage: t.coefficients(10)
[0, 0, 0, 0, 0, 1/5, 0, 0, 0, 0]

sage: s = L.term(1,4)
sage: t = s.integral(1)
sage: t.coefficients(10)
[1, 0, 0, 0, 0, 1/5, 0, 0, 0, 0]

invert()

Return 1 over this power series, i.e. invert this power series.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: x = L.gen()

Geometric series:

sage: a = ~(1-x); a.compute_coefficients(10); a
1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + O(x^11)

(Shifted) Fibonacci numbers:

sage: b = ~(1-x-x^2); b.compute_coefficients(10); b
1 + x + 2*x^2 + 3*x^3 + 5*x^4 + 8*x^5
+ 13*x^6 + 21*x^7 + 34*x^8 + 55*x^9 + 89*x^10 + O(x^11)

Series whose constant coefficient is \(0\) cannot be inverted:

sage: ~x
Traceback (most recent call last):
....
ZeroDivisionError: cannot invert x because constant coefficient is 0

is_finite(n=None)

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: a = L([0,0,1,0,0]); a
O(1)
sage: a.is_finite()
False
sage: c = a[4]
sage: a.is_finite()
False
sage: a.is_finite(4)
False
sage: c = a[5]
sage: a.is_finite()
True
sage: a.is_finite(4)
True

is_zero()

Return True if and only if self is zero.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: s = L([0,2,3,0])
sage: s.is_zero()
False

sage: s = L(0)
sage: s.is_zero()
True

sage: s = L([0])
sage: s.is_zero()
False
sage: s.coefficient(0)
0
sage: s.coefficient(1)
0
sage: s.is_zero()
True

iterator(n=0, initial=None)

Return an iterator for the coefficients of self starting at n.

EXAMPLES:

sage: from sage.combinat.species.stream import Stream
sage: L = LazyPowerSeriesRing(QQ)
sage: f = L(range(10))
sage: g = f.iterator(2)
sage: [next(g) for i in range(5)]
[2, 3, 4, 5, 6]
sage: g = f.iterator(2, initial=[0,0])
sage: [next(g) for i in range(5)]
[0, 0, 2, 3, 4]

refine_aorder()

Refines the approximate order of self as much as possible without computing any coefficients.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: a = L([0,0,0,0,1])
sage: a.aorder
0
sage: a.coefficient(2)
0
sage: a.aorder
0
sage: a.refine_aorder()
sage: a.aorder
3

sage: a = L([0,0])
sage: a.aorder
0
sage: a.coefficient(5)
0
sage: a.refine_aorder()
sage: a.aorder
Infinite series order

sage: a = L([0,0,1,0,0,0])
sage: a[4]
0
sage: a.refine_aorder()
sage: a.aorder
2

restricted(min=None, max=None)

Return the power series restricted to the coefficients starting at min and going up to, but not including max.

If min is not specified, then it is assumed to be zero. If max is not specified, then it is assumed to be infinity.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: a = L([1])
sage: a.restricted().coefficients(10)
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sage: a.restricted(min=2).coefficients(10)
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
sage: a.restricted(max=5).coefficients(10)
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
sage: a.restricted(min=2, max=6).coefficients(10)
[0, 0, 1, 1, 1, 1, 0, 0, 0, 0]

set_approximate_order(new_order)

Sets the approximate order of self and returns True if the approximate order has changed otherwise it will return False.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: f = L([0,0,0,3,2,1,0])
sage: f.get_aorder()
0
sage: f.set_approximate_order(3)
True
sage: f.set_approximate_order(3)
False

tail()

Return the power series whose coefficients obtained by subtracting the constant term from this series and then dividing by x.

EXAMPLES:

sage: from sage.combinat.species.stream import Stream
sage: L = LazyPowerSeriesRing(QQ)
sage: f = L(range(20))
sage: g = f.tail()
sage: g.coefficients(10)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

times(y)

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: gs0 = L(0)
sage: gs1 = L([1])

sage: prod0 = gs0 * gs1
sage: [prod0.coefficient(i) for i in range(11)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

sage: prod1 = gs1 * gs0
sage: [prod1.coefficient(i) for i in range(11)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

sage: prod2 = gs1 * gs1
sage: [prod2.coefficient(i) for i in range(11)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

sage: gs1 = L([1,2,4,8,0])
sage: gs2 = L([-1, 0,-1,-9,22,0])

sage: prod1 = gs1 * gs2
sage: [prod1.coefficient(i) for i in range(11)]
[-1, -2, -5, -19, 0, 0, 16, 176, 0, 0, 0]

sage: prod2 = gs2 * gs1
sage: [prod2.coefficient(i) for i in range(11)]
[-1, -2, -5, -19, 0, 0, 16, 176, 0, 0, 0]

class sage.combinat.species.series.LazyPowerSeriesRing(R, names=None, element_class=None)

Bases: sage.rings.ring.Algebra

gen(i=0)

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: L.gen().coefficients(5)
[0, 1, 0, 0, 0]

identity_element()

Return the one power series.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: L.identity_element()
1

ngens()

EXAMPLES:

sage: LazyPowerSeriesRing(QQ).ngens()
1

product_generator(g)

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: s1 = L([1,1,0])
sage: s2 = L([1,0,1,0])
sage: s3 = L([1,0,0,1,0])
sage: s4 = L([1,0,0,0,1,0])
sage: s5 = L([1,0,0,0,0,1,0])
sage: s6 = L([1,0,0,0,0,0,1,0])
sage: s = [s1, s2, s3, s4, s5, s6]
sage: def g():
....:     for a in s:
....:         yield a
sage: p = L.product_generator(g())
sage: p.coefficients(26)
[1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 5, 5, 4, 4, 4, 3, 2, 2, 1, 1, 1, 0, 0, 0, 0]

sage: def m(n):
....:     yield 1
....:     while True:
....:         for i in range(n-1):
....:             yield 0
....:         yield 1
sage: def s(n):
....:     q = 1/n
....:     yield 0
....:     while True:
....:         for i in range(n-1):
....:             yield 0
....:         yield q

sage: def lhs_gen():
....:     n = 1
....:     while True:
....:         yield L(m(n))
....:         n += 1

sage: def rhs_gen():
....:     n = 1
....:     while True:
....:         yield L(s(n))
....:         n += 1
sage: lhs = L.product_generator(lhs_gen())
sage: rhs = L.sum_generator(rhs_gen()).exponential()
sage: lhs.coefficients(10)
[1, 1, 2, 3, 5, 7, 11, 15, 22, 30]
sage: rhs.coefficients(10)
[1, 1, 2, 3, 5, 7, 11, 15, 22, 30]

sum(a)

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: l = [L(ZZ)]*3
sage: L.sum(l).coefficients(10)
[0, 3, -3, 6, -6, 9, -9, 12, -12, 15]

sum_generator(g)

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: g = [L([1])]*6 + [L(0)]
sage: t = L.sum_generator(g)
sage: t.coefficients(10)
[1, 2, 3, 4, 5, 6, 6, 6, 6, 6]

sage: s = L([1])
sage: def g():
....:     while True:
....:         yield s
sage: t = L.sum_generator(g())
sage: t.coefficients(9)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

term(r, n)

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: L.term(0,0)
0
sage: L.term(3,2).coefficients(5)
[0, 0, 3, 0, 0]

zero()

Return the zero power series.

EXAMPLES:

sage: L = LazyPowerSeriesRing(QQ)
sage: L.zero()
0

sage.combinat.species.series.uninitialized()

EXAMPLES:

sage: from sage.combinat.species.series import uninitialized
sage: uninitialized()
Traceback (most recent call last):
...
RuntimeError: we should never be here