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.
Bases: sage.structure.sage_object.SageObject
Create a linear binary recurrence sequence defined by initial conditions \(u_0\) and \(u_1\) and recurrence relation \(u_{n+2} = b*u_{n+1}+c*u_n\).
INPUT:
OUTPUT:
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
Decide whether the sequence is degenerate and an arithmetic sequence.
The sequence is arithmetic if and only if \(u_1 - u_0 = u_2 - u_1 = u_3 - u_2\).
This corresponds to the matrix \(F = [[0,1],[c,b]]\) being nondiagonalizable and \(\alpha/\beta = 1\).
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
Decide whether the binary recurrence sequence is degenerate.
Let \(\alpha\) and \(\beta\) denote the roots of the characteristic polynomial \(p(x) = x^2-bx -c\). Let \(a = u_1-u_0\beta/(\beta - \alpha)\) and \(b = u_1-u_0\alpha/(\beta - \alpha)\). The sequence is, thus, given by \(u_n = a \alpha^n - b\beta^n\). Then we say that the sequence is nondegenerate if and only if \(a*b*\alpha*\beta \neq 0\) and \(\alpha/\beta\) is not a root of unity.
More concretely, there are 4 classes of degeneracy, that can all be formulated in terms of the matrix \(F = [[0,1], [c, b]]\).
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
Decide whether the binary recurrence sequence is geometric - ie a geometric sequence.
This is a subcase of a degenerate binary recurrence sequence, for which \(ab=0\), i.e. \(u_{n}/u_{n-1}=r\) for some value of \(r\). See is_degenerate for a description of degeneracy and definitions of \(a\) and \(b\).
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
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 \(\alpha/\beta\) is a \(k\) th root of unity, where \(k>1\), then necessarily \(k = 2, 3, 4, 6\). Then \(F = [[0,1],[c,b]\) is diagonalizable, and \(F^k = [[\alpha^k, 0], [0,\beta^k]]\) is scaler matrix. Thus for all values of \(j\) mod \(k\), the \(j\) mod \(k\) terms of \(u_n\) form a geometric series.
If \(\alpha\) or \(\beta\) is zero, this implies that \(c=0\). This is the case when \(F\) is singular. In this case, \(u_1, u_2, u_3, ...\) 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
Return the period of the binary recurrence sequence modulo an integer m.
If \(n_1\) is congruent to \(n_2\) modulu period(m), then \(u_{n_1}\) is is congruent to \(u_{n_2}\) modulo m.
INPUT:
OUTPUT:
EXAMPLES:
If \(p = \pm 1 \mod 5\), then the period of the Fibonacci sequence mod \(p\) is \(p-1\) (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.
Find the indices of proveably all pth powers in the recurrence sequence bounded by Bound.
Let \(u_n\) be a binary recurrence sequence. A p th power in \(u_n\) is a solution to \(u_n = y^p\) for some integer \(y\). There are only finitely many p th powers in any recurrence sequence [SS].
INPUT:
OUTPUT:
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, raises ValueError.
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 than p.