\(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¶
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:
objectA 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 akRegularSequence.- 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.1ll,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
leftof the linear representation of recursive sequences.INPUT:
recurrence_rules– a namedtuple generated byparameters(); it only needs to contain a fielddim(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
remof the linear representation of the sequence represented byrecurrence_rules.INPUT:
recurrence_rules– a namedtuple generated byparameters()rem– an integer between0andk - 1correct_offset– (default:True) a boolean. IfTrue, 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 askRegularSequenceSpace.from_recurrence()coeffs– a dictionary wherecoeffs[(r, j)]is the coefficient \(c_{r,j}\) as given inkRegularSequenceSpace.from_recurrence(). Ifcoeffs[(r, j)]is not given for somerandj, then it is assumed to be zero.initial_values– a dictionary mapping integersnto then-th value of the sequence
OUTPUT:
A namedtuple
recurrence_rulesconsisting ofM,m,l,u,offset– parameters of the recursive sequences, see [HKL2021], Definition 3.1ll,uu,n1,dim– parameters and dimension of the resulting linear representation, see [HKL2021], Theorem Acoeffs– a dictionary mapping(r, j)to the coefficients \(c_{r, j}\) as given in [HKL2021], Equation (3.1). Ifcoeffs[(r, j)]is not given for somerandj, then it is assumed to be zero.initial_values– a dictionary mapping integersnto then-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:
equations– seekRegularSequenceSpace.from_recurrence()function– seekRegularSequenceSpace.from_recurrence()var– seekRegularSequenceSpace.from_recurrence()
OUTPUT:
A tuple consisting of
M,m– parameters of the recursive sequences, see [HKL2021], Definition 3.1coeffs– a dictionary mapping(r, j)to the coefficients \(c_{r, j}\) as given in [HKL2021], Equation (3.1)initial_values– a dictionary mapping integersnto then-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
rightof the linear representation of the sequence induced byrecurrence_rules.INPUT:
recurrence_rules– a namedtuple generated byparameters()
OUTPUT:
A vector.
- v_eval_n(recurrence_rules, n)¶
Return the vector \(v(n)\) as given in [HKL2021], Theorem A.
INPUT:
recurrence_rules– a namedtuple generated byparameters()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)
- 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 ininitial_values.INPUT:
M,m,l,u,offset– parameters of the recursive sequences, see [HKL2021], Definition 3.1ll– parameter of the resulting linear representation, see [HKL2021], Theorem Acoeffs– a dictionary wherecoeffs[(r, j)]is the coefficient \(c_{r,j}\) as given inkRegularSequenceSpace.from_recurrence(). Ifcoeffs[(r, j)]is not given for somerandj, then it is assumed to be zero.initial_values– a dictionary mapping integersnto then-th value of the sequencelast_value_needed– last initial value which is needed to determine the linear representation
OUTPUT:
A dictionary mapping integers
nto then-th value of the sequence for allnup tolast_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)¶
Bases:
sage.combinat.recognizable_series.RecognizableSeriesA \(k\)-regular sequence.
INPUT:
parent– an instance ofkRegularSequenceSpacemu– a family of square matrices, all of which have the same dimension. The indices of this family are \(0,...,k-1\).mumay be a list or tuple of cardinality \(k\) as well. See alsomu().left– (default:None) a vector. When evaluating the sequence, this vector is multiplied from the left to the matrix product. IfNone, 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. IfNone, 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
- class sage.combinat.k_regular_sequence.kRegularSequenceSpace(k, *args, **kwds)¶
Bases:
sage.combinat.recognizable_series.RecognizableSeriesSpaceThe space of \(k\)-regular Sequences over the given
coefficients.INPUT:
k– an integer at least \(2\) specifying the basecoefficient_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
- 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
coefficentsof the correspondingkRegularSequenceSpace, 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) == tfor some integerkand sometfrom the (semi)ringcoefficients.
The recurrence relations above uniquely determine a \(k\)-regular sequence; see [HKL2021] for further information.
function– symbolic functionfoccuring in the equationsvar– symbolic variable (nin the above description ofequations)offset– an integer (default:0). See explanation forequationsabove.
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, ...