Opened 8 years ago

Closed 8 years ago

# Binary recurrence sequences

Reported by: Owned by: ivogt161 minor sage-5.13 number theory sage-5.13.beta3 Isabel Vogt Eric Larson N/A

### Description

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.

### comment:1 Changed 8 years ago by elarson3

• Reviewers set to Eric Larson

### comment:2 follow-up: ↓ 5 Changed 8 years ago by 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]

1. 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

1. 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.
1. 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.
1. 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.
1. 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.
1. In is_quasigeometric, there are missing backslashes before alpha and beta. Also, throughout the file, quasigeomtric is sometimes spelled quadigeomtric.
1. 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).
1. 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?
1. _is_p_power_mod function: e confused with 3 in 3rd comment.
Last edited 8 years ago by elarson3 (previous) (diff)

### comment:3 Changed 8 years ago by elarson3

• Status changed from new to needs_review

### comment:4 Changed 8 years ago by elarson3

• Status changed from needs_review to needs_work

### comment:5 in reply to: ↑ 2 Changed 8 years ago by ivogt161

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

### comment:6 Changed 8 years ago by ivogt161

• Status changed from needs_work to needs_review

### comment:7 Changed 8 years ago by 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

1. Doctests pass, with full coverage.
1. PDF and HTML reference manuals build fine.

### comment:8 Changed 8 years ago by elarson3

• Status changed from needs_review to positive_review

### comment:9 Changed 8 years ago by jdemeyer

• Merged in set to sage-5.13.beta3
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.