Binary Recurrence Sequences.¶
This class implements several methods relating to general linear binary recurrence sequences, including a sieve to find perfect powers in integral linear binary recurrence sequences.
EXAMPLES:
sage: R = BinaryRecurrenceSequence(1,1) #the Fibonacci sequence
sage: R(137) #the 137th term of the Fibonacci sequence
19134702400093278081449423917
sage: R(137) == fibonacci(137)
True
sage: [R(i) % 4 for i in xrange(12)]
[0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1]
sage: R.period(4) #the period of the fibonacci sequence modulo 4
6
sage: R.pthpowers(2, 10**30) # long time (7 seconds) -- in fact these are all squares, c.f. [BMS06]
[0, 1, 2, 12]
sage: S = BinaryRecurrenceSequence(8,1) #a Lucas sequence
sage: S.period(73)
148
sage: S(5) % 73 == S(5 +148) %73
True
sage: S.pthpowers(3,10**30) # long time (3 seconds) -- provably finds the indices of all 3rd powers less than 10^30
[0, 1, 2]
sage: T = BinaryRecurrenceSequence(2,0,1,2)
sage: [T(i) for i in xrange(10)]
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
sage: T.is_degenerate()
True
sage: T.is_geometric()
True
sage: T.pthpowers(7,10**30)
Traceback (most recent call last):
...
ValueError: The degenerate binary recurrence sequence is geometric or quasigeometric and has many pth powers.
AUTHORS:
-Isabel Vogt (2013): initial version
REFERENCES:
[SV13] Silliman and Vogt. “Powers in Lucas Sequences via Galois Representations.” Proceedings of the American Mathematical Society, 2013. Arxiv 1307.5078v2
[BMS06] Bugeaud, Mignotte, and Siksek. “Classical and modular approaches to exponential Diophantine equations: I. Fibonacci and Lucas perfect powers.” Annals of Math, 2006.
[SS] Shorey and Stewart. “On the Diophantine equation a x^{2t} + b x^t y + c y^2 = d and pure powers in recurrence sequences.” Mathematica Scandinavica, 1983.
-
class
sage.combinat.binary_recurrence_sequences.
BinaryRecurrenceSequence
(b, c, u0=0, u1=1)¶ Bases:
sage.structure.sage_object.SageObject
Create a linear binary recurrence sequence defined by initial conditions
and
and recurrence relation
.
INPUT:
b
– an integer (partially determining the recurrence relation)c
– an integer (partially determining the recurrence relation)u0
– an integer (the 0th term of the binary recurrence sequence)u1
– an integer (the 1st term of the binary recurrence sequence)
OUTPUT:
- An integral linear binary recurrence sequence defined by
u0
,u1
, and
See also
EXAMPLES:
sage: R = BinaryRecurrenceSequence(3,3,2,1) sage: R Binary recurrence sequence defined by: u_n = 3 * u_{n-1} + 3 * u_{n-2}; With initial conditions: u_0 = 2, and u_1 = 1
-
is_arithmetic
()¶ Decide whether the sequence is degenerate and an arithmetic sequence.
The sequence is arithmetic if and only if
.
This corresponds to the matrix
being nondiagonalizable and
.
EXAMPLES:
sage: S = BinaryRecurrenceSequence(2,-1) sage: [S(i) for i in xrange(10)] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: S.is_arithmetic() True
-
is_degenerate
()¶ Decide whether the binary recurrence sequence is degenerate.
Let
and
denote the roots of the characteristic polynomial
. Let
and
. The sequence is, thus, given by
. Then we say that the sequence is nondegenerate if and only if
and
is not a root of unity.
More concretely, there are 4 classes of degeneracy, that can all be formulated in terms of the matrix
.
is singular – this corresponds to
c
= 0, and thus. This sequence is geometric after term
u0
and so we call itquasigeometric
.is an eigenvector of
– this corresponds to a
geometric
sequence with.
is nondiagonalizable – this corresponds to
. This sequence will be the point-wise product of an arithmetic and geometric sequence.
is scaler, for some
– this corresponds to
a
th root of unity. This sequence is a union of several geometric sequences, and so we again call it
quasigeometric
.
EXAMPLES:
sage: S = BinaryRecurrenceSequence(0,1) sage: S.is_degenerate() True sage: S.is_geometric() False sage: S.is_quasigeometric() True sage: R = BinaryRecurrenceSequence(3,-2) sage: R.is_degenerate() False sage: T = BinaryRecurrenceSequence(2,-1) sage: T.is_degenerate() True sage: T.is_arithmetic() True
-
is_geometric
()¶ Decide whether the binary recurrence sequence is geometric - ie a geometric sequence.
This is a subcase of a degenerate binary recurrence sequence, for which
, i.e.
for some value of
. See
is_degenerate
for a description of degeneracy and definitions ofand
.
EXAMPLES:
sage: S = BinaryRecurrenceSequence(2,0,1,2) sage: [S(i) for i in xrange(10)] [1, 2, 4, 8, 16, 32, 64, 128, 256, 512] sage: S.is_geometric() True
-
is_quasigeometric
()¶ Decide whether the binary recurrence sequence is degenerate and similar to a geometric sequence, i.e. the union of multiple geometric sequences, or geometric after term
u0
.If
is a
th root of unity, where
, then necessarily
. Then
is diagonalizable, and
is scaler matrix. Thus for all values of
mod
, the
mod
terms of
form a geometric series.
If
or
is zero, this implies that
. This is the case when
is singular. In this case,
is geometric.
EXAMPLES:
sage: S = BinaryRecurrenceSequence(0,1) sage: [S(i) for i in xrange(10)] [0, 1, 0, 1, 0, 1, 0, 1, 0, 1] sage: S.is_quasigeometric() True sage: R = BinaryRecurrenceSequence(3,0) sage: [R(i) for i in xrange(10)] [0, 1, 3, 9, 27, 81, 243, 729, 2187, 6561] sage: R.is_quasigeometric() True
-
period
(m)¶ Return the period of the binary recurrence sequence modulo an integer
m
.If
is congruent to
modulu
period(m)
, thenis is congruent to
modulo
m
.INPUT:
m
– an integer (modulo which the period of the recurrence relation is calculated).
OUTPUT:
- The integer (the period of the sequence modulo m)
EXAMPLES:
If
, then the period of the Fibonacci sequence mod
is
(c.f. Lemma 3.3 of [BMS06]).
sage: R = BinaryRecurrenceSequence(1,1) sage: R.period(31) 30 sage: [R(i) % 4 for i in xrange(12)] [0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1] sage: R.period(4) 6
This function works for degenerate sequences as well.
sage: S = BinaryRecurrenceSequence(2,0,1,2) sage: S.is_degenerate() True sage: S.is_geometric() True sage: [S(i) % 17 for i in xrange(16)] [1, 2, 4, 8, 16, 15, 13, 9, 1, 2, 4, 8, 16, 15, 13, 9] sage: S.period(17) 8
Note: the answer is cached.
-
pthpowers
(p, Bound)¶ Find the indices of proveably all pth powers in the recurrence sequence bounded by Bound.
Let
be a binary recurrence sequence. A
p
th power inis a solution to
for some integer
. There are only finitely many
p
th powers in any recurrence sequence [SS].INPUT:
p
- a rational prime integer (the fixed p in)
Bound
- a natural number (the maximum indexin
that is checked).
OUTPUT:
- A list of the indices of all
p
th powers less bounded byBound
. If the sequence is degenerate and there are manyp
th powers, raisesValueError
.
EXAMPLES:
sage: R = BinaryRecurrenceSequence(1,1) #the Fibonacci sequence sage: R.pthpowers(2, 10**30) # long time (7 seconds) -- in fact these are all squares, c.f. [BMS06] [0, 1, 2, 12] sage: S = BinaryRecurrenceSequence(8,1) #a Lucas sequence sage: S.pthpowers(3,10**30) # long time (3 seconds) -- provably finds the indices of all 3rd powers less than 10^30 [0, 1, 2] sage: Q = BinaryRecurrenceSequence(3,3,2,1) sage: Q.pthpowers(11,10**30) # long time (7.5 seconds) [1]
If the sequence is degenerate, and there are are no
p
th powers, returns. Otherwise, if there are many
p
th powers, raisesValueError
.sage: T = BinaryRecurrenceSequence(2,0,1,2) sage: T.is_degenerate() True sage: T.is_geometric() True sage: T.pthpowers(7,10**30) Traceback (most recent call last): ... ValueError: The degenerate binary recurrence sequence is geometric or quasigeometric and has many pth powers. sage: L = BinaryRecurrenceSequence(4,0,2,2) sage: [L(i).factor() for i in xrange(10)] [2, 2, 2^3, 2^5, 2^7, 2^9, 2^11, 2^13, 2^15, 2^17] sage: L.is_quasigeometric() True sage: L.pthpowers(2,10**30) []
NOTE: This function is primarily optimized in the range where
Bound
is much larger thanp
.