$k$ -regular sequences¶

An introduction and formal definition of $k$ -regular sequences can be found, for example, on the Wikipedia article k-regular_sequence or in [AS2003].

Sage

sage: import logging
sage: logging.basicConfig()

Python

>>> from sage.all import *
>>> import logging
>>> logging.basicConfig()

Sage Live

import logging
logging.basicConfig()

Examples¶

Binary sum of digits¶

The binary sum of digits $S (n)$ of a nonnegative integer $n$ satisfies $S (2 n) = S (n)$ and $S (2 n + 1) = S (n) + 1$ . We model this by the following:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: S = Seq2((Matrix([[1, 0], [0, 1]]), Matrix([[1, 0], [1, 1]])),
....:          left=vector([0, 1]), right=vector([1, 0]))
sage: S
2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...
sage: all(S[n] == sum(n.digits(2)) for n in srange(10))
True

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> S = Seq2((Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(1), Integer(0)], [Integer(1), Integer(1)]])),
...          left=vector([Integer(0), Integer(1)]), right=vector([Integer(1), Integer(0)]))
>>> S
2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...
>>> all(S[n] == sum(n.digits(Integer(2))) for n in srange(Integer(10)))
True

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
S = Seq2((Matrix([[1, 0], [0, 1]]), Matrix([[1, 0], [1, 1]])),
         left=vector([0, 1]), right=vector([1, 0]))
S
all(S[n] == sum(n.digits(2)) for n in srange(10))

Number of odd entries in Pascal’s triangle¶

Let us consider the number of odd entries in the first $n$ rows of Pascals’s triangle:

Sage

sage: @cached_function
....: def u(n):
....:     if n <= 1:
....:         return n
....:     return 2 * u(n // 2) + u((n+1) // 2)
sage: tuple(u(n) for n in srange(10))
(0, 1, 3, 5, 9, 11, 15, 19, 27, 29)

Python

>>> from sage.all import *
>>> @cached_function
... def u(n):
...     if n <= Integer(1):
...         return n
...     return Integer(2) * u(n // Integer(2)) + u((n+Integer(1)) // Integer(2))
>>> tuple(u(n) for n in srange(Integer(10)))
(0, 1, 3, 5, 9, 11, 15, 19, 27, 29)

Sage Live

@cached_function
def u(n):
    if n <= 1:
        return n
    return 2 * u(n // 2) + u((n+1) // 2)
tuple(u(n) for n in srange(10))

There is a $2$ -regular sequence describing the numbers above as well:

Sage

sage: U = Seq2((Matrix([[3, 0], [2, 1]]), Matrix([[2, 1], [0, 3]])),
....:          left=vector([1, 0]), right=vector([0, 1]))
sage: all(U[n] == u(n) for n in srange(30))
True

Python

>>> from sage.all import *
>>> U = Seq2((Matrix([[Integer(3), Integer(0)], [Integer(2), Integer(1)]]), Matrix([[Integer(2), Integer(1)], [Integer(0), Integer(3)]])),
...          left=vector([Integer(1), Integer(0)]), right=vector([Integer(0), Integer(1)]))
>>> all(U[n] == u(n) for n in srange(Integer(30)))
True

Sage Live

U = Seq2((Matrix([[3, 0], [2, 1]]), Matrix([[2, 1], [0, 3]])),
         left=vector([1, 0]), right=vector([0, 1]))
all(U[n] == u(n) for n in srange(30))

Various¶

AUTHORS:

Daniel Krenn (2016, 2021)
Gabriel F. Lipnik (2021)

ACKNOWLEDGEMENT:

Daniel Krenn is supported by the Austrian Science Fund (FWF): P 24644-N26.
Gabriel F. Lipnik is supported by the Austrian Science Fund (FWF): W 1230.

Classes and Methods¶

exception sage.combinat.regular_sequence.DegeneratedSequenceError[source]¶

Bases: RuntimeError

Exception raised if a degenerated sequence (see is_degenerated()) is detected.

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: Seq2((Matrix([2]), Matrix([3])), vector([1]), vector([1]))
Traceback (most recent call last):
...
DegeneratedSequenceError: degenerated sequence: mu[0]*right != right.
Using such a sequence might lead to wrong results.
You can use 'allow_degenerated_sequence=True' followed
by a call of method .regenerated() for correcting this.

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> Seq2((Matrix([Integer(2)]), Matrix([Integer(3)])), vector([Integer(1)]), vector([Integer(1)]))
Traceback (most recent call last):
...
DegeneratedSequenceError: degenerated sequence: mu[0]*right != right.
Using such a sequence might lead to wrong results.
You can use 'allow_degenerated_sequence=True' followed
by a call of method .regenerated() for correcting this.

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
Seq2((Matrix([2]), Matrix([3])), vector([1]), vector([1]))

class sage.combinat.regular_sequence.RecurrenceParser(k, coefficient_ring)[source]¶

Bases: object

A parser for recurrence relations that allow the construction of a $k$ -linear representation for the sequence satisfying these recurrence relations.

This is used by RegularSequenceRing.from_recurrence() to construct a RegularSequence.

ind(M, m, ll, uu)[source]¶

Determine the index operator corresponding to the recursive sequence as defined in [HKL2022].

INPUT:

M, m – parameters of the recursive sequences, see [HKL2022], Definition 3.1
ll, uu – parameters of the resulting linear representation, see [HKL2022], Theorem A

OUTPUT:

A dictionary which maps both row numbers to subsequence parameters and vice versa, i.e.,

ind[i] – a pair (j, d) representing the sequence $x (k^{j} n + d)$ in the $i$ -th component (0-based) of the resulting linear representation
ind[(j, d)] – the (0-based) row number of the sequence $x (k^{j} n + d)$ in the linear representation

EXAMPLES:

Sage

sage: from sage.combinat.regular_sequence import RecurrenceParser
sage: RP = RecurrenceParser(2, ZZ)
sage: RP.ind(3, 1, -3, 3)
{(0, 0): 0, (1, -1): 3, (1, -2): 2, (1, -3): 1,
(1, 0): 4, (1, 1): 5, (1, 2): 6, (1, 3): 7, (2, -1): 10,
(2, -2): 9, (2, -3): 8, (2, 0): 11, (2, 1): 12, (2, 2): 13,
(2, 3): 14, (2, 4): 15, (2, 5): 16, 0: (0, 0), 1: (1, -3),
10: (2, -1), 11: (2, 0), 12: (2, 1), 13: (2, 2), 14: (2, 3),
15: (2, 4), 16: (2, 5), 2: (1, -2), 3: (1, -1), 4: (1, 0),
5: (1, 1), 6: (1, 2), 7: (1, 3), 8: (2, -3), 9: (2, -2)}

Python

>>> from sage.all import *
>>> from sage.combinat.regular_sequence import RecurrenceParser
>>> RP = RecurrenceParser(Integer(2), ZZ)
>>> RP.ind(Integer(3), Integer(1), -Integer(3), Integer(3))
{(0, 0): 0, (1, -1): 3, (1, -2): 2, (1, -3): 1,
(1, 0): 4, (1, 1): 5, (1, 2): 6, (1, 3): 7, (2, -1): 10,
(2, -2): 9, (2, -3): 8, (2, 0): 11, (2, 1): 12, (2, 2): 13,
(2, 3): 14, (2, 4): 15, (2, 5): 16, 0: (0, 0), 1: (1, -3),
10: (2, -1), 11: (2, 0), 12: (2, 1), 13: (2, 2), 14: (2, 3),
15: (2, 4), 16: (2, 5), 2: (1, -2), 3: (1, -1), 4: (1, 0),
5: (1, 1), 6: (1, 2), 7: (1, 3), 8: (2, -3), 9: (2, -2)}

Sage Live

from sage.combinat.regular_sequence import RecurrenceParser
RP = RecurrenceParser(2, ZZ)
RP.ind(3, 1, -3, 3)

See also

RegularSequenceRing.from_recurrence()

left(recurrence_rules)[source]¶

Construct the vector left of the linear representation of recursive sequences.

INPUT:

recurrence_rules – a namedtuple generated by parameters(); it only needs to contain a field dim (a positive integer)

OUTPUT: a vector

EXAMPLES:

Sage

sage: from collections import namedtuple
sage: from sage.combinat.regular_sequence import RecurrenceParser
sage: RP = RecurrenceParser(2, ZZ)
sage: RRD = namedtuple('recurrence_rules_dim',
....:                  ['dim', 'inhomogeneities'])
sage: recurrence_rules = RRD(dim=5, inhomogeneities={})
sage: RP.left(recurrence_rules)
(1, 0, 0, 0, 0)

Python

>>> from sage.all import *
>>> from collections import namedtuple
>>> from sage.combinat.regular_sequence import RecurrenceParser
>>> RP = RecurrenceParser(Integer(2), ZZ)
>>> RRD = namedtuple('recurrence_rules_dim',
...                  ['dim', 'inhomogeneities'])
>>> recurrence_rules = RRD(dim=Integer(5), inhomogeneities={})
>>> RP.left(recurrence_rules)
(1, 0, 0, 0, 0)

Sage Live

from collections import namedtuple
from sage.combinat.regular_sequence import RecurrenceParser
RP = RecurrenceParser(2, ZZ)
RRD = namedtuple('recurrence_rules_dim',
                 ['dim', 'inhomogeneities'])
recurrence_rules = RRD(dim=5, inhomogeneities={})
RP.left(recurrence_rules)

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: RRD = namedtuple('recurrence_rules_dim',
....:                  ['M', 'm', 'll', 'uu', 'dim', 'inhomogeneities'])
sage: recurrence_rules = RRD(M=3, m=2, ll=0, uu=9, dim=5,
....:                        inhomogeneities={0: Seq2.one_hadamard()})
sage: RP.left(recurrence_rules)
(1, 0, 0, 0, 0, 0, 0, 0)

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> RRD = namedtuple('recurrence_rules_dim',
...                  ['M', 'm', 'll', 'uu', 'dim', 'inhomogeneities'])
>>> recurrence_rules = RRD(M=Integer(3), m=Integer(2), ll=Integer(0), uu=Integer(9), dim=Integer(5),
...                        inhomogeneities={Integer(0): Seq2.one_hadamard()})
>>> RP.left(recurrence_rules)
(1, 0, 0, 0, 0, 0, 0, 0)

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
RRD = namedtuple('recurrence_rules_dim',
                 ['M', 'm', 'll', 'uu', 'dim', 'inhomogeneities'])
recurrence_rules = RRD(M=3, m=2, ll=0, uu=9, dim=5,
                       inhomogeneities={0: Seq2.one_hadamard()})
RP.left(recurrence_rules)

See also

RegularSequenceRing.from_recurrence()

matrix(recurrence_rules, rem, correct_offset=True)[source]¶

Construct the matrix for remainder rem of the linear representation of the sequence represented by recurrence_rules.

INPUT:

recurrence_rules – a namedtuple generated by parameters()
rem – integer between $0$ and $k - 1$
correct_offset – boolean (default: True); if True, then the resulting linear representation has no offset. See [HKL2022] for more information.

OUTPUT: a matrix

EXAMPLES:

The following example illustrates how the coefficients in the right-hand sides of the recurrence relations correspond to the entries of the matrices.

Sage

sage: from sage.combinat.regular_sequence import RecurrenceParser
sage: RP = RecurrenceParser(2, ZZ)
sage: var('n')
n
sage: function('f')
f
sage: M, m, coeffs, initial_values = RP.parse_recurrence([
....:     f(8*n) == -1*f(2*n - 1) + 1*f(2*n + 1),
....:     f(8*n + 1) == -11*f(2*n - 1) + 10*f(2*n) + 11*f(2*n + 1),
....:     f(8*n + 2) == -21*f(2*n - 1) + 20*f(2*n) + 21*f(2*n + 1),
....:     f(8*n + 3) == -31*f(2*n - 1) + 30*f(2*n) + 31*f(2*n + 1),
....:     f(8*n + 4) == -41*f(2*n - 1) + 40*f(2*n) + 41*f(2*n + 1),
....:     f(8*n + 5) == -51*f(2*n - 1) + 50*f(2*n) + 51*f(2*n + 1),
....:     f(8*n + 6) == -61*f(2*n - 1) + 60*f(2*n) + 61*f(2*n + 1),
....:     f(8*n + 7) == -71*f(2*n - 1) + 70*f(2*n) + 71*f(2*n + 1),
....:     f(0) == 0, f(1) == 1, f(2) == 2, f(3) == 3, f(4) == 4,
....:     f(5) == 5, f(6) == 6, f(7) == 7], f, n)
sage: rules = RP.parameters(
....:     M, m, coeffs, initial_values, 0)
sage: RP.matrix(rules, 0, False)
[  0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0]
[  0 -51  50  51   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0 -61  60  61   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0 -71  70  71   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0  -1   0   1   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -11  10  11   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -21  20  21   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -31  30  31   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -41  40  41   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -51  50  51   0   0   0   0   0   0   0   0   0   0   0]
sage: RP.matrix(rules, 1, False)
[  0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1]
[  0   0   0 -11  10  11   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -21  20  21   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -31  30  31   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -41  40  41   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -51  50  51   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -61  60  61   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -71  70  71   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0  -1   0   1   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0 -11  10  11   0   0   0   0   0   0   0   0   0]

Python

>>> from sage.all import *
>>> from sage.combinat.regular_sequence import RecurrenceParser
>>> RP = RecurrenceParser(Integer(2), ZZ)
>>> var('n')
n
>>> function('f')
f
>>> M, m, coeffs, initial_values = RP.parse_recurrence([
...     f(Integer(8)*n) == -Integer(1)*f(Integer(2)*n - Integer(1)) + Integer(1)*f(Integer(2)*n + Integer(1)),
...     f(Integer(8)*n + Integer(1)) == -Integer(11)*f(Integer(2)*n - Integer(1)) + Integer(10)*f(Integer(2)*n) + Integer(11)*f(Integer(2)*n + Integer(1)),
...     f(Integer(8)*n + Integer(2)) == -Integer(21)*f(Integer(2)*n - Integer(1)) + Integer(20)*f(Integer(2)*n) + Integer(21)*f(Integer(2)*n + Integer(1)),
...     f(Integer(8)*n + Integer(3)) == -Integer(31)*f(Integer(2)*n - Integer(1)) + Integer(30)*f(Integer(2)*n) + Integer(31)*f(Integer(2)*n + Integer(1)),
...     f(Integer(8)*n + Integer(4)) == -Integer(41)*f(Integer(2)*n - Integer(1)) + Integer(40)*f(Integer(2)*n) + Integer(41)*f(Integer(2)*n + Integer(1)),
...     f(Integer(8)*n + Integer(5)) == -Integer(51)*f(Integer(2)*n - Integer(1)) + Integer(50)*f(Integer(2)*n) + Integer(51)*f(Integer(2)*n + Integer(1)),
...     f(Integer(8)*n + Integer(6)) == -Integer(61)*f(Integer(2)*n - Integer(1)) + Integer(60)*f(Integer(2)*n) + Integer(61)*f(Integer(2)*n + Integer(1)),
...     f(Integer(8)*n + Integer(7)) == -Integer(71)*f(Integer(2)*n - Integer(1)) + Integer(70)*f(Integer(2)*n) + Integer(71)*f(Integer(2)*n + Integer(1)),
...     f(Integer(0)) == Integer(0), f(Integer(1)) == Integer(1), f(Integer(2)) == Integer(2), f(Integer(3)) == Integer(3), f(Integer(4)) == Integer(4),
...     f(Integer(5)) == Integer(5), f(Integer(6)) == Integer(6), f(Integer(7)) == Integer(7)], f, n)
>>> rules = RP.parameters(
...     M, m, coeffs, initial_values, Integer(0))
>>> RP.matrix(rules, Integer(0), False)
[  0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0]
[  0 -51  50  51   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0 -61  60  61   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0 -71  70  71   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0  -1   0   1   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -11  10  11   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -21  20  21   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -31  30  31   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -41  40  41   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -51  50  51   0   0   0   0   0   0   0   0   0   0   0]
>>> RP.matrix(rules, Integer(1), False)
[  0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1]
[  0   0   0 -11  10  11   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -21  20  21   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -31  30  31   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -41  40  41   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -51  50  51   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -61  60  61   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0 -71  70  71   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0  -1   0   1   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0 -11  10  11   0   0   0   0   0   0   0   0   0]

Sage Live

from sage.combinat.regular_sequence import RecurrenceParser
RP = RecurrenceParser(2, ZZ)
var('n')
function('f')
M, m, coeffs, initial_values = RP.parse_recurrence([
    f(8*n) == -1*f(2*n - 1) + 1*f(2*n + 1),
    f(8*n + 1) == -11*f(2*n - 1) + 10*f(2*n) + 11*f(2*n + 1),
    f(8*n + 2) == -21*f(2*n - 1) + 20*f(2*n) + 21*f(2*n + 1),
    f(8*n + 3) == -31*f(2*n - 1) + 30*f(2*n) + 31*f(2*n + 1),
    f(8*n + 4) == -41*f(2*n - 1) + 40*f(2*n) + 41*f(2*n + 1),
    f(8*n + 5) == -51*f(2*n - 1) + 50*f(2*n) + 51*f(2*n + 1),
    f(8*n + 6) == -61*f(2*n - 1) + 60*f(2*n) + 61*f(2*n + 1),
    f(8*n + 7) == -71*f(2*n - 1) + 70*f(2*n) + 71*f(2*n + 1),
    f(0) == 0, f(1) == 1, f(2) == 2, f(3) == 3, f(4) == 4,
    f(5) == 5, f(6) == 6, f(7) == 7], f, n)
rules = RP.parameters(
    M, m, coeffs, initial_values, 0)
RP.matrix(rules, 0, False)
RP.matrix(rules, 1, False)

Stern–Brocot Sequence:

Sage

sage: SB_rules = RP.parameters(
....:     1, 0, {(0, 0): 1, (1, 0): 1, (1, 1): 1},
....:     {0: 0, 1: 1, 2: 1}, 0)
sage: RP.matrix(SB_rules, 0)
[1 0 0]
[1 1 0]
[0 1 0]
sage: RP.matrix(SB_rules, 1)
[1 1 0]
[0 1 0]
[0 1 1]

Python

>>> from sage.all import *
>>> SB_rules = RP.parameters(
...     Integer(1), Integer(0), {(Integer(0), Integer(0)): Integer(1), (Integer(1), Integer(0)): Integer(1), (Integer(1), Integer(1)): Integer(1)},
...     {Integer(0): Integer(0), Integer(1): Integer(1), Integer(2): Integer(1)}, Integer(0))
>>> RP.matrix(SB_rules, Integer(0))
[1 0 0]
[1 1 0]
[0 1 0]
>>> RP.matrix(SB_rules, Integer(1))
[1 1 0]
[0 1 0]
[0 1 1]

Sage Live

SB_rules = RP.parameters(
    1, 0, {(0, 0): 1, (1, 0): 1, (1, 1): 1},
    {0: 0, 1: 1, 2: 1}, 0)
RP.matrix(SB_rules, 0)
RP.matrix(SB_rules, 1)

Number of Unbordered Factors in the Thue–Morse Sequence:

Sage

sage: M, m, coeffs, initial_values = RP.parse_recurrence([
....:     f(8*n) == 2*f(4*n),
....:     f(8*n + 1) == f(4*n + 1),
....:     f(8*n + 2) == f(4*n + 1) + f(4*n + 3),
....:     f(8*n + 3) == -f(4*n + 1) + f(4*n + 2),
....:     f(8*n + 4) == 2*f(4*n + 2),
....:     f(8*n + 5) == f(4*n + 3),
....:     f(8*n + 6) == -f(4*n + 1) + f(4*n + 2) + f(4*n + 3),
....:     f(8*n + 7) == 2*f(4*n + 1) + f(4*n + 3),
....:     f(0) == 1, f(1) == 2, f(2) == 2, f(3) == 4, f(4) == 2,
....:     f(5) == 4, f(6) == 6, f(7) == 0, f(8) == 4, f(9) == 4,
....:     f(10) == 4, f(11) == 4, f(12) == 12, f(13) == 0, f(14) == 4,
....:     f(15) == 4, f(16) == 8, f(17) == 4, f(18) == 8, f(19) == 0,
....:     f(20) == 8, f(21) == 4, f(22) == 4, f(23) == 8], f, n)
sage: UB_rules = RP.parameters(
....:     M, m, coeffs, initial_values, 3)
sage: RP.matrix(UB_rules, 0)
[ 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  2  0  0  0  0  0  0  0  0  0 -1  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  1  0  0  0  0  0  0 -4  0  0]
[ 0  0  0  0 -1  1  0  0  0  0  0  0  0  4  2  0]
[ 0  0  0  0  0  2  0  0  0  0  0  0  0 -2  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0 -1  1  1  0  0  0  0  0  0  2  2  0]
[ 0  0  0  0  2  0  1  0  0  0  0  0  0 -8 -4 -4]
[ 0  0  0  0  0  0  0  2  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0]
sage: RP.matrix(UB_rules, 1)
[ 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  2  0  0  0  0  0  0  0 -2  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0 -1  1  1  0  0  0  0  0  0  2  2  0]
[ 0  0  0  0  2  0  1  0  0  0  0  0  0 -8 -4 -4]
[ 0  0  0  0  0  0  0  2  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  1  0  1  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0 -1  1  0  0  0  2  0  0]
[ 0  0  0  0  0  0  0  0  0  2  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]

Python

>>> from sage.all import *
>>> M, m, coeffs, initial_values = RP.parse_recurrence([
...     f(Integer(8)*n) == Integer(2)*f(Integer(4)*n),
...     f(Integer(8)*n + Integer(1)) == f(Integer(4)*n + Integer(1)),
...     f(Integer(8)*n + Integer(2)) == f(Integer(4)*n + Integer(1)) + f(Integer(4)*n + Integer(3)),
...     f(Integer(8)*n + Integer(3)) == -f(Integer(4)*n + Integer(1)) + f(Integer(4)*n + Integer(2)),
...     f(Integer(8)*n + Integer(4)) == Integer(2)*f(Integer(4)*n + Integer(2)),
...     f(Integer(8)*n + Integer(5)) == f(Integer(4)*n + Integer(3)),
...     f(Integer(8)*n + Integer(6)) == -f(Integer(4)*n + Integer(1)) + f(Integer(4)*n + Integer(2)) + f(Integer(4)*n + Integer(3)),
...     f(Integer(8)*n + Integer(7)) == Integer(2)*f(Integer(4)*n + Integer(1)) + f(Integer(4)*n + Integer(3)),
...     f(Integer(0)) == Integer(1), f(Integer(1)) == Integer(2), f(Integer(2)) == Integer(2), f(Integer(3)) == Integer(4), f(Integer(4)) == Integer(2),
...     f(Integer(5)) == Integer(4), f(Integer(6)) == Integer(6), f(Integer(7)) == Integer(0), f(Integer(8)) == Integer(4), f(Integer(9)) == Integer(4),
...     f(Integer(10)) == Integer(4), f(Integer(11)) == Integer(4), f(Integer(12)) == Integer(12), f(Integer(13)) == Integer(0), f(Integer(14)) == Integer(4),
...     f(Integer(15)) == Integer(4), f(Integer(16)) == Integer(8), f(Integer(17)) == Integer(4), f(Integer(18)) == Integer(8), f(Integer(19)) == Integer(0),
...     f(Integer(20)) == Integer(8), f(Integer(21)) == Integer(4), f(Integer(22)) == Integer(4), f(Integer(23)) == Integer(8)], f, n)
>>> UB_rules = RP.parameters(
...     M, m, coeffs, initial_values, Integer(3))
>>> RP.matrix(UB_rules, Integer(0))
[ 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  2  0  0  0  0  0  0  0  0  0 -1  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  1  0  0  0  0  0  0 -4  0  0]
[ 0  0  0  0 -1  1  0  0  0  0  0  0  0  4  2  0]
[ 0  0  0  0  0  2  0  0  0  0  0  0  0 -2  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0 -1  1  1  0  0  0  0  0  0  2  2  0]
[ 0  0  0  0  2  0  1  0  0  0  0  0  0 -8 -4 -4]
[ 0  0  0  0  0  0  0  2  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0]
>>> RP.matrix(UB_rules, Integer(1))
[ 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  2  0  0  0  0  0  0  0 -2  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0 -1  1  1  0  0  0  0  0  0  2  2  0]
[ 0  0  0  0  2  0  1  0  0  0  0  0  0 -8 -4 -4]
[ 0  0  0  0  0  0  0  2  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  1  0  1  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0 -1  1  0  0  0  2  0  0]
[ 0  0  0  0  0  0  0  0  0  2  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]

Sage Live

M, m, coeffs, initial_values = RP.parse_recurrence([
    f(8*n) == 2*f(4*n),
    f(8*n + 1) == f(4*n + 1),
    f(8*n + 2) == f(4*n + 1) + f(4*n + 3),
    f(8*n + 3) == -f(4*n + 1) + f(4*n + 2),
    f(8*n + 4) == 2*f(4*n + 2),
    f(8*n + 5) == f(4*n + 3),
    f(8*n + 6) == -f(4*n + 1) + f(4*n + 2) + f(4*n + 3),
    f(8*n + 7) == 2*f(4*n + 1) + f(4*n + 3),
    f(0) == 1, f(1) == 2, f(2) == 2, f(3) == 4, f(4) == 2,
    f(5) == 4, f(6) == 6, f(7) == 0, f(8) == 4, f(9) == 4,
    f(10) == 4, f(11) == 4, f(12) == 12, f(13) == 0, f(14) == 4,
    f(15) == 4, f(16) == 8, f(17) == 4, f(18) == 8, f(19) == 0,
    f(20) == 8, f(21) == 4, f(22) == 4, f(23) == 8], f, n)
UB_rules = RP.parameters(
    M, m, coeffs, initial_values, 3)
RP.matrix(UB_rules, 0)
RP.matrix(UB_rules, 1)

See also

RegularSequenceRing.from_recurrence()

parameters(M, m, coeffs, initial_values, offset=0, inhomogeneities={})[source]¶

Determine parameters from recurrence relations as admissible in RegularSequenceRing.from_recurrence().

INPUT:

All parameters are explained in the high-level method RegularSequenceRing.from_recurrence().

OUTPUT: a namedtuple recurrence_rules consisting of

M, m, l, u, offset – parameters of the recursive sequences, see [HKL2022], Definition 3.1
ll, uu, n1, dim – parameters and dimension of the resulting linear representation, see [HKL2022], Theorem A
coeffs – dictionary mapping (r, j) to the coefficients $c_{r, j}$ as given in [HKL2022], Equation (3.1). If coeffs[(r, j)] is not given for some r and j, then it is assumed to be zero.
initial_values – dictionary mapping integers n to the n-th value of the sequence
inhomogeneities – dictionary mapping integers r to the inhomogeneity $g_{r}$ as given in [HKL2022], Corollary D

EXAMPLES:

Sage

sage: from sage.combinat.regular_sequence import RecurrenceParser
sage: RP = RecurrenceParser(2, ZZ)
sage: RP.parameters(2, 1,
....: {(0, -2): 3, (0, 0): 1, (0, 1): 2, (1, -2): 6, (1, 0): 4,
....: (1, 1): 5, (2, -2): 9, (2, 0): 7, (2, 1): 8, (3, -2): 12,
....: (3, 0): 10, (3, 1): 11}, {0: 1, 1: 2, 2: 1, 3: 4}, 0, {0: 1})
recurrence_rules(M=2, m=1, l=-2, u=1, ll=-6, uu=3, dim=14,
coeffs={(0, -2): 3, (0, 0): 1, (0, 1): 2, (1, -2): 6, (1, 0): 4,
(1, 1): 5, (2, -2): 9, (2, 0): 7, (2, 1): 8, (3, -2): 12,
(3, 0): 10, (3, 1): 11}, initial_values={0: 1, 1: 2, 2: 1, 3: 4,
4: 13, 5: 30, 6: 48, 7: 66, 8: 77, 9: 208, 10: 340, 11: 472,
12: 220, 13: 600, -6: 0, -5: 0, -4: 0, -3: 0, -2: 0, -1: 0},
offset=1, n1=3, inhomogeneities={0: 2-regular sequence 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, ...})

Python

>>> from sage.all import *
>>> from sage.combinat.regular_sequence import RecurrenceParser
>>> RP = RecurrenceParser(Integer(2), ZZ)
>>> RP.parameters(Integer(2), Integer(1),
... {(Integer(0), -Integer(2)): Integer(3), (Integer(0), Integer(0)): Integer(1), (Integer(0), Integer(1)): Integer(2), (Integer(1), -Integer(2)): Integer(6), (Integer(1), Integer(0)): Integer(4),
... (Integer(1), Integer(1)): Integer(5), (Integer(2), -Integer(2)): Integer(9), (Integer(2), Integer(0)): Integer(7), (Integer(2), Integer(1)): Integer(8), (Integer(3), -Integer(2)): Integer(12),
... (Integer(3), Integer(0)): Integer(10), (Integer(3), Integer(1)): Integer(11)}, {Integer(0): Integer(1), Integer(1): Integer(2), Integer(2): Integer(1), Integer(3): Integer(4)}, Integer(0), {Integer(0): Integer(1)})
recurrence_rules(M=2, m=1, l=-2, u=1, ll=-6, uu=3, dim=14,
coeffs={(0, -2): 3, (0, 0): 1, (0, 1): 2, (1, -2): 6, (1, 0): 4,
(1, 1): 5, (2, -2): 9, (2, 0): 7, (2, 1): 8, (3, -2): 12,
(3, 0): 10, (3, 1): 11}, initial_values={0: 1, 1: 2, 2: 1, 3: 4,
4: 13, 5: 30, 6: 48, 7: 66, 8: 77, 9: 208, 10: 340, 11: 472,
12: 220, 13: 600, -6: 0, -5: 0, -4: 0, -3: 0, -2: 0, -1: 0},
offset=1, n1=3, inhomogeneities={0: 2-regular sequence 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, ...})

Sage Live

from sage.combinat.regular_sequence import RecurrenceParser
RP = RecurrenceParser(2, ZZ)
RP.parameters(2, 1,
{(0, -2): 3, (0, 0): 1, (0, 1): 2, (1, -2): 6, (1, 0): 4,
(1, 1): 5, (2, -2): 9, (2, 0): 7, (2, 1): 8, (3, -2): 12,
(3, 0): 10, (3, 1): 11}, {0: 1, 1: 2, 2: 1, 3: 4}, 0, {0: 1})

See also

RegularSequenceRing.from_recurrence()

parse_direct_arguments(M, m, coeffs, initial_values)[source]¶

Check whether the direct arguments as admissible in RegularSequenceRing.from_recurrence() are valid.

INPUT:

All parameters are explained in the high-level method RegularSequenceRing.from_recurrence().

OUTPUT: a tuple consisting of the input parameters

EXAMPLES:

Sage

sage: from sage.combinat.regular_sequence import RecurrenceParser
sage: RP = RecurrenceParser(2, ZZ)
sage: RP.parse_direct_arguments(2, 1,
....:     {(0, -2): 3, (0, 0): 1, (0, 1): 2,
....:      (1, -2): 6, (1, 0): 4, (1, 1): 5,
....:      (2, -2): 9, (2, 0): 7, (2, 1): 8,
....:      (3, -2): 12, (3, 0): 10, (3, 1): 11},
....:     {0: 1, 1: 2, 2: 1})
(2, 1, {(0, -2): 3, (0, 0): 1, (0, 1): 2,
(1, -2): 6, (1, 0): 4, (1, 1): 5,
(2, -2): 9, (2, 0): 7, (2, 1): 8,
(3, -2): 12, (3, 0): 10, (3, 1): 11},
{0: 1, 1: 2, 2: 1})

Python

>>> from sage.all import *
>>> from sage.combinat.regular_sequence import RecurrenceParser
>>> RP = RecurrenceParser(Integer(2), ZZ)
>>> RP.parse_direct_arguments(Integer(2), Integer(1),
...     {(Integer(0), -Integer(2)): Integer(3), (Integer(0), Integer(0)): Integer(1), (Integer(0), Integer(1)): Integer(2),
...      (Integer(1), -Integer(2)): Integer(6), (Integer(1), Integer(0)): Integer(4), (Integer(1), Integer(1)): Integer(5),
...      (Integer(2), -Integer(2)): Integer(9), (Integer(2), Integer(0)): Integer(7), (Integer(2), Integer(1)): Integer(8),
...      (Integer(3), -Integer(2)): Integer(12), (Integer(3), Integer(0)): Integer(10), (Integer(3), Integer(1)): Integer(11)},
...     {Integer(0): Integer(1), Integer(1): Integer(2), Integer(2): Integer(1)})
(2, 1, {(0, -2): 3, (0, 0): 1, (0, 1): 2,
(1, -2): 6, (1, 0): 4, (1, 1): 5,
(2, -2): 9, (2, 0): 7, (2, 1): 8,
(3, -2): 12, (3, 0): 10, (3, 1): 11},
{0: 1, 1: 2, 2: 1})

Sage Live

from sage.combinat.regular_sequence import RecurrenceParser
RP = RecurrenceParser(2, ZZ)
RP.parse_direct_arguments(2, 1,
    {(0, -2): 3, (0, 0): 1, (0, 1): 2,
     (1, -2): 6, (1, 0): 4, (1, 1): 5,
     (2, -2): 9, (2, 0): 7, (2, 1): 8,
     (3, -2): 12, (3, 0): 10, (3, 1): 11},
    {0: 1, 1: 2, 2: 1})

Stern–Brocot Sequence:

Sage

sage: RP.parse_direct_arguments(1, 0,
....:     {(0, 0): 1, (1, 0): 1, (1, 1): 1},
....:     {0: 0, 1: 1})
(1, 0, {(0, 0): 1, (1, 0): 1, (1, 1): 1}, {0: 0, 1: 1})

Python

>>> from sage.all import *
>>> RP.parse_direct_arguments(Integer(1), Integer(0),
...     {(Integer(0), Integer(0)): Integer(1), (Integer(1), Integer(0)): Integer(1), (Integer(1), Integer(1)): Integer(1)},
...     {Integer(0): Integer(0), Integer(1): Integer(1)})
(1, 0, {(0, 0): 1, (1, 0): 1, (1, 1): 1}, {0: 0, 1: 1})

Sage Live

RP.parse_direct_arguments(1, 0,
    {(0, 0): 1, (1, 0): 1, (1, 1): 1},
    {0: 0, 1: 1})

See also

RegularSequenceRing.from_recurrence()

parse_recurrence(equations, function, var)[source]¶

Parse recurrence relations as admissible in RegularSequenceRing.from_recurrence().

INPUT:

All parameters are explained in the high-level method RegularSequenceRing.from_recurrence().

OUTPUT: a tuple consisting of

M, m – see RegularSequenceRing.from_recurrence()
coeffs – see RegularSequenceRing.from_recurrence()
initial_values – see RegularSequenceRing.from_recurrence()

EXAMPLES:

Sage

sage: from sage.combinat.regular_sequence import RecurrenceParser
sage: RP = RecurrenceParser(2, ZZ)
sage: var('n')
n
sage: function('f')
f
sage: RP.parse_recurrence([
....:     f(4*n) == f(2*n) + 2*f(2*n + 1) + 3*f(2*n - 2),
....:     f(4*n + 1) == 4*f(2*n) + 5*f(2*n + 1) + 6*f(2*n - 2),
....:     f(4*n + 2) == 7*f(2*n) + 8*f(2*n + 1) + 9*f(2*n - 2),
....:     f(4*n + 3) == 10*f(2*n) + 11*f(2*n + 1) + 12*f(2*n - 2),
....:     f(0) == 1, f(1) == 2, f(2) == 1], f, n)
(2, 1, {(0, -2): 3, (0, 0): 1, (0, 1): 2, (1, -2): 6, (1, 0): 4,
(1, 1): 5, (2, -2): 9, (2, 0): 7, (2, 1): 8, (3, -2): 12, (3, 0): 10,
(3, 1): 11}, {0: 1, 1: 2, 2: 1})

Python

>>> from sage.all import *
>>> from sage.combinat.regular_sequence import RecurrenceParser
>>> RP = RecurrenceParser(Integer(2), ZZ)
>>> var('n')
n
>>> function('f')
f
>>> RP.parse_recurrence([
...     f(Integer(4)*n) == f(Integer(2)*n) + Integer(2)*f(Integer(2)*n + Integer(1)) + Integer(3)*f(Integer(2)*n - Integer(2)),
...     f(Integer(4)*n + Integer(1)) == Integer(4)*f(Integer(2)*n) + Integer(5)*f(Integer(2)*n + Integer(1)) + Integer(6)*f(Integer(2)*n - Integer(2)),
...     f(Integer(4)*n + Integer(2)) == Integer(7)*f(Integer(2)*n) + Integer(8)*f(Integer(2)*n + Integer(1)) + Integer(9)*f(Integer(2)*n - Integer(2)),
...     f(Integer(4)*n + Integer(3)) == Integer(10)*f(Integer(2)*n) + Integer(11)*f(Integer(2)*n + Integer(1)) + Integer(12)*f(Integer(2)*n - Integer(2)),
...     f(Integer(0)) == Integer(1), f(Integer(1)) == Integer(2), f(Integer(2)) == Integer(1)], f, n)
(2, 1, {(0, -2): 3, (0, 0): 1, (0, 1): 2, (1, -2): 6, (1, 0): 4,
(1, 1): 5, (2, -2): 9, (2, 0): 7, (2, 1): 8, (3, -2): 12, (3, 0): 10,
(3, 1): 11}, {0: 1, 1: 2, 2: 1})

Sage Live

from sage.combinat.regular_sequence import RecurrenceParser
RP = RecurrenceParser(2, ZZ)
var('n')
function('f')
RP.parse_recurrence([
    f(4*n) == f(2*n) + 2*f(2*n + 1) + 3*f(2*n - 2),
    f(4*n + 1) == 4*f(2*n) + 5*f(2*n + 1) + 6*f(2*n - 2),
    f(4*n + 2) == 7*f(2*n) + 8*f(2*n + 1) + 9*f(2*n - 2),
    f(4*n + 3) == 10*f(2*n) + 11*f(2*n + 1) + 12*f(2*n - 2),
    f(0) == 1, f(1) == 2, f(2) == 1], f, n)

Stern–Brocot Sequence:

Sage

sage: RP.parse_recurrence([
....:    f(2*n) == f(n), f(2*n + 1) == f(n) + f(n + 1),
....:    f(0) == 0, f(1) == 1], f, n)
(1, 0, {(0, 0): 1, (1, 0): 1, (1, 1): 1}, {0: 0, 1: 1})

Python

>>> from sage.all import *
>>> RP.parse_recurrence([
...    f(Integer(2)*n) == f(n), f(Integer(2)*n + Integer(1)) == f(n) + f(n + Integer(1)),
...    f(Integer(0)) == Integer(0), f(Integer(1)) == Integer(1)], f, n)
(1, 0, {(0, 0): 1, (1, 0): 1, (1, 1): 1}, {0: 0, 1: 1})

Sage Live

RP.parse_recurrence([
   f(2*n) == f(n), f(2*n + 1) == f(n) + f(n + 1),
   f(0) == 0, f(1) == 1], f, n)

See also

RegularSequenceRing.from_recurrence()

right(recurrence_rules)[source]¶

Construct the vector right of the linear representation of the sequence induced by recurrence_rules.

INPUT:

recurrence_rules – a namedtuple generated by parameters()

OUTPUT: a vector

See also

RegularSequenceRing.from_recurrence()

shifted_inhomogeneities(recurrence_rules)[source]¶

Return a dictionary of all needed shifted inhomogeneities as described in the proof of Corollary D in [HKL2022].

INPUT:

recurrence_rules – a namedtuple generated by parameters()

OUTPUT:

A dictionary mapping $r$ to the regular sequence $\sum_{i} g_{r} (n + i)$ for $g_{r}$ as given in [HKL2022], Corollary D, and $i$ between $⌊ ℓ^{'} / k^{M} ⌋$ and $⌊ (k^{M - 1} - k^{m} + u^{'}) / k^{M} ⌋ + 1$ ; see [HKL2022], proof of Corollary D. The first blocks of the corresponding vector-valued sequence (obtained from its linear representation) correspond to the sequences $g_{r} (n + i)$ where $i$ is as in the sum above; the remaining blocks consist of other shifts which are required for the regular sequence.

EXAMPLES:

Sage

sage: from collections import namedtuple
sage: from sage.combinat.regular_sequence import RecurrenceParser
sage: RP = RecurrenceParser(2, ZZ)
sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: S = Seq2((Matrix([[1, 0], [0, 1]]), Matrix([[1, 0], [1, 1]])),
....:          left=vector([0, 1]), right=vector([1, 0]))
sage: S
2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...
sage: RR = namedtuple('recurrence_rules',
....:                  ['M', 'm', 'll', 'uu', 'inhomogeneities'])
sage: recurrence_rules = RR(M=3, m=0, ll=-14, uu=14,
....:                       inhomogeneities={0: S, 1: S})
sage: SI = RP.shifted_inhomogeneities(recurrence_rules)
sage: SI
{0: 2-regular sequence 4, 5, 7, 9, 11, 11, 11, 12, 13, 13, ...,
 1: 2-regular sequence 4, 5, 7, 9, 11, 11, 11, 12, 13, 13, ...}

Python

>>> from sage.all import *
>>> from collections import namedtuple
>>> from sage.combinat.regular_sequence import RecurrenceParser
>>> RP = RecurrenceParser(Integer(2), ZZ)
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> S = Seq2((Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(1), Integer(0)], [Integer(1), Integer(1)]])),
...          left=vector([Integer(0), Integer(1)]), right=vector([Integer(1), Integer(0)]))
>>> S
2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...
>>> RR = namedtuple('recurrence_rules',
...                  ['M', 'm', 'll', 'uu', 'inhomogeneities'])
>>> recurrence_rules = RR(M=Integer(3), m=Integer(0), ll=-Integer(14), uu=Integer(14),
...                       inhomogeneities={Integer(0): S, Integer(1): S})
>>> SI = RP.shifted_inhomogeneities(recurrence_rules)
>>> SI
{0: 2-regular sequence 4, 5, 7, 9, 11, 11, 11, 12, 13, 13, ...,
 1: 2-regular sequence 4, 5, 7, 9, 11, 11, 11, 12, 13, 13, ...}

Sage Live

from collections import namedtuple
from sage.combinat.regular_sequence import RecurrenceParser
RP = RecurrenceParser(2, ZZ)
Seq2 = RegularSequenceRing(2, ZZ)
S = Seq2((Matrix([[1, 0], [0, 1]]), Matrix([[1, 0], [1, 1]])),
         left=vector([0, 1]), right=vector([1, 0]))
S
RR = namedtuple('recurrence_rules',
                 ['M', 'm', 'll', 'uu', 'inhomogeneities'])
recurrence_rules = RR(M=3, m=0, ll=-14, uu=14,
                      inhomogeneities={0: S, 1: S})
SI = RP.shifted_inhomogeneities(recurrence_rules)
SI

The first blocks of the corresponding vector-valued sequence correspond to the corresponding shifts of the inhomogeneity. In this particular case, there are no other blocks:

Sage

sage: lower = -2
sage: upper = 3
sage: SI[0].dimension() == S.dimension() * (upper - lower + 1)
True
sage: all(
....:     Seq2(
....:         SI[0].mu,
....:         vector((i - lower)*[0, 0] + list(S.left) + (upper - i)*[0, 0]),
....:         SI[0].right)
....:     == S.subsequence(1, i)
....:     for i in range(lower, upper+1))
True

Python

>>> from sage.all import *
>>> lower = -Integer(2)
>>> upper = Integer(3)
>>> SI[Integer(0)].dimension() == S.dimension() * (upper - lower + Integer(1))
True
>>> all(
...     Seq2(
...         SI[Integer(0)].mu,
...         vector((i - lower)*[Integer(0), Integer(0)] + list(S.left) + (upper - i)*[Integer(0), Integer(0)]),
...         SI[Integer(0)].right)
...     == S.subsequence(Integer(1), i)
...     for i in range(lower, upper+Integer(1)))
True

Sage Live

lower = -2
upper = 3
SI[0].dimension() == S.dimension() * (upper - lower + 1)
all(
    Seq2(
        SI[0].mu,
        vector((i - lower)*[0, 0] + list(S.left) + (upper - i)*[0, 0]),
        SI[0].right)
    == S.subsequence(1, i)
    for i in range(lower, upper+1))

See also

RegularSequenceRing.from_recurrence()

v_eval_n(recurrence_rules, n)[source]¶

Return the vector $v (n)$ as given in [HKL2022], Theorem A.

INPUT:

recurrence_rules – a namedtuple generated by parameters()
n – integer

OUTPUT: a vector

EXAMPLES:

Stern–Brocot Sequence:

Sage

sage: from sage.combinat.regular_sequence import RecurrenceParser
sage: RP = RecurrenceParser(2, ZZ)
sage: SB_rules = RP.parameters(
....:     1, 0, {(0, 0): 1, (1, 0): 1, (1, 1): 1},
....:     {0: 0, 1: 1, 2: 1}, 0)
sage: RP.v_eval_n(SB_rules, 0)
(0, 1, 1)

Python

>>> from sage.all import *
>>> from sage.combinat.regular_sequence import RecurrenceParser
>>> RP = RecurrenceParser(Integer(2), ZZ)
>>> SB_rules = RP.parameters(
...     Integer(1), Integer(0), {(Integer(0), Integer(0)): Integer(1), (Integer(1), Integer(0)): Integer(1), (Integer(1), Integer(1)): Integer(1)},
...     {Integer(0): Integer(0), Integer(1): Integer(1), Integer(2): Integer(1)}, Integer(0))
>>> RP.v_eval_n(SB_rules, Integer(0))
(0, 1, 1)

Sage Live

from sage.combinat.regular_sequence import RecurrenceParser
RP = RecurrenceParser(2, ZZ)
SB_rules = RP.parameters(
    1, 0, {(0, 0): 1, (1, 0): 1, (1, 1): 1},
    {0: 0, 1: 1, 2: 1}, 0)
RP.v_eval_n(SB_rules, 0)

See also

RegularSequenceRing.from_recurrence()

values(M, m, l, u, ll, coeffs, initial_values, last_value_needed, offset, inhomogeneities)[source]¶

Determine enough values of the corresponding recursive sequence by applying the recurrence relations given in RegularSequenceRing.from_recurrence() to the values given in initial_values.

INPUT:

M, m, l, u, offset – parameters of the recursive sequences, see [HKL2022], Definition 3.1
ll – parameter of the resulting linear representation, see [HKL2022], Theorem A
coeffs – dictionary where coeffs[(r, j)] is the coefficient $c_{r, j}$ as given in RegularSequenceRing.from_recurrence(). If coeffs[(r, j)] is not given for some r and j, then it is assumed to be zero.
initial_values – dictionary mapping integers n to the n-th value of the sequence
last_value_needed – last initial value which is needed to determine the linear representation
inhomogeneities – dictionary mapping integers r to the inhomogeneity $g_{r}$ as given in [HKL2022], Corollary D

OUTPUT:

A dictionary mapping integers n to the n-th value of the sequence for all n up to last_value_needed.

EXAMPLES:

Stern–Brocot Sequence:

Sage

sage: from sage.combinat.regular_sequence import RecurrenceParser
sage: RP = RecurrenceParser(2, ZZ)
sage: RP.values(M=1, m=0, l=0, u=1, ll=0,
....:     coeffs={(0, 0): 1, (1, 0): 1, (1, 1): 1},
....:     initial_values={0: 0, 1: 1, 2: 1}, last_value_needed=20,
....:     offset=0, inhomogeneities={})
{0: 0, 1: 1, 2: 1, 3: 2, 4: 1, 5: 3, 6: 2, 7: 3, 8: 1, 9: 4, 10: 3,
11: 5, 12: 2, 13: 5, 14: 3, 15: 4, 16: 1, 17: 5, 18: 4, 19: 7, 20: 3}

Python

>>> from sage.all import *
>>> from sage.combinat.regular_sequence import RecurrenceParser
>>> RP = RecurrenceParser(Integer(2), ZZ)
>>> RP.values(M=Integer(1), m=Integer(0), l=Integer(0), u=Integer(1), ll=Integer(0),
...     coeffs={(Integer(0), Integer(0)): Integer(1), (Integer(1), Integer(0)): Integer(1), (Integer(1), Integer(1)): Integer(1)},
...     initial_values={Integer(0): Integer(0), Integer(1): Integer(1), Integer(2): Integer(1)}, last_value_needed=Integer(20),
...     offset=Integer(0), inhomogeneities={})
{0: 0, 1: 1, 2: 1, 3: 2, 4: 1, 5: 3, 6: 2, 7: 3, 8: 1, 9: 4, 10: 3,
11: 5, 12: 2, 13: 5, 14: 3, 15: 4, 16: 1, 17: 5, 18: 4, 19: 7, 20: 3}

Sage Live

from sage.combinat.regular_sequence import RecurrenceParser
RP = RecurrenceParser(2, ZZ)
RP.values(M=1, m=0, l=0, u=1, ll=0,
    coeffs={(0, 0): 1, (1, 0): 1, (1, 1): 1},
    initial_values={0: 0, 1: 1, 2: 1}, last_value_needed=20,
    offset=0, inhomogeneities={})

See also

RegularSequenceRing.from_recurrence()

class sage.combinat.regular_sequence.RegularSequence(parent, mu, left=None, right=None)[source]¶

Bases: RecognizableSeries

A $k$ -regular sequence.

INPUT:

parent – an instance of RegularSequenceRing
mu – a family of square matrices, all of which have the same dimension. The indices of this family are $0, . . ., k - 1$ . mu may be a list or tuple of cardinality $k$ as well. See also mu().
left – (default: None) a vector. When evaluating the sequence, this vector is multiplied from the left to the matrix product. If None, then this multiplication is skipped.
right – (default: None) a vector. When evaluating the sequence, this vector is multiplied from the right to the matrix product. If None, then this multiplication is skipped.

When created via the parent RegularSequenceRing, then the following option is available.

allow_degenerated_sequence – boolean (default: False); if set, then there will be no check if the input is a degenerated sequence (see is_degenerated()). Otherwise the input is checked and a DegeneratedSequenceError is raised if such a sequence is detected.

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: S = Seq2((Matrix([[3, 0], [6, 1]]), Matrix([[0, 1], [-6, 5]])),
....:          vector([1, 0]), vector([0, 1])); S
2-regular sequence 0, 1, 3, 5, 9, 11, 15, 19, 27, 29, ...

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> S = Seq2((Matrix([[Integer(3), Integer(0)], [Integer(6), Integer(1)]]), Matrix([[Integer(0), Integer(1)], [-Integer(6), Integer(5)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(0), Integer(1)])); S
2-regular sequence 0, 1, 3, 5, 9, 11, 15, 19, 27, 29, ...

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
S = Seq2((Matrix([[3, 0], [6, 1]]), Matrix([[0, 1], [-6, 5]])),
         vector([1, 0]), vector([0, 1])); S

We can access the coefficients of a sequence by

Sage

sage: S[5]
11

Python

>>> from sage.all import *
>>> S[Integer(5)]
11

Sage Live

S[5]

or iterating over the first, say $10$ , by

Sage

sage: from itertools import islice
sage: list(islice(S, 10))
[0, 1, 3, 5, 9, 11, 15, 19, 27, 29]

Python

>>> from sage.all import *
>>> from itertools import islice
>>> list(islice(S, Integer(10)))
[0, 1, 3, 5, 9, 11, 15, 19, 27, 29]

Sage Live

from itertools import islice
list(islice(S, 10))

backward_differences(**kwds)[source]¶

Return the sequence of backward differences of this $k$ -regular sequence.

INPUT:

minimize – (default: None) a boolean or None. If True, then minimized() is called after the operation, if False, then not. If this argument is None, then the default specified by the parent’s minimize_results is used.

OUTPUT: a RegularSequence

Note

The coefficient to the index $- 1$ is $0$ .

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: C = Seq2((Matrix([[2, 0], [2, 1]]), Matrix([[0, 1], [-2, 3]])),
....:          vector([1, 0]), vector([0, 1]))
sage: C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
sage: C.backward_differences()
2-regular sequence 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> C = Seq2((Matrix([[Integer(2), Integer(0)], [Integer(2), Integer(1)]]), Matrix([[Integer(0), Integer(1)], [-Integer(2), Integer(3)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(0), Integer(1)]))
>>> C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
>>> C.backward_differences()
2-regular sequence 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
C = Seq2((Matrix([[2, 0], [2, 1]]), Matrix([[0, 1], [-2, 3]])),
         vector([1, 0]), vector([0, 1]))
C
C.backward_differences()

Sage

sage: E = Seq2((Matrix([[0, 1], [0, 1]]), Matrix([[0, 0], [0, 1]])),
....:          vector([1, 0]), vector([1, 1]))
sage: E
2-regular sequence 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
sage: E.backward_differences()
2-regular sequence 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, ...

Python

>>> from sage.all import *
>>> E = Seq2((Matrix([[Integer(0), Integer(1)], [Integer(0), Integer(1)]]), Matrix([[Integer(0), Integer(0)], [Integer(0), Integer(1)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(1), Integer(1)]))
>>> E
2-regular sequence 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
>>> E.backward_differences()
2-regular sequence 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, ...

Sage Live

E = Seq2((Matrix([[0, 1], [0, 1]]), Matrix([[0, 0], [0, 1]])),
         vector([1, 0]), vector([1, 1]))
E
E.backward_differences()

coefficient_of_n(n, **kwds)[source]¶

Return the $n$ -th entry of this sequence.

INPUT:

n – nonnegative integer

OUTPUT: an element of the universe of the sequence

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: S = Seq2((Matrix([[1, 0], [0, 1]]), Matrix([[0, -1], [1, 2]])),
....:          left=vector([0, 1]), right=vector([1, 0]))
sage: S[7]
3

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> S = Seq2((Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(0), -Integer(1)], [Integer(1), Integer(2)]])),
...          left=vector([Integer(0), Integer(1)]), right=vector([Integer(1), Integer(0)]))
>>> S[Integer(7)]
3

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
S = Seq2((Matrix([[1, 0], [0, 1]]), Matrix([[0, -1], [1, 2]])),
         left=vector([0, 1]), right=vector([1, 0]))
S[7]

This is equivalent to:

Sage

sage: S.coefficient_of_n(7)
3

Python

>>> from sage.all import *
>>> S.coefficient_of_n(Integer(7))
3

Sage Live

S.coefficient_of_n(7)

convolution(*args, **kwds)[source]¶

Return the product of this $k$ -regular sequence with other, where the multiplication is convolution of power series.

The operator $*$ is mapped to convolution().

INPUT:

other – a RegularSequence
minimize – (default: None) a boolean or None. If True, then minimized() is called after the operation, if False, then not. If this argument is None, then the default specified by the parent’s minimize_results is used.

OUTPUT: a RegularSequence

ALGORITHM:

See pdf attached to github pull request #35894 which contains a draft describing the details of the used algorithm.

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: E = Seq2((Matrix([[0, 1], [0, 1]]), Matrix([[0, 0], [0, 1]])),
....:          vector([1, 0]), vector([1, 1]))
sage: E
2-regular sequence 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> E = Seq2((Matrix([[Integer(0), Integer(1)], [Integer(0), Integer(1)]]), Matrix([[Integer(0), Integer(0)], [Integer(0), Integer(1)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(1), Integer(1)]))
>>> E
2-regular sequence 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
E = Seq2((Matrix([[0, 1], [0, 1]]), Matrix([[0, 0], [0, 1]])),
         vector([1, 0]), vector([1, 1]))
E

We can build the convolution (in the sense of power-series) of $E$ by itself via:

Sage

sage: E.convolution(E)
2-regular sequence 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, ...

Python

>>> from sage.all import *
>>> E.convolution(E)
2-regular sequence 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, ...

Sage Live

E.convolution(E)

This is the same as using multiplication operator:

Sage

sage: E * E
2-regular sequence 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, ...

Python

>>> from sage.all import *
>>> E * E
2-regular sequence 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, ...

Sage Live

E * E

Building partial_sums() can also be seen as a convolution:

Sage

sage: o = Seq2.one_hadamard()
sage: E * o
2-regular sequence 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...
sage: E * o == E.partial_sums(include_n=True)
True

Python

>>> from sage.all import *
>>> o = Seq2.one_hadamard()
>>> E * o
2-regular sequence 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...
>>> E * o == E.partial_sums(include_n=True)
True

Sage Live

o = Seq2.one_hadamard()
E * o
E * o == E.partial_sums(include_n=True)

forward_differences(**kwds)[source]¶

Return the sequence of forward differences of this $k$ -regular sequence.

INPUT:

minimize – (default: None) a boolean or None. If True, then minimized() is called after the operation, if False, then not. If this argument is None, then the default specified by the parent’s minimize_results is used.

OUTPUT: a RegularSequence

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: C = Seq2((Matrix([[2, 0], [2, 1]]), Matrix([[0, 1], [-2, 3]])),
....:          vector([1, 0]), vector([0, 1]))
sage: C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
sage: C.forward_differences()
2-regular sequence 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> C = Seq2((Matrix([[Integer(2), Integer(0)], [Integer(2), Integer(1)]]), Matrix([[Integer(0), Integer(1)], [-Integer(2), Integer(3)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(0), Integer(1)]))
>>> C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
>>> C.forward_differences()
2-regular sequence 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
C = Seq2((Matrix([[2, 0], [2, 1]]), Matrix([[0, 1], [-2, 3]])),
         vector([1, 0]), vector([0, 1]))
C
C.forward_differences()

Sage

sage: E = Seq2((Matrix([[0, 1], [0, 1]]), Matrix([[0, 0], [0, 1]])),
....:          vector([1, 0]), vector([1, 1]))
sage: E
2-regular sequence 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
sage: E.forward_differences()
2-regular sequence -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, ...

Python

>>> from sage.all import *
>>> E = Seq2((Matrix([[Integer(0), Integer(1)], [Integer(0), Integer(1)]]), Matrix([[Integer(0), Integer(0)], [Integer(0), Integer(1)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(1), Integer(1)]))
>>> E
2-regular sequence 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
>>> E.forward_differences()
2-regular sequence -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, ...

Sage Live

E = Seq2((Matrix([[0, 1], [0, 1]]), Matrix([[0, 0], [0, 1]])),
         vector([1, 0]), vector([1, 1]))
E
E.forward_differences()

is_degenerated()[source]¶

Return whether this $k$ -regular sequence is degenerated, i.e., whether this $k$ -regular sequence does not satisfy $μ [0] right = right$ .

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: Seq2((Matrix([2]), Matrix([3])), vector([1]), vector([1]))  # indirect doctest
Traceback (most recent call last):
...
DegeneratedSequenceError: degenerated sequence: mu[0]*right != right.
Using such a sequence might lead to wrong results.
You can use 'allow_degenerated_sequence=True' followed
by a call of method .regenerated() for correcting this.
sage: S = Seq2((Matrix([2]), Matrix([3])), vector([1]), vector([1]),
....:          allow_degenerated_sequence=True)
sage: S
2-regular sequence 1, 3, 6, 9, 12, 18, 18, 27, 24, 36, ...
sage: S.is_degenerated()
True

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> Seq2((Matrix([Integer(2)]), Matrix([Integer(3)])), vector([Integer(1)]), vector([Integer(1)]))  # indirect doctest
Traceback (most recent call last):
...
DegeneratedSequenceError: degenerated sequence: mu[0]*right != right.
Using such a sequence might lead to wrong results.
You can use 'allow_degenerated_sequence=True' followed
by a call of method .regenerated() for correcting this.
>>> S = Seq2((Matrix([Integer(2)]), Matrix([Integer(3)])), vector([Integer(1)]), vector([Integer(1)]),
...          allow_degenerated_sequence=True)
>>> S
2-regular sequence 1, 3, 6, 9, 12, 18, 18, 27, 24, 36, ...
>>> S.is_degenerated()
True

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
Seq2((Matrix([2]), Matrix([3])), vector([1]), vector([1]))  # indirect doctest
S = Seq2((Matrix([2]), Matrix([3])), vector([1]), vector([1]),
         allow_degenerated_sequence=True)
S
S.is_degenerated()

Sage

sage: C = Seq2((Matrix([[2, 0], [2, 1]]), Matrix([[0, 1], [-2, 3]])),
....:          vector([1, 0]), vector([0, 1]))
sage: C.is_degenerated()
False

Python

>>> from sage.all import *
>>> C = Seq2((Matrix([[Integer(2), Integer(0)], [Integer(2), Integer(1)]]), Matrix([[Integer(0), Integer(1)], [-Integer(2), Integer(3)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(0), Integer(1)]))
>>> C.is_degenerated()
False

Sage Live

C = Seq2((Matrix([[2, 0], [2, 1]]), Matrix([[0, 1], [-2, 3]])),
         vector([1, 0]), vector([0, 1]))
C.is_degenerated()

partial_sums(*args, **kwds)[source]¶

Return the sequence of partial sums of this $k$ -regular sequence. That is, the $n$ -th entry of the result is the sum of the first $n$ entries in the original sequence.

INPUT:

include_n – boolean (default: False); if set, then the $n$ -th entry of the result is the sum of the entries up to index $n$ (included)
minimize – (default: None) a boolean or None. If True, then minimized() is called after the operation, if False, then not. If this argument is None, then the default specified by the parent’s minimize_results is used.

OUTPUT: a RegularSequence

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)

sage: E = Seq2((Matrix([[0, 1], [0, 1]]), Matrix([[0, 0], [0, 1]])),
....:          vector([1, 0]), vector([1, 1]))
sage: E
2-regular sequence 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
sage: E.partial_sums()
2-regular sequence 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, ...
sage: E.partial_sums(include_n=True)
2-regular sequence 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)

>>> E = Seq2((Matrix([[Integer(0), Integer(1)], [Integer(0), Integer(1)]]), Matrix([[Integer(0), Integer(0)], [Integer(0), Integer(1)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(1), Integer(1)]))
>>> E
2-regular sequence 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
>>> E.partial_sums()
2-regular sequence 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, ...
>>> E.partial_sums(include_n=True)
2-regular sequence 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
E = Seq2((Matrix([[0, 1], [0, 1]]), Matrix([[0, 0], [0, 1]])),
         vector([1, 0]), vector([1, 1]))
E
E.partial_sums()
E.partial_sums(include_n=True)

Sage

sage: C = Seq2((Matrix([[2, 0], [2, 1]]), Matrix([[0, 1], [-2, 3]])),
....:          vector([1, 0]), vector([0, 1]))
sage: C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
sage: C.partial_sums()
2-regular sequence 0, 0, 1, 3, 6, 10, 15, 21, 28, 36, ...
sage: C.partial_sums(include_n=True)
2-regular sequence 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, ...

Python

>>> from sage.all import *
>>> C = Seq2((Matrix([[Integer(2), Integer(0)], [Integer(2), Integer(1)]]), Matrix([[Integer(0), Integer(1)], [-Integer(2), Integer(3)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(0), Integer(1)]))
>>> C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
>>> C.partial_sums()
2-regular sequence 0, 0, 1, 3, 6, 10, 15, 21, 28, 36, ...
>>> C.partial_sums(include_n=True)
2-regular sequence 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, ...

Sage Live

C = Seq2((Matrix([[2, 0], [2, 1]]), Matrix([[0, 1], [-2, 3]])),
         vector([1, 0]), vector([0, 1]))
C
C.partial_sums()
C.partial_sums(include_n=True)

The following linear representation of $S$ is chosen badly (is degenerated, see is_degenerated()), as $μ (0)$ applied on $right$ does not equal $right$ :

Sage

sage: S = Seq2((Matrix([2]), Matrix([3])), vector([1]), vector([1]),
....:          allow_degenerated_sequence=True)
sage: S
2-regular sequence 1, 3, 6, 9, 12, 18, 18, 27, 24, 36, ...

Python

>>> from sage.all import *
>>> S = Seq2((Matrix([Integer(2)]), Matrix([Integer(3)])), vector([Integer(1)]), vector([Integer(1)]),
...          allow_degenerated_sequence=True)
>>> S
2-regular sequence 1, 3, 6, 9, 12, 18, 18, 27, 24, 36, ...

Sage Live

S = Seq2((Matrix([2]), Matrix([3])), vector([1]), vector([1]),
         allow_degenerated_sequence=True)
S

Therefore, building partial sums produces a wrong result:

Sage

sage: H = S.partial_sums(include_n=True, minimize=False)
sage: H
2-regular sequence 1, 5, 16, 25, 62, 80, 98, 125, 274, 310, ...
sage: H = S.partial_sums(minimize=False)
sage: H
2-regular sequence 0, 2, 10, 16, 50, 62, 80, 98, 250, 274, ...

Python

>>> from sage.all import *
>>> H = S.partial_sums(include_n=True, minimize=False)
>>> H
2-regular sequence 1, 5, 16, 25, 62, 80, 98, 125, 274, 310, ...
>>> H = S.partial_sums(minimize=False)
>>> H
2-regular sequence 0, 2, 10, 16, 50, 62, 80, 98, 250, 274, ...

Sage Live

H = S.partial_sums(include_n=True, minimize=False)
H
H = S.partial_sums(minimize=False)
H

We can guess() the correct representation:

Sage

sage: from itertools import islice
sage: L = []; ps = 0
sage: for s in islice(S, 110):
....:     ps += s
....:     L.append(ps)
sage: G = Seq2.guess(lambda n: L[n])
sage: G
2-regular sequence 1, 4, 10, 19, 31, 49, 67, 94, 118, 154, ...
sage: G.linear_representation()
((1, 0, 0, 0),
 Finite family {0: [  0   1   0   0]
                   [  0   0   0   1]
                   [ -5   5   1   0]
                   [ 10 -17   0   8],
                1: [  0   0   1   0]
                   [ -5   3   3   0]
                   [ -5   0   6   0]
                   [-30  21  10   0]},
 (1, 1, 4, 1))
sage: G.minimized().dimension() == G.dimension()
True

Python

>>> from sage.all import *
>>> from itertools import islice
>>> L = []; ps = Integer(0)
>>> for s in islice(S, Integer(110)):
...     ps += s
...     L.append(ps)
>>> G = Seq2.guess(lambda n: L[n])
>>> G
2-regular sequence 1, 4, 10, 19, 31, 49, 67, 94, 118, 154, ...
>>> G.linear_representation()
((1, 0, 0, 0),
 Finite family {0: [  0   1   0   0]
                   [  0   0   0   1]
                   [ -5   5   1   0]
                   [ 10 -17   0   8],
                1: [  0   0   1   0]
                   [ -5   3   3   0]
                   [ -5   0   6   0]
                   [-30  21  10   0]},
 (1, 1, 4, 1))
>>> G.minimized().dimension() == G.dimension()
True

Sage Live

from itertools import islice
L = []; ps = 0
for s in islice(S, 110):
    ps += s
    L.append(ps)
G = Seq2.guess(lambda n: L[n])
G
G.linear_representation()
G.minimized().dimension() == G.dimension()

Or we regenerate the sequence $S$ first:

Sage

sage: S.regenerated().partial_sums(include_n=True, minimize=False)
2-regular sequence 1, 4, 10, 19, 31, 49, 67, 94, 118, 154, ...
sage: S.regenerated().partial_sums(minimize=False)
2-regular sequence 0, 1, 4, 10, 19, 31, 49, 67, 94, 118, ...

Python

>>> from sage.all import *
>>> S.regenerated().partial_sums(include_n=True, minimize=False)
2-regular sequence 1, 4, 10, 19, 31, 49, 67, 94, 118, 154, ...
>>> S.regenerated().partial_sums(minimize=False)
2-regular sequence 0, 1, 4, 10, 19, 31, 49, 67, 94, 118, ...

Sage Live

S.regenerated().partial_sums(include_n=True, minimize=False)
S.regenerated().partial_sums(minimize=False)

regenerated(*args, **kwds)[source]¶

Return a $k$ -regular sequence that satisfies $μ [0] right = right$ with the same values as this sequence.

INPUT:

minimize – (default: None) a boolean or None. If True, then minimized() is called after the operation, if False, then not. If this argument is None, then the default specified by the parent’s minimize_results is used.

OUTPUT: a RegularSequence

ALGORITHM:

Theorem B of [HKL2022] with $n_{0} = 1$ .

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)

The following linear representation of $S$ is chosen badly (is degenerated, see is_degenerated()), as $μ (0)$ applied on $right$ does not equal $right$ :

Sage

sage: S = Seq2((Matrix([2]), Matrix([3])), vector([1]), vector([1]),
....:          allow_degenerated_sequence=True)
sage: S
2-regular sequence 1, 3, 6, 9, 12, 18, 18, 27, 24, 36, ...
sage: S.is_degenerated()
True

Python

>>> from sage.all import *
>>> S = Seq2((Matrix([Integer(2)]), Matrix([Integer(3)])), vector([Integer(1)]), vector([Integer(1)]),
...          allow_degenerated_sequence=True)
>>> S
2-regular sequence 1, 3, 6, 9, 12, 18, 18, 27, 24, 36, ...
>>> S.is_degenerated()
True

Sage Live

S = Seq2((Matrix([2]), Matrix([3])), vector([1]), vector([1]),
         allow_degenerated_sequence=True)
S
S.is_degenerated()

However, we can regenerate the sequence $S$ :

Sage

sage: H = S.regenerated()
sage: H
2-regular sequence 1, 3, 6, 9, 12, 18, 18, 27, 24, 36, ...
sage: H.linear_representation()
((1, 0),
 Finite family {0: [ 0  1]
                   [-2  3],
                1: [3 0]
                   [6 0]},
 (1, 1))
sage: H.is_degenerated()
False

Python

>>> from sage.all import *
>>> H = S.regenerated()
>>> H
2-regular sequence 1, 3, 6, 9, 12, 18, 18, 27, 24, 36, ...
>>> H.linear_representation()
((1, 0),
 Finite family {0: [ 0  1]
                   [-2  3],
                1: [3 0]
                   [6 0]},
 (1, 1))
>>> H.is_degenerated()
False

Sage Live

H = S.regenerated()
H
H.linear_representation()
H.is_degenerated()

shift_left(b=1, **kwds)[source]¶

Return the sequence obtained by shifting this $k$ -regular sequence $b$ steps to the left.

INPUT:

b – integer
minimize – (default: None) a boolean or None. If True, then minimized() is called after the operation, if False, then not. If this argument is None, then the default specified by the parent’s minimize_results is used.

OUTPUT: a RegularSequence

Note

If $b$ is negative (i.e., actually a right-shift), then the coefficients when accessing negative indices are $0$ .

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: C = Seq2((Matrix([[2, 0], [0, 1]]), Matrix([[2, 1], [0, 1]])),
....:          vector([1, 0]), vector([0, 1])); C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

sage: C.shift_left()
2-regular sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
sage: C.shift_left(3)
2-regular sequence 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
sage: C.shift_left(-2)
2-regular sequence 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, ...

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> C = Seq2((Matrix([[Integer(2), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(2), Integer(1)], [Integer(0), Integer(1)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(0), Integer(1)])); C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

>>> C.shift_left()
2-regular sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
>>> C.shift_left(Integer(3))
2-regular sequence 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
>>> C.shift_left(-Integer(2))
2-regular sequence 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, ...

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
C = Seq2((Matrix([[2, 0], [0, 1]]), Matrix([[2, 1], [0, 1]])),
         vector([1, 0]), vector([0, 1])); C
C.shift_left()
C.shift_left(3)
C.shift_left(-2)

shift_right(b=1, **kwds)[source]¶

Return the sequence obtained by shifting this $k$ -regular sequence $b$ steps to the right.

INPUT:

b – integer
minimize – (default: None) a boolean or None. If True, then minimized() is called after the operation, if False, then not. If this argument is None, then the default specified by the parent’s minimize_results is used.

OUTPUT: a RegularSequence

Note

If $b$ is positive (i.e., indeed a right-shift), then the coefficients when accessing negative indices are $0$ .

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: C = Seq2((Matrix([[2, 0], [0, 1]]), Matrix([[2, 1], [0, 1]])),
....:          vector([1, 0]), vector([0, 1])); C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

sage: C.shift_right()
2-regular sequence 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, ...
sage: C.shift_right(3)
2-regular sequence 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, ...
sage: C.shift_right(-2)
2-regular sequence 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> C = Seq2((Matrix([[Integer(2), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(2), Integer(1)], [Integer(0), Integer(1)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(0), Integer(1)])); C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

>>> C.shift_right()
2-regular sequence 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, ...
>>> C.shift_right(Integer(3))
2-regular sequence 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, ...
>>> C.shift_right(-Integer(2))
2-regular sequence 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
C = Seq2((Matrix([[2, 0], [0, 1]]), Matrix([[2, 1], [0, 1]])),
         vector([1, 0]), vector([0, 1])); C
C.shift_right()
C.shift_right(3)
C.shift_right(-2)

subsequence(*args, **kwds)[source]¶

Return the subsequence with indices $a n + b$ of this $k$ -regular sequence.

INPUT:

a – nonnegative integer
b – integer

Alternatively, this is allowed to be a dictionary $b_{j} \mapsto c_{j}$ . If so and applied on $f (n)$ , the result will be the sum of all $c_{j} \cdot f (a n + b_{j})$ .
minimize – (default: None) a boolean or None. If True, then minimized() is called after the operation, if False, then not. If this argument is None, then the default specified by the parent’s minimize_results is used.

OUTPUT: a RegularSequence

Note

If $b$ is negative (i.e., right-shift), then the coefficients when accessing negative indices are $0$ .

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)

We consider the sequence $C$ with $C (n) = n$ and the following linear representation corresponding to the vector $(n, 1)$ :

Sage

sage: C = Seq2((Matrix([[2, 0], [0, 1]]), Matrix([[2, 1], [0, 1]])),
....:          vector([1, 0]), vector([0, 1])); C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

Python

>>> from sage.all import *
>>> C = Seq2((Matrix([[Integer(2), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(2), Integer(1)], [Integer(0), Integer(1)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(0), Integer(1)])); C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

Sage Live

C = Seq2((Matrix([[2, 0], [0, 1]]), Matrix([[2, 1], [0, 1]])),
         vector([1, 0]), vector([0, 1])); C

We now extract various subsequences of $C$ :

Sage

sage: C.subsequence(2, 0)
2-regular sequence 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, ...

sage: S31 = C.subsequence(3, 1); S31
2-regular sequence 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, ...
sage: S31.linear_representation()
((1, 0),
 Finite family {0: [ 0  1]
                   [-2  3],
                1: [ 6 -2]
                   [10 -3]},
 (1, 1))

sage: C.subsequence(3, 2)
2-regular sequence 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, ...

Python

>>> from sage.all import *
>>> C.subsequence(Integer(2), Integer(0))
2-regular sequence 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, ...

>>> S31 = C.subsequence(Integer(3), Integer(1)); S31
2-regular sequence 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, ...
>>> S31.linear_representation()
((1, 0),
 Finite family {0: [ 0  1]
                   [-2  3],
                1: [ 6 -2]
                   [10 -3]},
 (1, 1))

>>> C.subsequence(Integer(3), Integer(2))
2-regular sequence 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, ...

Sage Live

C.subsequence(2, 0)
S31 = C.subsequence(3, 1); S31
S31.linear_representation()
C.subsequence(3, 2)

Sage

sage: Srs = C.subsequence(1, -1); Srs
2-regular sequence 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, ...
sage: Srs.linear_representation()
((1, 0, 0),
 Finite family {0: [ 0  1  0]
                   [-2  3  0]
                   [-4  4  1],
                1: [ -2   2   0]
                   [  0   0   1]
                   [ 12 -12   5]},
 (0, 0, 1))

Python

>>> from sage.all import *
>>> Srs = C.subsequence(Integer(1), -Integer(1)); Srs
2-regular sequence 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, ...
>>> Srs.linear_representation()
((1, 0, 0),
 Finite family {0: [ 0  1  0]
                   [-2  3  0]
                   [-4  4  1],
                1: [ -2   2   0]
                   [  0   0   1]
                   [ 12 -12   5]},
 (0, 0, 1))

Sage Live

Srs = C.subsequence(1, -1); Srs
Srs.linear_representation()

We can build backward_differences() manually by passing a dictionary for the parameter b:

Sage

sage: Sbd = C.subsequence(1, {0: 1, -1: -1}); Sbd
2-regular sequence 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

Python

>>> from sage.all import *
>>> Sbd = C.subsequence(Integer(1), {Integer(0): Integer(1), -Integer(1): -Integer(1)}); Sbd
2-regular sequence 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

Sage Live

Sbd = C.subsequence(1, {0: 1, -1: -1}); Sbd

transposed(allow_degenerated_sequence=False)[source]¶

Return the transposed sequence.

INPUT:

allow_degenerated_sequence – boolean (default: False); if set, then there will be no check if the transposed sequence is a degenerated sequence (see is_degenerated()). Otherwise the transposed sequence is checked and a DegeneratedSequenceError is raised if such a sequence is detected.

OUTPUT: a RegularSequence

Each of the matrices in mu is transposed. Additionally the vectors left and right are switched.

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: U = Seq2((Matrix([[3, 2], [0, 1]]), Matrix([[2, 0], [1, 3]])),
....:          left=vector([0, 1]), right=vector([1, 0]),
....:          allow_degenerated_sequence=True)
sage: U.is_degenerated()
True
sage: Ut = U.transposed()
sage: Ut.linear_representation()
((1, 0),
 Finite family {0: [3 0]
                   [2 1],
                1: [2 1]
                   [0 3]},
 (0, 1))
sage: Ut.is_degenerated()
False

sage: Ut.transposed()
Traceback (most recent call last):
...
DegeneratedSequenceError: degenerated sequence: mu[0]*right != right.
Using such a sequence might lead to wrong results.
You can use 'allow_degenerated_sequence=True' followed
by a call of method .regenerated() for correcting this.
sage: Utt = Ut.transposed(allow_degenerated_sequence=True)
sage: Utt.is_degenerated()
True

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> U = Seq2((Matrix([[Integer(3), Integer(2)], [Integer(0), Integer(1)]]), Matrix([[Integer(2), Integer(0)], [Integer(1), Integer(3)]])),
...          left=vector([Integer(0), Integer(1)]), right=vector([Integer(1), Integer(0)]),
...          allow_degenerated_sequence=True)
>>> U.is_degenerated()
True
>>> Ut = U.transposed()
>>> Ut.linear_representation()
((1, 0),
 Finite family {0: [3 0]
                   [2 1],
                1: [2 1]
                   [0 3]},
 (0, 1))
>>> Ut.is_degenerated()
False

>>> Ut.transposed()
Traceback (most recent call last):
...
DegeneratedSequenceError: degenerated sequence: mu[0]*right != right.
Using such a sequence might lead to wrong results.
You can use 'allow_degenerated_sequence=True' followed
by a call of method .regenerated() for correcting this.
>>> Utt = Ut.transposed(allow_degenerated_sequence=True)
>>> Utt.is_degenerated()
True

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
U = Seq2((Matrix([[3, 2], [0, 1]]), Matrix([[2, 0], [1, 3]])),
         left=vector([0, 1]), right=vector([1, 0]),
         allow_degenerated_sequence=True)
U.is_degenerated()
Ut = U.transposed()
Ut.linear_representation()
Ut.is_degenerated()
Ut.transposed()
Utt = Ut.transposed(allow_degenerated_sequence=True)
Utt.is_degenerated()

See also

RecognizableSeries.transposed

class sage.combinat.regular_sequence.RegularSequenceRing(k, *args, **kwds)[source]¶

Bases: RecognizableSeriesSpace

The space of $k$ -regular Sequences over the given coefficient_ring.

INPUT:

k – integer at least $2$ specifying the base
coefficient_ring – a (semi-)ring
category – (default: None) the category of this space

EXAMPLES:

Sage

sage: RegularSequenceRing(2, ZZ)
Space of 2-regular sequences over Integer Ring
sage: RegularSequenceRing(3, ZZ)
Space of 3-regular sequences over Integer Ring

Python

>>> from sage.all import *
>>> RegularSequenceRing(Integer(2), ZZ)
Space of 2-regular sequences over Integer Ring
>>> RegularSequenceRing(Integer(3), ZZ)
Space of 3-regular sequences over Integer Ring

Sage Live

RegularSequenceRing(2, ZZ)
RegularSequenceRing(3, ZZ)

See also

k-regular sequence, RegularSequence.

Element[source]¶: alias of RegularSequence

from_recurrence(*args, **kwds)[source]¶

Construct the unique $k$ -regular sequence which fulfills the given recurrence relations and initial values. The recurrence relations have to have the specific shape of $k$ -recursive sequences as described in [HKL2022], and are either given as symbolic equations, e.g.,

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: var('n')
n
sage: function('f')
f
sage: Seq2.from_recurrence([
....:     f(2*n) == 2*f(n), f(2*n + 1) == 3*f(n) + 4*f(n - 1),
....:     f(0) == 0, f(1) == 1], f, n)
2-regular sequence 0, 0, 0, 1, 2, 3, 4, 10, 6, 17, ...

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> var('n')
n
>>> function('f')
f
>>> Seq2.from_recurrence([
...     f(Integer(2)*n) == Integer(2)*f(n), f(Integer(2)*n + Integer(1)) == Integer(3)*f(n) + Integer(4)*f(n - Integer(1)),
...     f(Integer(0)) == Integer(0), f(Integer(1)) == Integer(1)], f, n)
2-regular sequence 0, 0, 0, 1, 2, 3, 4, 10, 6, 17, ...

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
var('n')
function('f')
Seq2.from_recurrence([
    f(2*n) == 2*f(n), f(2*n + 1) == 3*f(n) + 4*f(n - 1),
    f(0) == 0, f(1) == 1], f, n)

or via the parameters of the $k$ -recursive sequence as described in the input block below:

Sage

sage: Seq2.from_recurrence(M=1, m=0,
....:     coeffs={(0, 0): 2, (1, 0): 3, (1, -1): 4},
....:     initial_values={0: 0, 1: 1})
2-regular sequence 0, 0, 0, 1, 2, 3, 4, 10, 6, 17, ...

Python

>>> from sage.all import *
>>> Seq2.from_recurrence(M=Integer(1), m=Integer(0),
...     coeffs={(Integer(0), Integer(0)): Integer(2), (Integer(1), Integer(0)): Integer(3), (Integer(1), -Integer(1)): Integer(4)},
...     initial_values={Integer(0): Integer(0), Integer(1): Integer(1)})
2-regular sequence 0, 0, 0, 1, 2, 3, 4, 10, 6, 17, ...

Sage Live

Seq2.from_recurrence(M=1, m=0,
    coeffs={(0, 0): 2, (1, 0): 3, (1, -1): 4},
    initial_values={0: 0, 1: 1})

INPUT:

Positional arguments:

If the recurrence relations are represented by symbolic equations, then the following arguments are required:

equations – list of equations where the elements have either the form
- $f (k^{M} n + r) = c_{r, l} f (k^{m} n + l) + c_{r, l + 1} f (k^{m} n + l + 1) + . . . + c_{r, u} f (k^{m} n + u)$ for some integers $0 \leq r < k^{M}$ , $M > m \geq 0$ and $l \leq u$ , and some coefficients $c_{r, j}$ from the (semi)ring coefficients of the corresponding RegularSequenceRing, valid for all integers $n \geq offset$ for some integer $offset \geq max (- l / k^{m}, 0)$ (default: 0), and there is an equation of this form (with the same parameters $M$ and $m$ ) for all $r$
or the form
- f(k) == t for some integer k and some t from the (semi)ring coefficient_ring.
The recurrence relations above uniquely determine a $k$ -regular sequence; see [HKL2022] for further information.
function – symbolic function f occurring in the equations
var – symbolic variable (n in the above description of equations)

The following second representation of the recurrence relations is particularly useful for cases where coefficient_ring is not compatible with sage.symbolic.ring.SymbolicRing. Then the following arguments are required:

M – parameter of the recursive sequences, see [HKL2022], Definition 3.1, as well as in the description of equations above
m – parameter of the recursive sequences, see [HKL2022], Definition 3.1, as well as in the description of equations above
coeffs – dictionary where coeffs[(r, j)] is the coefficient $c_{r, j}$ as given in the description of equations above. If coeffs[(r, j)] is not given for some r and j, then it is assumed to be zero.
initial_values – dictionary mapping integers n to the n-th value of the sequence

Optional keyword-only argument:

offset – integer (default: $0$ ); see explanation of equations above
inhomogeneities – (default: {}) a dictionary mapping integers r to the inhomogeneity $g_{r}$ as given in [HKL2022], Corollary D. All inhomogeneities have to be regular sequences from self or elements of coefficient_ring.

OUTPUT: a RegularSequence

EXAMPLES:

Stern–Brocot Sequence:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: var('n')
n
sage: function('f')
f
sage: SB = Seq2.from_recurrence([
....:     f(2*n) == f(n), f(2*n + 1) == f(n) + f(n + 1),
....:     f(0) == 0, f(1) == 1], f, n)
sage: SB
2-regular sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, ...

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> var('n')
n
>>> function('f')
f
>>> SB = Seq2.from_recurrence([
...     f(Integer(2)*n) == f(n), f(Integer(2)*n + Integer(1)) == f(n) + f(n + Integer(1)),
...     f(Integer(0)) == Integer(0), f(Integer(1)) == Integer(1)], f, n)
>>> SB
2-regular sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, ...

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
var('n')
function('f')
SB = Seq2.from_recurrence([
    f(2*n) == f(n), f(2*n + 1) == f(n) + f(n + 1),
    f(0) == 0, f(1) == 1], f, n)
SB

Number of Odd Entries in Pascal’s Triangle:

Sage

sage: Seq2.from_recurrence([
....:     f(2*n) == 3*f(n), f(2*n + 1) == 2*f(n) + f(n + 1),
....:     f(0) == 0, f(1) == 1], f, n)
2-regular sequence 0, 1, 3, 5, 9, 11, 15, 19, 27, 29, ...

Python

>>> from sage.all import *
>>> Seq2.from_recurrence([
...     f(Integer(2)*n) == Integer(3)*f(n), f(Integer(2)*n + Integer(1)) == Integer(2)*f(n) + f(n + Integer(1)),
...     f(Integer(0)) == Integer(0), f(Integer(1)) == Integer(1)], f, n)
2-regular sequence 0, 1, 3, 5, 9, 11, 15, 19, 27, 29, ...

Sage Live

Seq2.from_recurrence([
    f(2*n) == 3*f(n), f(2*n + 1) == 2*f(n) + f(n + 1),
    f(0) == 0, f(1) == 1], f, n)

Number of Unbordered Factors in the Thue–Morse Sequence:

Sage

sage: UB = Seq2.from_recurrence([
....:     f(8*n) == 2*f(4*n),
....:     f(8*n + 1) == f(4*n + 1),
....:     f(8*n + 2) == f(4*n + 1) + f(4*n + 3),
....:     f(8*n + 3) == -f(4*n + 1) + f(4*n + 2),
....:     f(8*n + 4) == 2*f(4*n + 2),
....:     f(8*n + 5) == f(4*n + 3),
....:     f(8*n + 6) == -f(4*n + 1) + f(4*n + 2) + f(4*n + 3),
....:     f(8*n + 7) == 2*f(4*n + 1) + f(4*n + 3),
....:     f(0) == 1, f(1) == 2, f(2) == 2, f(3) == 4, f(4) == 2,
....:     f(5) == 4, f(6) == 6, f(7) == 0, f(8) == 4, f(9) == 4,
....:     f(10) == 4, f(11) == 4, f(12) == 12, f(13) == 0, f(14) == 4,
....:     f(15) == 4, f(16) == 8, f(17) == 4, f(18) == 8, f(19) == 0,
....:     f(20) == 8, f(21) == 4, f(22) == 4, f(23) == 8], f, n, offset=3)
sage: UB
2-regular sequence 1, 2, 2, 4, 2, 4, 6, 0, 4, 4, ...

Python

>>> from sage.all import *
>>> UB = Seq2.from_recurrence([
...     f(Integer(8)*n) == Integer(2)*f(Integer(4)*n),
...     f(Integer(8)*n + Integer(1)) == f(Integer(4)*n + Integer(1)),
...     f(Integer(8)*n + Integer(2)) == f(Integer(4)*n + Integer(1)) + f(Integer(4)*n + Integer(3)),
...     f(Integer(8)*n + Integer(3)) == -f(Integer(4)*n + Integer(1)) + f(Integer(4)*n + Integer(2)),
...     f(Integer(8)*n + Integer(4)) == Integer(2)*f(Integer(4)*n + Integer(2)),
...     f(Integer(8)*n + Integer(5)) == f(Integer(4)*n + Integer(3)),
...     f(Integer(8)*n + Integer(6)) == -f(Integer(4)*n + Integer(1)) + f(Integer(4)*n + Integer(2)) + f(Integer(4)*n + Integer(3)),
...     f(Integer(8)*n + Integer(7)) == Integer(2)*f(Integer(4)*n + Integer(1)) + f(Integer(4)*n + Integer(3)),
...     f(Integer(0)) == Integer(1), f(Integer(1)) == Integer(2), f(Integer(2)) == Integer(2), f(Integer(3)) == Integer(4), f(Integer(4)) == Integer(2),
...     f(Integer(5)) == Integer(4), f(Integer(6)) == Integer(6), f(Integer(7)) == Integer(0), f(Integer(8)) == Integer(4), f(Integer(9)) == Integer(4),
...     f(Integer(10)) == Integer(4), f(Integer(11)) == Integer(4), f(Integer(12)) == Integer(12), f(Integer(13)) == Integer(0), f(Integer(14)) == Integer(4),
...     f(Integer(15)) == Integer(4), f(Integer(16)) == Integer(8), f(Integer(17)) == Integer(4), f(Integer(18)) == Integer(8), f(Integer(19)) == Integer(0),
...     f(Integer(20)) == Integer(8), f(Integer(21)) == Integer(4), f(Integer(22)) == Integer(4), f(Integer(23)) == Integer(8)], f, n, offset=Integer(3))
>>> UB
2-regular sequence 1, 2, 2, 4, 2, 4, 6, 0, 4, 4, ...

Sage Live

UB = Seq2.from_recurrence([
    f(8*n) == 2*f(4*n),
    f(8*n + 1) == f(4*n + 1),
    f(8*n + 2) == f(4*n + 1) + f(4*n + 3),
    f(8*n + 3) == -f(4*n + 1) + f(4*n + 2),
    f(8*n + 4) == 2*f(4*n + 2),
    f(8*n + 5) == f(4*n + 3),
    f(8*n + 6) == -f(4*n + 1) + f(4*n + 2) + f(4*n + 3),
    f(8*n + 7) == 2*f(4*n + 1) + f(4*n + 3),
    f(0) == 1, f(1) == 2, f(2) == 2, f(3) == 4, f(4) == 2,
    f(5) == 4, f(6) == 6, f(7) == 0, f(8) == 4, f(9) == 4,
    f(10) == 4, f(11) == 4, f(12) == 12, f(13) == 0, f(14) == 4,
    f(15) == 4, f(16) == 8, f(17) == 4, f(18) == 8, f(19) == 0,
    f(20) == 8, f(21) == 4, f(22) == 4, f(23) == 8], f, n, offset=3)
UB

Binary sum of digits $S (n)$ , characterized by the recurrence relations $S (4 n) = S (2 n)$ , $S (4 n + 1) = S (2 n + 1)$ , $S (4 n + 2) = S (2 n + 1)$ and $S (4 n + 3) = - S (2 n) + 2 S (2 n + 1)$ :

Sage

sage: S = Seq2.from_recurrence([
....:     f(4*n) == f(2*n),
....:     f(4*n + 1) == f(2*n + 1),
....:     f(4*n + 2) == f(2*n + 1),
....:     f(4*n + 3) == -f(2*n) + 2*f(2*n + 1),
....:     f(0) == 0, f(1) == 1], f, n)
sage: S
2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...

Python

>>> from sage.all import *
>>> S = Seq2.from_recurrence([
...     f(Integer(4)*n) == f(Integer(2)*n),
...     f(Integer(4)*n + Integer(1)) == f(Integer(2)*n + Integer(1)),
...     f(Integer(4)*n + Integer(2)) == f(Integer(2)*n + Integer(1)),
...     f(Integer(4)*n + Integer(3)) == -f(Integer(2)*n) + Integer(2)*f(Integer(2)*n + Integer(1)),
...     f(Integer(0)) == Integer(0), f(Integer(1)) == Integer(1)], f, n)
>>> S
2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...

Sage Live

S = Seq2.from_recurrence([
    f(4*n) == f(2*n),
    f(4*n + 1) == f(2*n + 1),
    f(4*n + 2) == f(2*n + 1),
    f(4*n + 3) == -f(2*n) + 2*f(2*n + 1),
    f(0) == 0, f(1) == 1], f, n)
S

In order to check if this sequence is indeed the binary sum of digits, we construct it directly via its linear representation and compare it with S:

Sage

sage: S2 = Seq2(
....:     (Matrix([[1, 0], [0, 1]]), Matrix([[1, 0], [1, 1]])),
....:     left=vector([0, 1]), right=vector([1, 0]))
sage: (S - S2).is_trivial_zero()
True

Python

>>> from sage.all import *
>>> S2 = Seq2(
...     (Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(1), Integer(0)], [Integer(1), Integer(1)]])),
...     left=vector([Integer(0), Integer(1)]), right=vector([Integer(1), Integer(0)]))
>>> (S - S2).is_trivial_zero()
True

Sage Live

S2 = Seq2(
    (Matrix([[1, 0], [0, 1]]), Matrix([[1, 0], [1, 1]])),
    left=vector([0, 1]), right=vector([1, 0]))
(S - S2).is_trivial_zero()

Alternatively, we can also use the simpler but inhomogeneous recurrence relations $S (2 n) = S (n)$ and $S (2 n + 1) = S (n) + 1$ via direct parameters:

Sage

sage: S3 = Seq2.from_recurrence(M=1, m=0,
....:     coeffs={(0, 0): 1, (1, 0): 1},
....:     initial_values={0: 0, 1: 1},
....:     inhomogeneities={1: 1})
sage: S3
2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...
sage: (S3 - S2).is_trivial_zero()
True

Python

>>> from sage.all import *
>>> S3 = Seq2.from_recurrence(M=Integer(1), m=Integer(0),
...     coeffs={(Integer(0), Integer(0)): Integer(1), (Integer(1), Integer(0)): Integer(1)},
...     initial_values={Integer(0): Integer(0), Integer(1): Integer(1)},
...     inhomogeneities={Integer(1): Integer(1)})
>>> S3
2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...
>>> (S3 - S2).is_trivial_zero()
True

Sage Live

S3 = Seq2.from_recurrence(M=1, m=0,
    coeffs={(0, 0): 1, (1, 0): 1},
    initial_values={0: 0, 1: 1},
    inhomogeneities={1: 1})
S3
(S3 - S2).is_trivial_zero()

Number of Non-Zero Elements in the Generalized Pascal’s Triangle (see [LRS2017]):

Sage

sage: Seq2 = RegularSequenceRing(2, QQ)
sage: P = Seq2.from_recurrence([
....:     f(4*n) == 5/3*f(2*n) - 1/3*f(2*n + 1),
....:     f(4*n + 1) == 4/3*f(2*n) + 1/3*f(2*n + 1),
....:     f(4*n + 2) == 1/3*f(2*n) + 4/3*f(2*n + 1),
....:     f(4*n + 3) == -1/3*f(2*n) + 5/3*f(2*n + 1),
....:     f(0) == 1, f(1) == 2], f, n)
sage: P
2-regular sequence 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, ...

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), QQ)
>>> P = Seq2.from_recurrence([
...     f(Integer(4)*n) == Integer(5)/Integer(3)*f(Integer(2)*n) - Integer(1)/Integer(3)*f(Integer(2)*n + Integer(1)),
...     f(Integer(4)*n + Integer(1)) == Integer(4)/Integer(3)*f(Integer(2)*n) + Integer(1)/Integer(3)*f(Integer(2)*n + Integer(1)),
...     f(Integer(4)*n + Integer(2)) == Integer(1)/Integer(3)*f(Integer(2)*n) + Integer(4)/Integer(3)*f(Integer(2)*n + Integer(1)),
...     f(Integer(4)*n + Integer(3)) == -Integer(1)/Integer(3)*f(Integer(2)*n) + Integer(5)/Integer(3)*f(Integer(2)*n + Integer(1)),
...     f(Integer(0)) == Integer(1), f(Integer(1)) == Integer(2)], f, n)
>>> P
2-regular sequence 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, ...

Sage Live

Seq2 = RegularSequenceRing(2, QQ)
P = Seq2.from_recurrence([
    f(4*n) == 5/3*f(2*n) - 1/3*f(2*n + 1),
    f(4*n + 1) == 4/3*f(2*n) + 1/3*f(2*n + 1),
    f(4*n + 2) == 1/3*f(2*n) + 4/3*f(2*n + 1),
    f(4*n + 3) == -1/3*f(2*n) + 5/3*f(2*n + 1),
    f(0) == 1, f(1) == 2], f, n)
P

Finally, the same sequence can also be obtained via direct parameters without symbolic equations:

Sage

sage: Seq2.from_recurrence(M=2, m=1,
....:     coeffs={(0, 0): 5/3, (0, 1): -1/3,
....:             (1, 0): 4/3, (1, 1): 1/3,
....:             (2, 0): 1/3, (2, 1): 4/3,
....:             (3, 0): -1/3, (3, 1): 5/3},
....:     initial_values={0: 1, 1: 2})
2-regular sequence 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, ...

Python

>>> from sage.all import *
>>> Seq2.from_recurrence(M=Integer(2), m=Integer(1),
...     coeffs={(Integer(0), Integer(0)): Integer(5)/Integer(3), (Integer(0), Integer(1)): -Integer(1)/Integer(3),
...             (Integer(1), Integer(0)): Integer(4)/Integer(3), (Integer(1), Integer(1)): Integer(1)/Integer(3),
...             (Integer(2), Integer(0)): Integer(1)/Integer(3), (Integer(2), Integer(1)): Integer(4)/Integer(3),
...             (Integer(3), Integer(0)): -Integer(1)/Integer(3), (Integer(3), Integer(1)): Integer(5)/Integer(3)},
...     initial_values={Integer(0): Integer(1), Integer(1): Integer(2)})
2-regular sequence 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, ...

Sage Live

Seq2.from_recurrence(M=2, m=1,
    coeffs={(0, 0): 5/3, (0, 1): -1/3,
            (1, 0): 4/3, (1, 1): 1/3,
            (2, 0): 1/3, (2, 1): 4/3,
            (3, 0): -1/3, (3, 1): 5/3},
    initial_values={0: 1, 1: 2})

guess(f, n_verify=100, max_exponent=10, sequence=None)[source]¶

Guess a $k$ -regular sequence whose first terms coincide with $(f (n))_{n \geq 0}$ .

INPUT:

f – a function (callable) which determines the sequence. It takes nonnegative integers as an input
n_verify – (default: 100) a positive integer. The resulting $k$ -regular sequence coincides with $f$ on the first n_verify terms.
max_exponent – (default: 10) a positive integer specifying the maximum exponent of $k$ which is tried when guessing the sequence, i.e., relations between $f (k^{t} n + r)$ are used for $0 \leq t \leq \max_exponent$ and $0 \leq r < k^{j}$
sequence – (default: None) a $k$ -regular sequence used for bootstrapping the guessing by adding information of the linear representation of sequence to the guessed representation

OUTPUT: a RegularSequence

ALGORITHM:

For the purposes of this description, the right vector valued sequence associated with a regular sequence consists of the corresponding matrix product multiplied by the right vector, but without the left vector of the regular sequence.

The algorithm maintains a right vector valued sequence consisting of the right vector valued sequence of the argument sequence (replaced by an empty tuple if sequence is None) plus several components of the shape $m \mapsto f (k^{t} \cdot m + r)$ for suitable t and r.

Implicitly, the algorithm also maintains a $d \times n_{verify}$ matrix A (where d is the dimension of the right vector valued sequence) whose columns are the current right vector valued sequence evaluated at the nonnegative integers less than $n_{verify}$ and ensures that this matrix has full row rank.

EXAMPLES:

Binary sum of digits:

Sage

sage: @cached_function
....: def s(n):
....:     if n == 0:
....:         return 0
....:     return s(n//2) + ZZ(is_odd(n))
sage: all(s(n) == sum(n.digits(2)) for n in srange(10))
True
sage: [s(n) for n in srange(10)]
[0, 1, 1, 2, 1, 2, 2, 3, 1, 2]

Python

>>> from sage.all import *
>>> @cached_function
... def s(n):
...     if n == Integer(0):
...         return Integer(0)
...     return s(n//Integer(2)) + ZZ(is_odd(n))
>>> all(s(n) == sum(n.digits(Integer(2))) for n in srange(Integer(10)))
True
>>> [s(n) for n in srange(Integer(10))]
[0, 1, 1, 2, 1, 2, 2, 3, 1, 2]

Sage Live

@cached_function
def s(n):
    if n == 0:
        return 0
    return s(n//2) + ZZ(is_odd(n))
all(s(n) == sum(n.digits(2)) for n in srange(10))
[s(n) for n in srange(10)]

Let us guess a $2$ -linear representation for $s (n)$ :

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: import logging
sage: logging.getLogger().setLevel(logging.INFO)
sage: S1 = Seq2.guess(s); S1
INFO:...:including f_{1*m+0}
INFO:...:including f_{2*m+1}
2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...
sage: S1.linear_representation()
((1, 0),
 Finite family {0: [1 0]
                   [0 1],
                1: [ 0  1]
                   [-1  2]},
 (0, 1))

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> import logging
>>> logging.getLogger().setLevel(logging.INFO)
>>> S1 = Seq2.guess(s); S1
INFO:...:including f_{1*m+0}
INFO:...:including f_{2*m+1}
2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...
>>> S1.linear_representation()
((1, 0),
 Finite family {0: [1 0]
                   [0 1],
                1: [ 0  1]
                   [-1  2]},
 (0, 1))

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
import logging
logging.getLogger().setLevel(logging.INFO)
S1 = Seq2.guess(s); S1
S1.linear_representation()

The INFO messages mean that the right vector valued sequence is the sequence $(s (n), s (2 n + 1))^{⊤}$ .

We guess again, but this time, we use a constant sequence for bootstrapping the guessing process:

Sage

sage: C = Seq2.one_hadamard(); C
2-regular sequence 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
sage: S2 = Seq2.guess(s, sequence=C); S2
INFO:...:including 2-regular sequence 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
INFO:...:including f_{1*m+0}
2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...
sage: S2.linear_representation()
((0, 1),
 Finite family {0: [1 0]
                   [0 1],
                1: [1 0]
                   [1 1]},
 (1, 0))
sage: S1 == S2
True

Python

>>> from sage.all import *
>>> C = Seq2.one_hadamard(); C
2-regular sequence 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
>>> S2 = Seq2.guess(s, sequence=C); S2
INFO:...:including 2-regular sequence 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
INFO:...:including f_{1*m+0}
2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...
>>> S2.linear_representation()
((0, 1),
 Finite family {0: [1 0]
                   [0 1],
                1: [1 0]
                   [1 1]},
 (1, 0))
>>> S1 == S2
True

Sage Live

C = Seq2.one_hadamard(); C
S2 = Seq2.guess(s, sequence=C); S2
S2.linear_representation()
S1 == S2

The sequence of all natural numbers:

Sage

sage: S = Seq2.guess(lambda n: n); S
INFO:...:including f_{1*m+0}
INFO:...:including f_{2*m+1}
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
sage: S.linear_representation()
((1, 0),
 Finite family {0: [2 0]
                   [2 1],
                1: [ 0  1]
                   [-2  3]},
 (0, 1))

Python

>>> from sage.all import *
>>> S = Seq2.guess(lambda n: n); S
INFO:...:including f_{1*m+0}
INFO:...:including f_{2*m+1}
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
>>> S.linear_representation()
((1, 0),
 Finite family {0: [2 0]
                   [2 1],
                1: [ 0  1]
                   [-2  3]},
 (0, 1))

Sage Live

S = Seq2.guess(lambda n: n); S
S.linear_representation()

The indicator function of the even integers:

Sage

sage: S = Seq2.guess(lambda n: ZZ(is_even(n))); S
INFO:...:including f_{1*m+0}
INFO:...:including f_{2*m+0}
2-regular sequence 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
sage: S.linear_representation()
((1, 0),
 Finite family {0: [0 1]
                   [0 1],
                1: [0 0]
                   [0 1]},
 (1, 1))

Python

>>> from sage.all import *
>>> S = Seq2.guess(lambda n: ZZ(is_even(n))); S
INFO:...:including f_{1*m+0}
INFO:...:including f_{2*m+0}
2-regular sequence 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
>>> S.linear_representation()
((1, 0),
 Finite family {0: [0 1]
                   [0 1],
                1: [0 0]
                   [0 1]},
 (1, 1))

Sage Live

S = Seq2.guess(lambda n: ZZ(is_even(n))); S
S.linear_representation()

The indicator function of the odd integers:

Sage

sage: S = Seq2.guess(lambda n: ZZ(is_odd(n))); S
INFO:...:including f_{1*m+0}
INFO:...:including f_{2*m+1}
2-regular sequence 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...
sage: S.linear_representation()
((1, 0),
 Finite family {0: [0 0]
                   [0 1],
                1: [0 1]
                   [0 1]},
 (0, 1))
sage: logging.getLogger().setLevel(logging.WARN)

Python

>>> from sage.all import *
>>> S = Seq2.guess(lambda n: ZZ(is_odd(n))); S
INFO:...:including f_{1*m+0}
INFO:...:including f_{2*m+1}
2-regular sequence 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...
>>> S.linear_representation()
((1, 0),
 Finite family {0: [0 0]
                   [0 1],
                1: [0 1]
                   [0 1]},
 (0, 1))
>>> logging.getLogger().setLevel(logging.WARN)

Sage Live

S = Seq2.guess(lambda n: ZZ(is_odd(n))); S
S.linear_representation()
logging.getLogger().setLevel(logging.WARN)

The following linear representation of $S$ is chosen badly (is degenerated, see is_degenerated()), as $μ (0)$ applied on $right$ does not equal $right$ :

Sage

sage: S = Seq2((Matrix([2]), Matrix([3])), vector([1]), vector([1]),
....:          allow_degenerated_sequence=True)
sage: S
2-regular sequence 1, 3, 6, 9, 12, 18, 18, 27, 24, 36, ...
sage: S.is_degenerated()
True

Python

>>> from sage.all import *
>>> S = Seq2((Matrix([Integer(2)]), Matrix([Integer(3)])), vector([Integer(1)]), vector([Integer(1)]),
...          allow_degenerated_sequence=True)
>>> S
2-regular sequence 1, 3, 6, 9, 12, 18, 18, 27, 24, 36, ...
>>> S.is_degenerated()
True

Sage Live

S = Seq2((Matrix([2]), Matrix([3])), vector([1]), vector([1]),
         allow_degenerated_sequence=True)
S
S.is_degenerated()

However, we can guess() a $2$ -regular sequence of dimension $2$ :

Sage

sage: G = Seq2.guess(lambda n: S[n])
sage: G
2-regular sequence 1, 3, 6, 9, 12, 18, 18, 27, 24, 36, ...
sage: G.linear_representation()
((1, 0),
 Finite family {0: [ 0  1]
                   [-2  3],
                1: [3 0]
                   [6 0]},
 (1, 1))

sage: G == S.regenerated()
True

Python

>>> from sage.all import *
>>> G = Seq2.guess(lambda n: S[n])
>>> G
2-regular sequence 1, 3, 6, 9, 12, 18, 18, 27, 24, 36, ...
>>> G.linear_representation()
((1, 0),
 Finite family {0: [ 0  1]
                   [-2  3],
                1: [3 0]
                   [6 0]},
 (1, 1))

>>> G == S.regenerated()
True

Sage Live

G = Seq2.guess(lambda n: S[n])
G
G.linear_representation()
G == S.regenerated()

one()[source]¶

Return the one element of this RegularSequenceRing, i.e. the unique neutral element for $*$ and also the embedding of the one of the coefficient ring into this RegularSequenceRing.

EXAMPLES:

Sage

sage: Seq2 = RegularSequenceRing(2, ZZ)
sage: O = Seq2.one(); O
2-regular sequence 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
sage: O.linear_representation()
((1), Finite family {0: [1], 1: [0]}, (1))

Python

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)
>>> O = Seq2.one(); O
2-regular sequence 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
>>> O.linear_representation()
((1), Finite family {0: [1], 1: [0]}, (1))

Sage Live

Seq2 = RegularSequenceRing(2, ZZ)
O = Seq2.one(); O
O.linear_representation()

some_elements()[source]¶

Return some elements of this $k$ -regular sequence.

See TestSuite for a typical use case.

OUTPUT: an iterator

EXAMPLES:

Sage

sage: tuple(RegularSequenceRing(2, ZZ).some_elements())
(2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...,
 2-regular sequence 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, ...,
 2-regular sequence 1, 1, 0, 1, -1, 0, 0, 1, -2, -1, ...,
 2-regular sequence 2, -1, 0, 0, 0, -1, 0, 0, 0, 0, ...,
 2-regular sequence 1, 1, 0, 1, 5, 0, 0, 1, -33, 5, ...,
 2-regular sequence -5, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...,
 2-regular sequence -59, -20, 0, -20, 0, 0, 0, -20, 0, 0, ...,
 ...
 2-regular sequence 2210, 170, 0, 0, 0, 0, 0, 0, 0, 0, ...)

Python

>>> from sage.all import *
>>> tuple(RegularSequenceRing(Integer(2), ZZ).some_elements())
(2-regular sequence 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...,
 2-regular sequence 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, ...,
 2-regular sequence 1, 1, 0, 1, -1, 0, 0, 1, -2, -1, ...,
 2-regular sequence 2, -1, 0, 0, 0, -1, 0, 0, 0, 0, ...,
 2-regular sequence 1, 1, 0, 1, 5, 0, 0, 1, -33, 5, ...,
 2-regular sequence -5, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...,
 2-regular sequence -59, -20, 0, -20, 0, 0, 0, -20, 0, 0, ...,
 ...
 2-regular sequence 2210, 170, 0, 0, 0, 0, 0, 0, 0, 0, ...)

Sage Live

tuple(RegularSequenceRing(2, ZZ).some_elements())

sage.combinat.regular_sequence.pad_right(T, length, zero=0)[source]¶

Pad T to the right by using zero to have at least the given length.

INPUT:

T – tuple, list or other iterable
length – nonnegative integer
zero – (default: 0) the elements to pad with

OUTPUT: an object of the same type as T

EXAMPLES:

Sage

sage: from sage.combinat.regular_sequence import pad_right
sage: pad_right((1, 2, 3), 10)
(1, 2, 3, 0, 0, 0, 0, 0, 0, 0)
sage: pad_right((1, 2, 3), 2)
(1, 2, 3)
sage: pad_right([(1, 2), (3, 4)], 4, (0, 0))
[(1, 2), (3, 4), (0, 0), (0, 0)]

Python

>>> from sage.all import *
>>> from sage.combinat.regular_sequence import pad_right
>>> pad_right((Integer(1), Integer(2), Integer(3)), Integer(10))
(1, 2, 3, 0, 0, 0, 0, 0, 0, 0)
>>> pad_right((Integer(1), Integer(2), Integer(3)), Integer(2))
(1, 2, 3)
>>> pad_right([(Integer(1), Integer(2)), (Integer(3), Integer(4))], Integer(4), (Integer(0), Integer(0)))
[(1, 2), (3, 4), (0, 0), (0, 0)]

Sage Live

from sage.combinat.regular_sequence import pad_right
pad_right((1, 2, 3), 10)
pad_right((1, 2, 3), 2)
pad_right([(1, 2), (3, 4)], 4, (0, 0))

sage.combinat.regular_sequence.value(D, k)[source]¶

Return the value of the expansion with digits $D$ in base $k$ , i.e.

\sum_{0 \leq j < len D} D [j] k^{j} .

INPUT:

D – tuple or other iterable
k – the base

OUTPUT:

An element in the common parent of the base $k$ and of the entries of $D$

EXAMPLES:

Sage

sage: from sage.combinat.regular_sequence import value
sage: value(42.digits(7), 7)
42

Python

>>> from sage.all import *
>>> from sage.combinat.regular_sequence import value
>>> value(Integer(42).digits(Integer(7)), Integer(7))
42

Sage Live

from sage.combinat.regular_sequence import value
value(42.digits(7), 7)

k-regular sequences¶

Examples¶

Binary sum of digits¶

Number of odd entries in Pascal’s triangle¶

Various¶

Classes and Methods¶

$k$ -regular sequences¶