\(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', 'inhomogeneities'])
sage: recurrence_rules = RRD(dim=5, inhomogeneities={})
sage: RP.left(recurrence_rules)
(1, 0, 0, 0, 0)

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

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, inhomogeneities={})#

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

  • inhomogeneities – a dictionary mapping integers r to the inhomogeneity \(g_r\) as given in [HKL2021], Corollary D.

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, {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, ...})

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

shifted_inhomogeneities(recurrence_rules)#

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

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 [HKL2021], Corollary D, and \(i\) between \(\lfloor\ell'/k^{M}\rfloor\) and \(\lfloor (k^{M-1} - k^{m} + u')/k^{M}\rfloor + 1\); see [HKL2021], 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: from collections import namedtuple
sage: from sage.combinat.k_regular_sequence import RecurrenceParser
sage: RP = RecurrenceParser(2, ZZ)
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: 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, ...}

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

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, inhomogeneities)#

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

  • inhomogeneities – a dictionary mapping integers r to the inhomogeneity \(g_r\) as given in [HKL2021], 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: 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, 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}

See also

kRegularSequenceSpace.from_recurrence()

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

Bases: 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`th entry of the result is the sum of the first `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: 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 coefficients 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 – (default: 0) an integer. See explanation of equations above.

  • inhomogeneities – (default: {}) a dictionary mapping integers r to the inhomogeneity \(g_r\) as given in [HKL2021], Corollary D. All inhomogeneities have to be regular sequences from self or elements of coefficient_ring.

OUTPUT: a kRegularSequence

EXAMPLES:

Stern–Brocot Sequence:

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

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

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

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

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

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

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

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

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

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

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