Binary recurrence sequences

[ivogt161]

This patch implements several methods relating to general integral linear binary recurrence sequences, including a sieve to find perfect powers in integral linear binary recurrence sequences.

[elarson3]

Issues with code:

1. The is_arithmetic function is broken:

sage: S = BinaryRecurrenceSequence(1,1,1,2)
sage: S.is_arithmetic()
True
sage: [S(i) for i in xrange(10)]
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

2. There is some issue with the caching in the period function:

sage: S = BinaryRecurrenceSequence(2, -1)
sage: S.period(9)
9
sage: S.period(3)
1
sage: S = BinaryRecurrenceSequence(2, -1) # but re-initialize to clear cache, and we get the right answer...
sage: S.period(3)
3

3. The pthpowers function performs sub-optimally when Bound is small compared to p.

Issues with documentation:

1. References don't print in the PDF manual.

2. In the BinaryRecurrenceSequence? class, order of input listed in documentation does not match order of input expected by init. Also, missing underscores on u0 and u1 cause funny PDF output.

3. In is_degenerate, the documentation claims u_n = au_{n-1} - bu_{n+1}, which is wrong. Also, please insert a comment saying what aa and bb are; and also a remark that \alpha, \beta are (b \pm A)/2. Again, missing underscores on u0 and u1 cause funny PDF output.

4. In is_geometric, the documentation says u_n = a * u_{n-1} or u_n = b * u_{n-2}, but this isn't what the code checks. Also "sage: S = BinaryRecurrenceSequence?(2,0,1,2)" is written twice.

5. In is_quasigeometric, there are missing backslashes before alpha and beta. Also, throughout the file, quasigeomtric is sometimes spelled quadigeomtric.

6. In period function, there is only one - after m in INPUT section, which causes funny output in PDF documentation. Also, there needs to be a note that the answer is cached (c.f. above issue with code).

6. In pthpowers function, "check" should be "checked", and "U_n" should be "u_n". Also, comments claim the code continues after 5 rounds of increasing modulus, but the code checks if it increased 7 times?

7. _is_p_power_mod function: e confused with 3 in 3rd comment.

[ivogt161]

Fixed all issues, except the first documentation issue (which isn't actually an issue; you must have not built the pdf correctly).

[elarson3]

Looks good now:

1. All issues raised above have been fixed satisfactorily. In particular:

sage: S = BinaryRecurrenceSequence(1,1,1,2)
sage: S.is_arithmetic()
False

sage: S = BinaryRecurrenceSequence(2, -1)
sage: S.period(9)
9
sage: S.period(3)
3

2. Doctests pass, with full coverage.

3. PDF and HTML reference manuals build fine.