\(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 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
left
of 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
rem
of the linear representation of the sequence represented byrecurrence_rules
.INPUT:
recurrence_rules
– a namedtuple generated byparameters()
rem
– an integer between0
andk - 1
correct_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=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 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 somer
andj
, then it is assumed to be zero.initial_values
– a dictionary mapping integersn
to 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_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})
- 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
M
,m
– seekRegularSequenceSpace.from_recurrence()
coeffs
– seekRegularSequenceSpace.from_recurrence()
initial_values
– seekRegularSequenceSpace.from_recurrence()
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 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 somer
andj
, then it is assumed to be zero.initial_values
– a dictionary mapping integersn
to then
-th value of the sequencelast_value_needed
– last initial value which is needed to determine the linear representation
OUTPUT:
A dictionary mapping integers
n
to then
-th value of the sequence for alln
up 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.RecognizableSeries
A \(k\)-regular sequence.
INPUT:
parent
– an instance ofkRegularSequenceSpace
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 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
- backward_differences(**kwds)¶
Return the sequence of backward differences of this \(k\)-regular sequence.
INPUT:
minimize
– (default:None
) a boolean orNone
. IfTrue
, thenminimized()
is called after the operation, ifFalse
, then not. If this argument isNone
, then the default specified by the parent’sminimize_results
is used.
OUTPUT:
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 orNone
. IfTrue
, thenminimized()
is called after the operation, ifFalse
, then not. If this argument isNone
, then the default specified by the parent’sminimize_results
is used.
OUTPUT:
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 orNone
. IfTrue
, thenminimized()
is called after the operation, ifFalse
, then not. If this argument isNone
, then the default specified by the parent’sminimize_results
is used.
OUTPUT:
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 integerminimize
– (default:None
) a boolean orNone
. IfTrue
, thenminimized()
is called after the operation, ifFalse
, then not. If this argument isNone
, then the default specified by the parent’sminimize_results
is used.
OUTPUT:
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 integerminimize
– (default:None
) a boolean orNone
. IfTrue
, thenminimized()
is called after the operation, ifFalse
, then not. If this argument isNone
, then the default specified by the parent’sminimize_results
is used.
OUTPUT:
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 integerb
– an integerAlternatively, 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 orNone
. IfTrue
, thenminimized()
is called after the operation, ifFalse
, then not. If this argument isNone
, then the default specified by the parent’sminimize_results
is used.
OUTPUT:
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 parameterb
: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 basecoefficient_ring
– a (semi-)ringcategory
– (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 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 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) == t
for some integerk
and somet
from the (semi)ringcoefficient_ring
.
The recurrence relations above uniquely determine a \(k\)-regular sequence; see [HKL2021] for further information.
function
– symbolic functionf
occurring in the equationsvar
– symbolic variable (n
in the above description ofequations
)
The following second representation of the recurrence relations is particularly useful for cases where
coefficient_ring
is not compatible withsage.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 ofequations
abovem
– parameter of the recursive sequences, see [HKL2021], Definition 3.1, as well as in the description ofequations
abovecoeffs
– a dictionary wherecoeffs[(r, j)]
is the coefficient \(c_{r,j}\) as given in the description ofequations
above. Ifcoeffs[(r, j)]
is not given for somer
andj
, then it is assumed to be zero.initial_values
– a dictionary mapping integersn
to then
-th value of the sequence
Optional keyword-only argument:
offset
– an integer (default:0
). See explanation ofequations
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, ...