# 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 range(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 range(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

See [SV2013], [BMS2006], and [SS1983].

class sage.combinat.binary_recurrence_sequences.BinaryRecurrenceSequence(b, c, u0=0, u1=1)

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:

• 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 $$u_{n+2} = b*u_{n+1}+c*u_n$$

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 $$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 range(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 $$\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]]$$.

• $$F$$ is singular – this corresponds to c = 0, and thus $$\alpha*\beta = 0$$. This sequence is geometric after term u0 and so we call it quasigeometric.
• $$v = [[u_0], [u_1]]$$ is an eigenvector of $$F$$ – this corresponds to a geometric sequence with $$a*b = 0$$.
• $$F$$ is nondiagonalizable – this corresponds to $$\alpha = \beta$$. This sequence will be the point-wise product of an arithmetic and geometric sequence.
• $$F^k$$ is scaler, for some $$k>1$$ – this corresponds to $$\alpha/\beta$$ a $$k$$ 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 $$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 range(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 $$\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 range(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 range(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 $$n_1$$ is congruent to $$n_2$$ modulo period(m), then $$u_{n_1}$$ is is congruent to $$u_{n_2}$$ 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 $$p = \pm 1 \mod 5$$, then the period of the Fibonacci sequence mod $$p$$ is $$p-1$$ (c.f. Lemma 3.3 of [BMS2006]).

sage: R = BinaryRecurrenceSequence(1,1)
sage: R.period(31)
30

sage: [R(i) % 4 for i in range(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 range(16)]
[1, 2, 4, 8, 16, 15, 13, 9, 1, 2, 4, 8, 16, 15, 13, 9]
sage: S.period(17)
8


pthpowers(p, Bound)

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 [SS1983].

INPUT:

• p - a rational prime integer (the fixed p in $$u_n = y^p$$)
• Bound - a natural number (the maximum index $$n$$ in $$u_n = y^p$$ that is checked).

OUTPUT:

• A list of the indices of all p th powers less bounded by Bound. If the sequence is degenerate and there are many p th powers, raises ValueError.

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. [BMS2006]_
[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)



If the sequence is degenerate, and there 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 range(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.