Stern-Brocot sequence: Difference between revisions
Content added Content deleted
(Add OEIS reference.) |
m (bold a heading.) |
||
Line 20: | Line 20: | ||
9. Consider the next member of the series, (the fourth member i.e. 1)</pre> |
9. Consider the next member of the series, (the fourth member i.e. 1)</pre> |
||
The task is to: |
;The task is to: |
||
# Create a function/method/subroutine/procedure/... to generate the Stern-Brocot sequence of integers. |
# Create a function/method/subroutine/procedure/... to generate the Stern-Brocot sequence of integers. |
||
# 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 first fifteen members of the sequence. (This should be: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4) |
||
Line 28: | Line 28: | ||
Show your output on the page. |
Show your output on the page. |
||
Ref: |
;Ref: |
||
* [https://www.youtube.com/watch?v=DpwUVExX27E Infinite Fractions - Numberphile] (Video). |
* [https://www.youtube.com/watch?v=DpwUVExX27E Infinite Fractions - Numberphile] (Video). |
||
* [http://www.ams.org/samplings/feature-column/fcarc-stern-brocot Trees, Teeth, and Time: The mathematics of clock making]. |
* [http://www.ams.org/samplings/feature-column/fcarc-stern-brocot Trees, Teeth, and Time: The mathematics of clock making]. |
Revision as of 08:55, 7 December 2014
Stern-Brocot sequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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.
- 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.
Python
<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) 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