# $$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(floor(n/2)) + u(ceil(n/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¶

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

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)

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]

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

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

INPUT:

• M, m, offset – parameters of the recursive sequences, see [HKL2021], Definition 3.1, as well as kRegularSequenceSpace.from_recurrence()

• 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

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)

parse_recurrence(equations, function, var)

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

INPUT:

OUTPUT:

A tuple consisting of

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

• coeffs – a dictionary mapping (r, j) to the coefficients $$c_{r, j}$$ as given in [HKL2021], Equation (3.1)

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

right(recurrence_rules)

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

INPUT:

OUTPUT:

A vector.

v_eval_n(recurrence_rules, n)

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

INPUT:

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)

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}

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

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]

class sage.combinat.k_regular_sequence.kRegularSequenceSpace(k, *args, **kwds)

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

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


Element

alias of kRegularSequence

from_recurrence(*args, **kwds)

Construct a $$k$$-regular sequence that fulfills the recurrence relations given in equations.

INPUT:

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

The recurrence relations above uniquely determine a $$k$$-regular sequence; see [HKL2021] for further information.

• function – symbolic function f occuring in the equations

• var – symbolic variable (n in the above description of equations)

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

OUTPUT:

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