Stern-Brocot sequence
For this task, the Stern-Brocot sequence is to be generated by an algorithm similar to that employed in generating the Fibonacci sequence.
1. The first and second members of the sequence are both 1
1, 1
2. Start by considering the second member of the sequence
3. Sum the considered member of the sequence and its precedent, (1 + 1) = 2, and append it to the end of the sequence.
1, 1, 2
4. Append the considered member of the sequence to the end of the sequence.
1, 1, 2, 1
5. Consider the next member of the series, (the third member i.e. 2)
6. GOTO 3
Expanding another loop we get:
7. Sum the considered member of the sequence and its precedent, (2 + 1) = 3, and append it to the end of the sequence.
1, 1, 2, 1, 3
8. Append the considered member of the sequence to the end of the sequence.
1, 1, 2, 1, 3, 2
9. Consider the next member of the series, (the fourth member i.e. 1)
- The task is to
- Create a function/method/subroutine/procedure/... to generate the Stern-Brocot sequence of integers using the method outlined above.
- Show the first fifteen members of the sequence. (This should be: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4)
- Show the (1-based) index of where the numbers 1-to-10 first appears in the sequence.
- Show the (1-based) index of where the number 100 first appears in the sequence.
- Check that the greatest common divisor of all the two consecutive members of the series up to the 1000th member, is always one.
Show your output on the page.
- Ref
- Infinite Fractions - Numberphile (Video).
- Trees, Teeth, and Time: The mathematics of clock making.
- A002487 The On-Line Encyclopedia of Integer Sequences.
C
Recursive function. <lang c>#include <stdio.h>
typedef unsigned int uint;
/* the sequence, 0-th member is 0 */ uint f(uint n) { return n < 2 ? n : (n&1) ? f(n/2) + f(n/2 + 1) : f(n/2); }
uint gcd(uint a, uint b) { return a ? a < b ? gcd(b%a, a) : gcd(a%b, b) : b; }
void find(uint from, uint to) { do { uint n; for (n = 1; f(n) != from ; n++); printf("%3u at Stern #%u.\n", from, n); } while (++from <= to); }
int main(void) { uint n; for (n = 1; n < 16; n++) printf("%u ", f(n)); puts("are the first fifteen.");
find(1, 10); find(100, 0);
for (n = 1; n < 1000 && gcd(f(n), f(n+1)) == 1; n++); printf(n == 1000 ? "All GCDs are 1.\n" : "GCD of #%d and #%d is not 1", n, n+1);
return 0; }</lang>
- Output:
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 are the first fifteen. 1 at Stern #1. 2 at Stern #3. 3 at Stern #5. 4 at Stern #9. 5 at Stern #11. 6 at Stern #33. 7 at Stern #19. 8 at Stern #21. 9 at Stern #35. 10 at Stern #39. 100 at Stern #1179. All GCDs are 1.
The above f() can be replaced by the following, which is much faster but probably less obvious as to how it arrives from the recurrence relations.
<lang c>uint f(uint n)
{
uint a = 1, b = 0;
while (n) {
if (n&1) b += a;
else a += b;
n >>= 1;
}
return b;
}</lang>
D
<lang d>import std.stdio, std.numeric, std.range, std.algorithm;
/// Generates members of the stern-brocot series, in order, /// returning them when the predicate becomes false. uint[] sternBrocot(bool delegate(in uint[]) pure nothrow @safe @nogc pred=seq => seq.length < 20) pure nothrow @safe {
typeof(return) sb = [1, 1];
size_t i = 0;
while (pred(sb)) {
sb ~= [sb[i .. i + 2].sum, sb[i + 1]];
i++;
}
return sb;
}
void main() {
enum nFirst = 15;
writefln("The first %d values:\n%s\n", nFirst,
sternBrocot(seq => seq.length < nFirst).take(nFirst));
foreach (immutable nOccur; iota(1, 10 + 1).chain(100.only))
writefln("1-based index of the first occurrence of %3d in the series: %d",
nOccur, sternBrocot(seq => nOccur != seq[$ - 2]).length - 1);
enum nGcd = 1_000;
auto s = sternBrocot(seq => seq.length < nGcd).take(nGcd);
assert(zip(s, s.dropOne).all!(ss => ss[].gcd == 1),
"A fraction from adjacent terms is reducible.");
}</lang>
- Output:
The first 15 values: [1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4] 1-based index of the first occurrence of 1 in the series: 1 1-based index of the first occurrence of 2 in the series: 3 1-based index of the first occurrence of 3 in the series: 5 1-based index of the first occurrence of 4 in the series: 9 1-based index of the first occurrence of 5 in the series: 11 1-based index of the first occurrence of 6 in the series: 33 1-based index of the first occurrence of 7 in the series: 19 1-based index of the first occurrence of 8 in the series: 21 1-based index of the first occurrence of 9 in the series: 35 1-based index of the first occurrence of 10 in the series: 39 1-based index of the first occurrence of 100 in the series: 1179
This uses a queue from the Queue/usage Task: <lang d>import std.stdio, std.algorithm, std.range, std.numeric, queue_usage2;
struct SternBrocot {
private auto sb = GrowableCircularQueue!uint(1, 1);
enum empty = false;
@property uint front() pure nothrow @safe @nogc {
return sb.front;
}
uint popFront() pure nothrow @safe {
sb.push(sb.front + sb[1]);
sb.push(sb[1]);
return sb.pop;
}
}
void main() {
SternBrocot().drop(50_000_000).front.writeln;
}</lang>
- Output:
7004
Recursive version:
<lang d>void main() {
import std.stdio, std.numeric, std.range, std.algorithm;
/// Stern-Brocot sequence, 0-th member is 0.
static uint sb(in uint n) pure nothrow @safe @nogc {
return (n < 2) ? n : ((n % 2) ? sb(n / 2) + sb(n / 2 + 1) : sb(n / 2));
}
enum nFirst = 15;
writefln("The first %d values:\n%s\n", nFirst, iota(1, nFirst + 1).map!sb);
foreach (immutable nOccur; iota(1, 10 + 1).chain(100.only))
writefln("1-based index of the first occurrence of %3d in the series: %d",
nOccur, sequence!q{n}.until!(n => sb(n) == nOccur).walkLength);
auto s = iota(1, 1_001).map!sb;
assert(s.zip(s.dropOne).all!(ss => ss[].gcd == 1),
"A fraction from adjacent terms is reducible.");
}</lang> The output is the same as the first version.
Haskell
<lang haskell>import Data.List
sb = 1:1: f (tail sb) sb where f (a:aa) (b:bb) = a+b : a : f aa bb
main = do print $ take 15 sb print [(i,1 + (\(Just i)->i) (elemIndex i sb)) | i <- [1..10]++[100]] print $ all (\(a,b)->1 == gcd a b) $ take 1000 $ zip sb (tail sb)</lang>
- Output:
[1,1,2,1,3,2,3,1,4,3,5,2,5,3,4] [(1,1),(2,3),(3,5),(4,9),(5,11),(6,33),(7,19),(8,21),(9,35),(10,39),(100,1179)] True
Python
Python: procedural
<lang python>def stern_brocot(predicate=lambda series: len(series) < 20):
"""\ Generates members of the stern-brocot series, in order, returning them when the predicate becomes false
>>> print('The first 10 values:',
stern_brocot(lambda series: len(series) < 10)[:10])
The first 10 values: [1, 1, 2, 1, 3, 2, 3, 1, 4, 3]
>>>
"""
sb, i = [1, 1], 0
while predicate(sb):
sb += [sum(sb[i:i + 2]), sb[i + 1]]
i += 1
return sb
if __name__ == '__main__':
from fractions import gcd
n_first = 15
print('The first %i values:\n ' % n_first,
stern_brocot(lambda series: len(series) < n_first)[:n_first])
print()
n_max = 10
for n_occur in list(range(1, n_max + 1)) + [100]:
print('1-based index of the first occurrence of %3i in the series:' % n_occur,
stern_brocot(lambda series: n_occur not in series).index(n_occur) + 1)
# The following would be much faster. Note that new values always occur at odd indices
# len(stern_brocot(lambda series: n_occur != series[-2])) - 1)
print()
n_gcd = 1000
s = stern_brocot(lambda series: len(series) < n_gcd)[:n_gcd]
assert all(gcd(prev, this) == 1
for prev, this in zip(s, s[1:])), 'A fraction from adjacent terms is reducible'</lang>
- Output:
The first 15 values: [1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4] 1-based index of the first occurrence of 1 in the series: 1 1-based index of the first occurrence of 2 in the series: 3 1-based index of the first occurrence of 3 in the series: 5 1-based index of the first occurrence of 4 in the series: 9 1-based index of the first occurrence of 5 in the series: 11 1-based index of the first occurrence of 6 in the series: 33 1-based index of the first occurrence of 7 in the series: 19 1-based index of the first occurrence of 8 in the series: 21 1-based index of the first occurrence of 9 in the series: 35 1-based index of the first occurrence of 10 in the series: 39 1-based index of the first occurrence of 100 in the series: 1179
Python: More functional
An iterator is used to produce successive members of the sequence. (its sb variable stores less compared to the procedural version aboveby popping the last element every time around the while loop.
In checking the gcd's, two iterators are tee'd off from the one stream with the second advanced by one value with its call to next().
See the talk page for how a deque was selected over the use of a straightforward list' <lang python>>>> from itertools import takewhile, tee, islice >>> from collections import deque >>> from fractions import gcd >>> >>> def stern_brocot():
sb = deque([1, 1])
while True:
sb += [sb[0] + sb[1], sb[1]]
yield sb.popleft()
>>> [s for _, s in zip(range(15), stern_brocot())]
[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]
>>> [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot()))
for occur in (list(range(1, 11)) + [100])]
[1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 1179] >>> prev, this = tee(stern_brocot(), 2) >>> next(this) 1 >>> all(gcd(p, t) == 1 for p, t in islice(zip(prev, this), 1000)) True >>> </lang>