75 lines
2.1 KiB
Go
75 lines
2.1 KiB
Go
// SB implements the Stern-Brocot sequence.
|
|
//
|
|
// Generator() satisfies RC Task 1. For remaining tasks, Generator could be
|
|
// used but FirstN(), and Find() are simpler methods for specific stopping
|
|
// criteria. FirstN and Find might also be considered to satisfy Task 1,
|
|
// in which case Generator would not really be needed. Anyway, there it is.
|
|
package sb
|
|
|
|
// Seq represents an even number of terms of a Stern-Brocot sequence.
|
|
//
|
|
// Terms are stored in a slice. Terms start with 1.
|
|
// (Specifically, the zeroth term, 0, given in OEIS A002487 is not represented.)
|
|
// Term 1 (== 1) is stored at slice index 0.
|
|
//
|
|
// Methods on Seq rely on Seq always containing an even number of terms.
|
|
type Seq []int
|
|
|
|
// New returns a Seq with the two base terms.
|
|
func New() *Seq {
|
|
return &Seq{1, 1} // Step 1 of the RC task.
|
|
}
|
|
|
|
// TwoMore appends two more terms to p.
|
|
// It's the body of the loop in the RC algorithm.
|
|
// Generate(), FirstN(), and Find() wrap this body in different ways.
|
|
func (p *Seq) TwoMore() {
|
|
s := *p
|
|
n := len(s) / 2 // Steps 2 and 5 of the RC task.
|
|
c := s[n]
|
|
*p = append(s, c+s[n-1], c) // Steps 3 and 4 of the RC task.
|
|
}
|
|
|
|
// Generator returns a generator function that returns successive terms
|
|
// (until overflow.)
|
|
func Generator() func() int {
|
|
n := 0
|
|
p := New()
|
|
return func() int {
|
|
if len(*p) == n {
|
|
p.TwoMore()
|
|
}
|
|
t := (*p)[n]
|
|
n++
|
|
return t
|
|
}
|
|
}
|
|
|
|
// FirstN lazily extends p as needed so that it has at least n terms.
|
|
// FirstN then returns a list of the first n terms.
|
|
func (p *Seq) FirstN(n int) []int {
|
|
for len(*p) < n {
|
|
p.TwoMore()
|
|
}
|
|
return []int((*p)[:n])
|
|
}
|
|
|
|
// Find lazily extends p as needed until it contains the value x
|
|
// Find then returns the slice index of x in p.
|
|
func (p *Seq) Find(x int) int {
|
|
for n, f := range *p {
|
|
if f == x {
|
|
return n
|
|
}
|
|
}
|
|
for {
|
|
p.TwoMore()
|
|
switch x {
|
|
case (*p)[len(*p)-2]:
|
|
return len(*p) - 2
|
|
case (*p)[len(*p)-1]:
|
|
return len(*p) - 1
|
|
}
|
|
}
|
|
}
|