\(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].

Warning

As this code is experimental, warnings are thrown when a \(k\)-regular sequence space is created for the first time in a session (see sage.misc.superseded.experimental).

Examples

Binary sum of digits

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

sage: Seq2 = kRegularSequenceSpace(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

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: @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)

There is a \(2\)-recursive sequence describing the numbers above as well:

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

Various

See also

recognizable series, sage.rings.cfinite_sequence, sage.combinat.binary_recurrence_sequences.

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

class sage.combinat.k_regular_sequence.RecurrenceParser(k, coefficient_ring)

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 kRegularSequenceSpace.from_recurrence() to construct a kRegularSequence.

ind(M, m, ll, uu)

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

INPUT:

  • M, m – parameters of the recursive sequences, see [HKL2021], Definition 3.1

  • ll, uu – parameters of the resulting linear representation, see [HKL2021], 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: from sage.combinat.k_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)}

See also

kRegularSequenceSpace.from_recurrence()

left(recurrence_rules)

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: from collections import namedtuple
sage: from sage.combinat.k_regular_sequence import RecurrenceParser
sage: RP = RecurrenceParser(2, ZZ)
sage: RRD = namedtuple('recurrence_rules_dim', ['dim'])
sage: recurrence_rules = RRD(dim=5)
sage: RP.left(recurrence_rules)
(1, 0, 0, 0, 0)

See also

kRegularSequenceSpace.from_recurrence()

matrix(recurrence_rules, rem, correct_offset=True)

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 – an integer between 0 and k - 1

  • correct_offset – (default: True) a boolean. If True, then the resulting linear representation has no offset. See [HKL2021] 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: from sage.combinat.k_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]

Stern–Brocot Sequence:

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]

Number of Unbordered Factors in the Thue–Morse Sequence:

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]

See also

kRegularSequenceSpace.from_recurrence()

parameters(M, m, coeffs, initial_values, offset=0)

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

INPUT:

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

OUTPUT: a namedtuple recurrence_rules consisting of

  • M, m, l, u, offset – parameters of the recursive sequences, see [HKL2021], Definition 3.1

  • ll, uu, n1, dim – parameters and dimension of the resulting linear representation, see [HKL2021], Theorem A

  • coeffs – a dictionary mapping (r, j) to the coefficients \(c_{r, j}\) as given in [HKL2021], Equation (3.1). If coeffs[(r, j)] is not given for some r and j, then it is assumed to be zero.

  • initial_values – a dictionary mapping integers n to the n-th value of the sequence

EXAMPLES:

sage: from sage.combinat.k_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)
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: 12, 5: 30, 6: 48, 7: 66, 8: 75, 9: 204, 10: 333, 11: 462,
12: 216, 13: 594, -6: 0, -5: 0, -4: 0, -3: 0, -2: 0, -1: 0},
offset=1, n1=3)

See also

kRegularSequenceSpace.from_recurrence()

parse_direct_arguments(M, m, coeffs, initial_values)

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

INPUT:

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

OUTPUT: a tuple consisting of the input parameters

EXAMPLES:

sage: from sage.combinat.k_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})

Stern–Brocot Sequence:

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})

See also

kRegularSequenceSpace.from_recurrence()

parse_recurrence(equations, function, var)

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

INPUT:

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

OUTPUT: a tuple consisting of

EXAMPLES:

sage: from sage.combinat.k_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})

Stern–Brocot Sequence:

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})

See also

kRegularSequenceSpace.from_recurrence()

right(recurrence_rules)

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

kRegularSequenceSpace.from_recurrence()

v_eval_n(recurrence_rules, n)

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

INPUT:

  • recurrence_rules – a namedtuple generated by parameters()

  • n – an integer

OUTPUT: a vector

EXAMPLES:

Stern–Brocot Sequence:

sage: from sage.combinat.k_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)

See also

kRegularSequenceSpace.from_recurrence()

values(M, m, l, u, ll, coeffs, initial_values, last_value_needed, offset)

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

INPUT:

  • M, m, l, u, offset – parameters of the recursive sequences, see [HKL2021], Definition 3.1

  • ll – parameter of the resulting linear representation, see [HKL2021], Theorem A

  • coeffs – a dictionary where coeffs[(r, j)] is the coefficient \(c_{r,j}\) as given in kRegularSequenceSpace.from_recurrence(). If coeffs[(r, j)] is not given for some r and j, then it is assumed to be zero.

  • initial_values – a 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

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: from sage.combinat.k_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)
{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}

See also

kRegularSequenceSpace.from_recurrence()

class sage.combinat.k_regular_sequence.kRegularSequence(parent, mu, left=None, right=None)

Bases: sage.combinat.recognizable_series.RecognizableSeries

A \(k\)-regular sequence.

INPUT:

  • parent – an instance of kRegularSequenceSpace

  • 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.

EXAMPLES:

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

We can access the coefficients of a sequence by

sage: S[5]
11

or iterating over the first, say \(10\), by

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

See also

k-regular sequence, kRegularSequenceSpace.

backward_differences(**kwds)

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 kRegularSequence

Note

The coefficient to the index \(-1\) is \(0\).

EXAMPLES:

sage: Seq2 = kRegularSequenceSpace(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, ...

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, ...
forward_differences(**kwds)

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 kRegularSequence

EXAMPLES:

sage: Seq2 = kRegularSequenceSpace(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, ...

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, ...
partial_sums(*args, **kwds)

Return the sequence of partial sums of this \(k\)-regular sequence. That is, the \(n\) entries in the original sequence.

INPUT:

  • include_n – (default: False) a boolean. 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 kRegularSequence

EXAMPLES:

sage: Seq2 = kRegularSequenceSpace(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, ...

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, ...
shift_left(b=1, **kwds)

Return the sequence obtained by shifting this \(k\)-regular sequence \(b\) steps to the left.

INPUT:

  • b – an 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 kRegularSequence

Note

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

EXAMPLES:

sage: Seq2 = kRegularSequenceSpace(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, ...
shift_right(b=1, **kwds)

Return the sequence obtained by shifting this \(k\)-regular sequence \(b\) steps to the right.

INPUT:

  • b – an 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 kRegularSequence

Note

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

EXAMPLES:

sage: Seq2 = kRegularSequenceSpace(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, ...
subsequence(*args, **kwds)

Return the subsequence with indices \(an+b\) of this \(k\)-regular sequence.

INPUT:

  • a – a nonnegative integer

  • b – an 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(an+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 kRegularSequence

Note

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

EXAMPLES:

sage: Seq2 = kRegularSequenceSpace(2, ZZ)

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

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, ...

We now extract various subsequences of \(C\):

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, ...

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))

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

sage: Sbd = C.subsequence(1, {0: 1, -1: -1}); Sbd
2-regular sequence 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
class sage.combinat.k_regular_sequence.kRegularSequenceSpace(k, *args, **kwds)

Bases: sage.combinat.recognizable_series.RecognizableSeriesSpace

The space of \(k\)-regular Sequences over the given coefficient_ring.

INPUT:

  • k – an integer at least \(2\) specifying the base

  • coefficient_ring – a (semi-)ring

  • category – (default: None) the category of this space

EXAMPLES:

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

See also

k-regular sequence, kRegularSequence.

Element

alias of kRegularSequence

from_recurrence(*args, **kwds)

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 [HKL2021], and are either given as symbolic equations, e.g.,

sage: Seq2 = kRegularSequenceSpace(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, ...

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

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, ...

INPUT:

Positional arguments:

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

  • equations – A 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 coefficents of the corresponding kRegularSequenceSpace, valid for all integers \(n \geq \text{offset}\) for some integer \(\text{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 [HKL2021] 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 [HKL2021], Definition 3.1, as well as in the description of equations above

  • m – parameter of the recursive sequences, see [HKL2021], Definition 3.1, as well as in the description of equations above

  • coeffs – a 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 – a dictionary mapping integers n to the n-th value of the sequence

Optional keyword-only argument:

  • offset – an integer (default: 0). See explanation of equations above.

OUTPUT: a kRegularSequence

EXAMPLES:

Stern–Brocot Sequence:

sage: Seq2 = kRegularSequenceSpace(2, ZZ)
sage: var('n')
n
sage: function('f')
f
sage: 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)
2-regular sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, ...

Number of Odd Entries in Pascal’s Triangle:

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, ...

Number of Unbordered Factors in the Thue–Morse Sequence:

sage: 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)
2-regular sequence 1, 2, 2, 4, 2, 4, 6, 0, 4, 4, ...

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

sage: Seq2 = kRegularSequenceSpace(2, QQ)
sage: 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)
2-regular sequence 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, ...

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

sage: Seq2.from_recurrence(2, 1,
....:     {(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},
....:     {0: 1, 1: 2})
2-regular sequence 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, ...