152:
above.) The left and right fractions do not correspond to vertices in the same row as the vertex, but rather to vertices in some preceding row. Each such fraction can be understood as labeling the region of the plane bounded by two infinite paths descending from the preceding vertex labeled by the same fraction. The second element of a triple will always be the mediant of the first and third elements. For example, the root is associated with
20:
151:
Each vertex in the tree can be associated with a triple of fractions consisting of three fractions in the same row as the vertex, namely the fraction immediately to the left of the vertex, the fraction at the vertex itself, and the fraction immediately to the right of the vertex. (Refer to the figure
2473:
and its ancestor must both be taken in lowest terms, and if there is no smaller or larger ancestor then 0/1 or 1/0 should be used respectively. Again, using 7/5 as an example, its closest smaller ancestor is 4/3, so its left child is (4 + 7)/(3 + 5) = 11/8, and its
904:
1149:
but using this equivalence to replace every continued fraction ending with a one by a shorter continued fraction shows that every rational number has a unique representation in which the last coefficient is greater than one. Then, unless
2661:
1461:
596:
511:
426:
357:
288:
219:
629:
1595:
2793:
2513:
A similar process of mediant insertion, starting with a different pair of interval endpoints , may also be seen to describe the construction of the vertices at each level of the Stern–Brocot tree. The
2737:
1283:
Equivalently this parent is formed by decreasing the denominator in the innermost term of the continued fraction by 1, and contracting with the previous term if the fraction becomes
2536:
Thus the Stern–Brocot sequences differ from the Farey sequences in two ways: they eventually include all positive rationals, not just the rationals within the interval , and at the
2844:
1310:
1863:
2854:
for the rational numbers, prioritized by their denominators. In other words, it is the unique binary search tree of the rational numbers in which the parent of any vertex
1325:
2422:
numbers into rational numbers. By stopping once the desired precision is reached, floating-point numbers can be approximated to arbitrary precision. If a real number
978:
951:
2563:
1777:
1174:
1147:
2795:
are two consecutive fractions at or above a certain level in the tree (in the sense that any fraction between them, must be in a lower level of the tree), then
2036:
2016:
1996:
1976:
1956:
1617:
1281:
1194:
924:
624:
2494:. As in the binary search technique for generating the Stern–Brocot tree, the Farey sequences can be constructed using mediants: the Farey sequence of order
103:
The root of the Stern–Brocot tree corresponds to the number 1. The parent-child relation between numbers in the Stern–Brocot tree may be defined in terms of
2100:
steps to be precise). Therefore, every positive rational number appears exactly once in this tree. Moreover all descendants of the left child of any number
1466:
3217:
516:
431:
2224:. Augment the non-negative rational numbers to including a value 1/0 (representing +∞) that is by definition greater than all other rationals. The
362:
293:
224:
155:
2548:
may be found by an inorder traversal of the left subtree of the Stern–Brocot tree, backtracking whenever a number with denominator greater than
2882:
in the Stern–Brocot tree is the rational number in the closed interval that has the smallest denominator among all numbers in this interval.
3122:
2934:
2925:. Like the Stern–Brocot tree, the Calkin–Wilf tree contains each positive rational number exactly once, but it is not a binary search tree.
2850:
Along with the definitions in terms of continued fractions and mediants described above, the Stern–Brocot tree may also be defined as a
606:
The relationship between parents and descendants can also be understood in terms of continued fractions. Every positive rational number
2434:
that is not in the sequence of mediants found by the algorithm above, then the sequence of mediants contains a closer approximation to
2996:
2980:
3305:
2669:
899:{\displaystyle q=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{k}}}}}}}}}}}=}
2521:
is the sequence formed by inserting a mediant between each consecutive pair of values in the Stern–Brocot sequence of order
3114:
2746:
2071:
It is clear that for each finite continued fraction expression one can repeatedly move to its parent, and reach the root =
3300:
2443:
1782:
116:
2886:
2139:
with respect to the usual ordering of the rational numbers. The set of rational numbers descending from a node
139:. The left subtree of the Stern–Brocot tree, containing the rational numbers in the range (0,1), is called the
2474:
closest larger ancestor is 3/2, so its right child is (7 + 3)/(5 + 2) = 10/7.
2225:
3040:
2871:
1622:
2490:
is the sorted sequence of fractions in the closed interval that have denominator less than or equal to
2453:
The Stern–Brocot tree may itself be defined directly in terms of mediants: the left child of any number
2221:
983:
108:
51:
2940:
2890:
1868:
1199:
3161:
3086:
1286:
132:
2533:
levels of the Stern–Brocot tree, together with the boundary values 0/1 and 1/0, in numerical order.
3183:
3095:
47:
3151:
3018:
2510: + 1, and placing these mediants between the two values from which they were computed.
2136:
104:
2801:
3237:
3118:
2976:
3173:
3090:
2656:{\displaystyle {{\frac {p_{1}}{q_{1}}},{\frac {p_{2}}{q_{2}}},\dots ,{\frac {p_{n}}{q_{n}}}}}
3128:
3080:
3008:
956:
929:
135:
of the tree provides a method of listing all positive rationals that is closely related to
3132:
62:
59:
1153:
3165:
2120:
in the tree are the numbers for which the sum of the continued fraction coefficients is
2968:
2851:
2502:
by computing the mediant of each two consecutive values in the Farey sequence of order
2483:
2419:
2377:
computed by this search is exactly the sequence of values on the path from the root to
2021:
2001:
1981:
1961:
1602:
1179:
909:
609:
136:
81:
3241:
3294:
2960:
2937:, whose definition for rational arguments is closely related to the Stern–Brocot tree
2217:
97:
36:
3022:
3193:
2964:
1456:{\displaystyle {\frac {23}{16}}=1+{\cfrac {1}{2+{\cfrac {1}{3+{\frac {1}{2}}}}}}=,}
73:
3079:
Brocot, Achille (1862), "Calcul des rouages par approximation, nouvelle méthode",
3066:
Brocot, Achille (1861), "Calcul des rouages par approximation, nouvelle méthode",
1998:
and it is the right child (in fact the former expression gives the left child if
1196:
has a parent in the Stern–Brocot tree given by the continued fraction expression
3277:
3268:
3207:
3109:
Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009),
591:{\displaystyle \left({\tfrac {c}{d}},{\tfrac {c+e}{d+f}},{\tfrac {e}{f}}\right)}
506:{\displaystyle \left({\tfrac {a}{b}},{\tfrac {a+c}{b+d}},{\tfrac {c}{d}}\right)}
124:
66:
44:
3286:
sequence A002487 (Stern's diatomic series (or Stern-Brocot sequence))
3187:
2540:
th step all mediants are included, not only the ones with denominator equal to
3273:
3264:
3258:
3226:
3013:
93:
89:
19:
3052:
Bogomolny credits this property to Pierre
Lamothe, a Canadian music theorist.
3246:
421:{\displaystyle \left({\tfrac {a}{b}},{\tfrac {c}{d}},{\tfrac {e}{f}}\right)}
352:{\displaystyle \left({\tfrac {1}{1}},{\tfrac {2}{1}},{\tfrac {1}{0}}\right)}
283:{\displaystyle \left({\tfrac {0}{1}},{\tfrac {1}{2}},{\tfrac {1}{1}}\right)}
214:{\displaystyle \left({\tfrac {0}{1}},{\tfrac {1}{1}},{\tfrac {1}{0}}\right)}
55:
131:. Because the tree contains each positive rational number exactly once, a
3254:
2506:, keeping the subset of mediants that have denominator exactly equal to
2411:
in the Stern–Brocot tree is the last mediant found that is not equal to
2663:
are all the rationals at the same depth in the Stern–Brocot tree, then
2866:
and its parent are both integers, in which the parent is smaller than
359:. The tree is generated by the following rule: the left descendent of
3211:
2517:
of order 0 is the sequence , and the Stern–Brocot sequence of order
2885:
Permuting the vertices on each level of the Stern–Brocot tree by a
1779:
then one child is the number represented by the continued fraction
1590:{\displaystyle ==1+{\cfrac {1}{2+{\frac {1}{4}}}}={\frac {13}{9}}.}
3156:
3111:
Combinatorics on words. Christoffel words and repetitions in words
3282:
2038:
is even). For instance, the continued fraction representation of
980:
is a positive integer. This representation is not unique because
92:
who used the Stern–Brocot tree to design systems of gears with a
1865:
while the other child is represented by the continued fraction
23:
The Stern–Brocot tree, and the Stern–Brocot sequences of order
65:, whose values are ordered from the left to the right as in a
3285:
953:
are non-negative integers, and each subsequent coefficient
111:, and a path in the tree from the root to any other number
88:). Stern was a German number theorist; Brocot was a French
2870:). It follows from the theory of Cartesian trees that the
2498: + 1 is formed from the Farey sequence of order
2461:
with its closest smaller ancestor, and the right child of
3081:
https://gallica.bnf.fr/ark:/12148/bpt6k1661912?rk=21459;2
2525: − 1. The Stern–Brocot sequence of order
2732:{\displaystyle \sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1}
2389:) occurring at some step in the search is the interval (
2220:
algorithm, which may be expressed in a simple way using
3175:
Trees, Teeth, and Time: The mathematics of clock making
3039:. A Java implementation of this algorithm can be found
2999:(2006), "Functional pearl: Enumerating the rationals",
1545:
1533:
1389:
1377:
1363:
1351:
792:
780:
766:
754:
733:
721:
700:
688:
667:
655:
221:
and its left and right descendents are associated with
3113:, CRM Monograph Series, vol. 27, Providence, RI:
1978:
and this is the left child; the other is greater than
1619:
in the Stern–Brocot tree has exactly two children: if
1548:
1536:
1392:
1380:
1366:
1354:
1291:
795:
783:
769:
757:
736:
724:
703:
691:
670:
658:
572:
541:
526:
487:
456:
441:
402:
387:
372:
333:
318:
303:
264:
249:
234:
195:
180:
165:
72:
The Stern–Brocot tree was introduced independently by
2975:(Second ed.), Addison-Wesley, pp. 116–118,
2804:
2749:
2672:
2566:
2024:
2004:
1984:
1964:
1871:
1786:
1785:
1625:
1605:
1469:
1463:
so its parent in the Stern–Brocot tree is the number
1328:
1289:
1202:
1182:
1156:
986:
959:
932:
912:
632:
626:
may be expressed as a continued fraction of the form
612:
519:
434:
365:
296:
227:
158:
2788:{\displaystyle {{\frac {p}{q}}<{\frac {p'}{q'}}}}
2418:
This binary search procedure can be used to convert
2469:with its closest larger ancestor. In this formula,
2838:
2787:
2731:
2655:
2030:
2010:
1990:
1970:
1950:
1857:
1771:
1611:
1589:
1455:
1304:
1275:
1188:
1168:
1141:
972:
945:
918:
898:
618:
590:
505:
420:
351:
282:
213:
96:close to some desired value by finding a ratio of
3096:Journal für die reine und angewandte Mathematik
2403:) representing the descendants of the mediant
2381:in the Stern–Brocot tree. Each open interval (
8:
2108:, and all descendants of the right child of
2216:in the Stern–Brocot tree may be found by a
2048:is and its two children are =
1322:has the continued fraction representation
3228:MF96: Fractions and the Stern-Brocot tree
3218:On-line Encyclopedia of Integer Sequences
3155:
3012:
2803:
2764:
2751:
2750:
2748:
2714:
2704:
2694:
2688:
2677:
2671:
2644:
2634:
2628:
2611:
2601:
2595:
2584:
2574:
2568:
2567:
2565:
2442:; in that sense, these mediants form the
2023:
2003:
1983:
1963:
1924:
1905:
1892:
1879:
1870:
1839:
1820:
1807:
1794:
1784:
1748:
1729:
1716:
1703:
1684:
1665:
1652:
1639:
1624:
1604:
1574:
1556:
1549:
1537:
1530:
1468:
1400:
1393:
1381:
1374:
1367:
1355:
1348:
1329:
1327:
1290:
1288:
1255:
1236:
1223:
1210:
1201:
1181:
1155:
1115:
1096:
1083:
1070:
1039:
1020:
1007:
994:
985:
964:
958:
937:
931:
911:
887:
868:
855:
842:
801:
796:
784:
777:
770:
758:
751:
742:
737:
725:
718:
709:
704:
692:
685:
676:
671:
659:
652:
643:
631:
611:
571:
540:
525:
518:
486:
455:
440:
433:
401:
386:
371:
364:
332:
317:
302:
295:
263:
248:
233:
226:
194:
179:
164:
157:
3091:"Ueber eine zahlentheoretische Funktion"
2438:that has a denominator at most equal to
2135:The Stern–Brocot tree forms an infinite
18:
2952:
2893:, in which the children of each number
2426:is approximated by any rational number
2081:of the tree in finitely many steps (in
16:Ordered binary tree of rational numbers
2247:is found, repeat the following steps:
85:
2212:The path from the root 1 to a number
77:
7:
2529:consists of all values at the first
1312:. For instance, the rational number
3037:Introduction to Programming in Java
2058:(the right child) and =
1958:One of these children is less than
2935:Minkowski's question-mark function
2198:and closest to it in the tree (or
2172:and closest to it in the tree (or
14:
3001:Journal of Functional Programming
2367:; terminate the search algorithm.
2143:is defined by the open interval (
2995:Gibbons, Jeremy; Lester, David;
3148:Modified Stern-Brocot Sequences
2889:produces a different tree, the
2858:has a smaller denominator than
2183:has no smaller ancestor) while
2018:is odd, and the right child if
1305:{\displaystyle {\tfrac {1}{1}}}
3213:The Stern–Brocot or Farey Tree
2544:. The Farey sequence of order
1942:
1872:
1858:{\displaystyle \displaystyle }
1851:
1787:
1766:
1696:
1690:
1632:
1518:
1500:
1494:
1470:
1447:
1423:
1267:
1203:
1133:
1063:
1057:
987:
893:
835:
1:
3178:, Feature Column from the AMS
3115:American Mathematical Society
2240:to 0/1 and 1/0, respectively.
602:A tree of continued fractions
2444:best rational approximations
513:and the right descendent is
2478:Relation to Farey sequences
3322:
2131:Mediants and binary search
3014:10.1017/S0956796806005880
2839:{\displaystyle p'q-pq'=1}
2340:is in the open interval (
2309:is in the open interval (
2209:has no larger ancestor).
3146:Aiylam, Dhroova (2013),
2887:bit-reversal permutation
45:infinite complete binary
3306:Trees (data structures)
2373:The sequence of values
2359:In the remaining case,
2226:binary search algorithm
2116:. The numbers at depth
1599:Conversely each number
115:provides a sequence of
2872:lowest common ancestor
2840:
2789:
2733:
2693:
2657:
2274:; compute the mediant
2232:Initialize two values
2032:
2012:
1992:
1972:
1952:
1859:
1773:
1613:
1591:
1457:
1306:
1277:
1190:
1170:
1143:
974:
947:
920:
900:
620:
592:
507:
422:
353:
284:
215:
32:
3035:Sedgewick and Wayne,
2841:
2790:
2734:
2673:
2658:
2556:Additional properties
2515:Stern–Brocot sequence
2228:proceeds as follows:
2168:that is smaller than
2033:
2013:
1993:
1973:
1953:
1860:
1774:
1614:
1592:
1458:
1307:
1278:
1191:
1171:
1144:
975:
973:{\displaystyle a_{i}}
948:
946:{\displaystyle a_{0}}
921:
901:
621:
593:
508:
423:
354:
285:
216:
22:
3225:Wildberger, Norman,
3184:Bogomolny, Alexander
3068:Revue Chronométrique
2973:Concrete mathematics
2901:are the two numbers
2802:
2747:
2670:
2564:
2194:that is larger than
2022:
2002:
1982:
1962:
1869:
1783:
1623:
1603:
1467:
1326:
1287:
1200:
1180:
1154:
984:
957:
930:
910:
630:
610:
517:
432:
363:
294:
225:
156:
133:breadth first search
3301:Continued fractions
3242:"Stern–Brocot Tree"
3166:2013arXiv1301.6807A
2874:of any two numbers
2205: = +∞ if
2190:is the ancestor of
2164:is the ancestor of
1772:{\displaystyle q==}
1547:
1535:
1391:
1379:
1365:
1353:
1169:{\displaystyle q=1}
794:
782:
768:
756:
735:
723:
702:
690:
669:
657:
105:continued fractions
3274:Amazing Graphs III
3265:Infinite fractions
3238:Weisstein, Eric W.
2836:
2785:
2729:
2653:
2465:is the mediant of
2457:is the mediant of
2179: = 0 if
2137:binary search tree
2068:(the left child).
2028:
2008:
1988:
1968:
1948:
1855:
1854:
1769:
1609:
1587:
1567:
1542:
1453:
1416:
1411:
1386:
1360:
1302:
1300:
1273:
1186:
1166:
1142:{\displaystyle =,}
1139:
970:
943:
916:
896:
828:
823:
818:
813:
808:
789:
763:
730:
697:
664:
616:
588:
581:
566:
535:
503:
496:
481:
450:
418:
411:
396:
381:
349:
342:
327:
312:
280:
273:
258:
243:
211:
204:
189:
174:
82:Achille Brocot
33:
3255:Stern–Brocot tree
3189:Stern Brocot-Tree
3124:978-0-8218-4480-9
2961:Graham, Ronald L.
2782:
2759:
2721:
2650:
2617:
2590:
2112:are greater than
2031:{\displaystyle k}
2011:{\displaystyle k}
1991:{\displaystyle q}
1971:{\displaystyle q}
1951:{\displaystyle .}
1612:{\displaystyle q}
1582:
1569:
1564:
1546:
1534:
1418:
1413:
1408:
1390:
1378:
1364:
1352:
1337:
1299:
1276:{\displaystyle .}
1189:{\displaystyle q}
919:{\displaystyle k}
830:
825:
820:
815:
810:
793:
781:
767:
755:
734:
722:
701:
689:
668:
656:
619:{\displaystyle q}
580:
565:
534:
495:
480:
449:
410:
395:
380:
341:
326:
311:
272:
257:
242:
203:
188:
173:
100:near that value.
41:Stern–Brocot tree
3313:
3284:
3251:
3250:
3231:
3220:
3208:Sloane, N. J. A.
3202:
3201:
3200:
3179:
3168:
3159:
3135:
3104:
3087:Stern, Moritz A.
3075:
3053:
3050:
3044:
3033:
3027:
3025:
3016:
2992:
2986:
2985:
2965:Knuth, Donald E.
2957:
2941:Calkin–Wilf tree
2891:Calkin–Wilf tree
2845:
2843:
2842:
2837:
2829:
2812:
2794:
2792:
2791:
2786:
2784:
2783:
2781:
2773:
2765:
2760:
2752:
2738:
2736:
2735:
2730:
2722:
2720:
2719:
2718:
2709:
2708:
2695:
2692:
2687:
2662:
2660:
2659:
2654:
2652:
2651:
2649:
2648:
2639:
2638:
2629:
2618:
2616:
2615:
2606:
2605:
2596:
2591:
2589:
2588:
2579:
2578:
2569:
2407:. The parent of
2332:is greater than
2126:
2099:
2080:
2079:
2075:
2067:
2066:
2062:
2057:
2056:
2052:
2047:
2046:
2042:
2037:
2035:
2034:
2029:
2017:
2015:
2014:
2009:
1997:
1995:
1994:
1989:
1977:
1975:
1974:
1969:
1957:
1955:
1954:
1949:
1929:
1928:
1910:
1909:
1897:
1896:
1884:
1883:
1864:
1862:
1861:
1856:
1844:
1843:
1825:
1824:
1812:
1811:
1799:
1798:
1778:
1776:
1775:
1770:
1753:
1752:
1734:
1733:
1721:
1720:
1708:
1707:
1689:
1688:
1670:
1669:
1657:
1656:
1644:
1643:
1618:
1616:
1615:
1610:
1596:
1594:
1593:
1588:
1583:
1575:
1570:
1568:
1566:
1565:
1557:
1543:
1541:
1531:
1462:
1460:
1459:
1454:
1419:
1417:
1415:
1414:
1412:
1410:
1409:
1401:
1387:
1385:
1375:
1361:
1359:
1349:
1338:
1330:
1321:
1320:
1316:
1311:
1309:
1308:
1303:
1301:
1292:
1282:
1280:
1279:
1274:
1260:
1259:
1241:
1240:
1228:
1227:
1215:
1214:
1195:
1193:
1192:
1187:
1175:
1173:
1172:
1167:
1148:
1146:
1145:
1140:
1126:
1125:
1101:
1100:
1088:
1087:
1075:
1074:
1050:
1049:
1025:
1024:
1012:
1011:
999:
998:
979:
977:
976:
971:
969:
968:
952:
950:
949:
944:
942:
941:
925:
923:
922:
917:
905:
903:
902:
897:
892:
891:
873:
872:
860:
859:
847:
846:
831:
829:
827:
826:
824:
822:
821:
819:
817:
816:
814:
812:
811:
809:
807:
806:
805:
790:
788:
778:
764:
762:
752:
747:
746:
731:
729:
719:
714:
713:
698:
696:
686:
681:
680:
665:
663:
653:
648:
647:
625:
623:
622:
617:
597:
595:
594:
589:
587:
583:
582:
573:
567:
564:
553:
542:
536:
527:
512:
510:
509:
504:
502:
498:
497:
488:
482:
479:
468:
457:
451:
442:
427:
425:
424:
419:
417:
413:
412:
403:
397:
388:
382:
373:
358:
356:
355:
350:
348:
344:
343:
334:
328:
319:
313:
304:
289:
287:
286:
281:
279:
275:
274:
265:
259:
250:
244:
235:
220:
218:
217:
212:
210:
206:
205:
196:
190:
181:
175:
166:
74:Moritz Stern
63:rational numbers
3321:
3320:
3316:
3315:
3314:
3312:
3311:
3310:
3291:
3290:
3236:
3235:
3224:
3206:
3198:
3196:
3182:
3172:Austin, David,
3171:
3145:
3142:
3125:
3108:
3085:
3065:
3062:
3057:
3056:
3051:
3047:
3034:
3030:
2994:
2993:
2989:
2983:
2969:Patashnik, Oren
2959:
2958:
2954:
2949:
2931:
2822:
2805:
2800:
2799:
2774:
2766:
2745:
2744:
2710:
2700:
2699:
2668:
2667:
2640:
2630:
2607:
2597:
2580:
2570:
2562:
2561:
2558:
2480:
2401:
2394:
2203:
2188:
2177:
2162:
2155:
2148:
2133:
2121:
2097:
2088:
2082:
2077:
2073:
2072:
2064:
2060:
2059:
2054:
2050:
2049:
2044:
2040:
2039:
2020:
2019:
2000:
1999:
1980:
1979:
1960:
1959:
1920:
1901:
1888:
1875:
1867:
1866:
1835:
1816:
1803:
1790:
1781:
1780:
1744:
1725:
1712:
1699:
1680:
1661:
1648:
1635:
1621:
1620:
1601:
1600:
1544:
1532:
1465:
1464:
1388:
1376:
1362:
1350:
1324:
1323:
1318:
1314:
1313:
1285:
1284:
1251:
1232:
1219:
1206:
1198:
1197:
1178:
1177:
1152:
1151:
1111:
1092:
1079:
1066:
1035:
1016:
1003:
990:
982:
981:
960:
955:
954:
933:
928:
927:
908:
907:
883:
864:
851:
838:
797:
791:
779:
765:
753:
738:
732:
720:
705:
699:
687:
672:
666:
654:
639:
628:
627:
608:
607:
604:
554:
543:
524:
520:
515:
514:
469:
458:
439:
435:
430:
429:
370:
366:
361:
360:
301:
297:
292:
291:
232:
228:
223:
222:
163:
159:
154:
153:
149:
147:Generating rule
137:Farey sequences
17:
12:
11:
5:
3319:
3317:
3309:
3308:
3303:
3293:
3292:
3289:
3288:
3280:
3271:
3262:
3252:
3233:
3222:
3204:
3180:
3169:
3141:
3140:External links
3138:
3137:
3136:
3123:
3106:
3083:
3077:
3061:
3058:
3055:
3054:
3045:
3028:
3007:(3): 281–291,
2987:
2981:
2951:
2950:
2948:
2945:
2944:
2943:
2938:
2930:
2927:
2852:Cartesian tree
2848:
2847:
2835:
2832:
2828:
2825:
2821:
2818:
2815:
2811:
2808:
2780:
2777:
2772:
2769:
2763:
2758:
2755:
2741:
2740:
2728:
2725:
2717:
2713:
2707:
2703:
2698:
2691:
2686:
2683:
2680:
2676:
2647:
2643:
2637:
2633:
2627:
2624:
2621:
2614:
2610:
2604:
2600:
2594:
2587:
2583:
2577:
2573:
2557:
2554:
2484:Farey sequence
2479:
2476:
2420:floating-point
2399:
2392:
2371:
2370:
2369:
2368:
2357:
2326:
2295:
2278: = (
2241:
2201:
2186:
2175:
2160:
2153:
2146:
2132:
2129:
2104:are less than
2093:
2086:
2027:
2007:
1987:
1967:
1947:
1944:
1941:
1938:
1935:
1932:
1927:
1923:
1919:
1916:
1913:
1908:
1904:
1900:
1895:
1891:
1887:
1882:
1878:
1874:
1853:
1850:
1847:
1842:
1838:
1834:
1831:
1828:
1823:
1819:
1815:
1810:
1806:
1802:
1797:
1793:
1789:
1768:
1765:
1762:
1759:
1756:
1751:
1747:
1743:
1740:
1737:
1732:
1728:
1724:
1719:
1715:
1711:
1706:
1702:
1698:
1695:
1692:
1687:
1683:
1679:
1676:
1673:
1668:
1664:
1660:
1655:
1651:
1647:
1642:
1638:
1634:
1631:
1628:
1608:
1586:
1581:
1578:
1573:
1563:
1560:
1555:
1552:
1540:
1529:
1526:
1523:
1520:
1517:
1514:
1511:
1508:
1505:
1502:
1499:
1496:
1493:
1490:
1487:
1484:
1481:
1478:
1475:
1472:
1452:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1422:
1407:
1404:
1399:
1396:
1384:
1373:
1370:
1358:
1347:
1344:
1341:
1336:
1333:
1298:
1295:
1272:
1269:
1266:
1263:
1258:
1254:
1250:
1247:
1244:
1239:
1235:
1231:
1226:
1222:
1218:
1213:
1209:
1205:
1185:
1165:
1162:
1159:
1138:
1135:
1132:
1129:
1124:
1121:
1118:
1114:
1110:
1107:
1104:
1099:
1095:
1091:
1086:
1082:
1078:
1073:
1069:
1065:
1062:
1059:
1056:
1053:
1048:
1045:
1042:
1038:
1034:
1031:
1028:
1023:
1019:
1015:
1010:
1006:
1002:
997:
993:
989:
967:
963:
940:
936:
915:
895:
890:
886:
882:
879:
876:
871:
867:
863:
858:
854:
850:
845:
841:
837:
834:
804:
800:
787:
776:
773:
761:
750:
745:
741:
728:
717:
712:
708:
695:
684:
679:
675:
662:
651:
646:
642:
638:
635:
615:
603:
600:
586:
579:
576:
570:
563:
560:
557:
552:
549:
546:
539:
533:
530:
523:
501:
494:
491:
485:
478:
475:
472:
467:
464:
461:
454:
448:
445:
438:
416:
409:
406:
400:
394:
391:
385:
379:
376:
369:
347:
340:
337:
331:
325:
322:
316:
310:
307:
300:
278:
271:
268:
262:
256:
253:
247:
241:
238:
231:
209:
202:
199:
193:
187:
184:
178:
172:
169:
162:
148:
145:
117:approximations
98:smooth numbers
15:
13:
10:
9:
6:
4:
3:
2:
3318:
3307:
3304:
3302:
3299:
3298:
3296:
3287:
3281:
3279:
3275:
3272:
3270:
3266:
3263:
3260:
3256:
3253:
3249:
3248:
3243:
3239:
3234:
3230:
3229:
3223:
3219:
3215:
3214:
3209:
3205:
3195:
3191:
3190:
3185:
3181:
3177:
3176:
3170:
3167:
3163:
3158:
3153:
3149:
3144:
3143:
3139:
3134:
3130:
3126:
3120:
3116:
3112:
3107:
3102:
3098:
3097:
3092:
3088:
3084:
3082:
3078:
3073:
3069:
3064:
3063:
3059:
3049:
3046:
3042:
3038:
3032:
3029:
3024:
3020:
3015:
3010:
3006:
3002:
2998:
2997:Bird, Richard
2991:
2988:
2984:
2982:0-201-55802-5
2978:
2974:
2970:
2966:
2962:
2956:
2953:
2946:
2942:
2939:
2936:
2933:
2932:
2928:
2926:
2924:
2920:
2917: +
2916:
2912:
2909: +
2908:
2904:
2900:
2896:
2892:
2888:
2883:
2881:
2877:
2873:
2869:
2865:
2861:
2857:
2853:
2833:
2830:
2826:
2823:
2819:
2816:
2813:
2809:
2806:
2798:
2797:
2796:
2778:
2775:
2770:
2767:
2761:
2756:
2753:
2743:Moreover, if
2726:
2723:
2715:
2711:
2705:
2701:
2696:
2689:
2684:
2681:
2678:
2674:
2666:
2665:
2664:
2645:
2641:
2635:
2631:
2625:
2622:
2619:
2612:
2608:
2602:
2598:
2592:
2585:
2581:
2575:
2571:
2555:
2553:
2551:
2547:
2543:
2539:
2534:
2532:
2528:
2524:
2520:
2516:
2511:
2509:
2505:
2501:
2497:
2493:
2489:
2485:
2477:
2475:
2472:
2468:
2464:
2460:
2456:
2451:
2449:
2445:
2441:
2437:
2433:
2429:
2425:
2421:
2416:
2414:
2410:
2406:
2402:
2395:
2388:
2384:
2380:
2376:
2366:
2362:
2358:
2356:and continue.
2355:
2351:
2347:
2343:
2339:
2335:
2331:
2327:
2325:and continue.
2324:
2320:
2316:
2312:
2308:
2304:
2301:is less than
2300:
2296:
2293:
2290: +
2289:
2285:
2282: +
2281:
2277:
2273:
2269:
2265:
2261:
2257:
2253:
2249:
2248:
2246:
2242:
2239:
2235:
2231:
2230:
2229:
2227:
2223:
2219:
2218:binary search
2215:
2210:
2208:
2204:
2197:
2193:
2189:
2182:
2178:
2171:
2167:
2163:
2156:
2149:
2142:
2138:
2130:
2128:
2124:
2119:
2115:
2111:
2107:
2103:
2096:
2092:
2085:
2069:
2025:
2005:
1985:
1965:
1945:
1939:
1936:
1933:
1930:
1925:
1921:
1917:
1914:
1911:
1906:
1902:
1898:
1893:
1889:
1885:
1880:
1876:
1848:
1845:
1840:
1836:
1832:
1829:
1826:
1821:
1817:
1813:
1808:
1804:
1800:
1795:
1791:
1763:
1760:
1757:
1754:
1749:
1745:
1741:
1738:
1735:
1730:
1726:
1722:
1717:
1713:
1709:
1704:
1700:
1693:
1685:
1681:
1677:
1674:
1671:
1666:
1662:
1658:
1653:
1649:
1645:
1640:
1636:
1629:
1626:
1606:
1597:
1584:
1579:
1576:
1571:
1561:
1558:
1553:
1550:
1538:
1527:
1524:
1521:
1515:
1512:
1509:
1506:
1503:
1497:
1491:
1488:
1485:
1482:
1479:
1476:
1473:
1450:
1444:
1441:
1438:
1435:
1432:
1429:
1426:
1420:
1405:
1402:
1397:
1394:
1382:
1371:
1368:
1356:
1345:
1342:
1339:
1334:
1331:
1296:
1293:
1270:
1264:
1261:
1256:
1252:
1248:
1245:
1242:
1237:
1233:
1229:
1224:
1220:
1216:
1211:
1207:
1183:
1176:, the number
1163:
1160:
1157:
1136:
1130:
1127:
1122:
1119:
1116:
1112:
1108:
1105:
1102:
1097:
1093:
1089:
1084:
1080:
1076:
1071:
1067:
1060:
1054:
1051:
1046:
1043:
1040:
1036:
1032:
1029:
1026:
1021:
1017:
1013:
1008:
1004:
1000:
995:
991:
965:
961:
938:
934:
913:
888:
884:
880:
877:
874:
869:
865:
861:
856:
852:
848:
843:
839:
832:
802:
798:
785:
774:
771:
759:
748:
743:
739:
726:
715:
710:
706:
693:
682:
677:
673:
660:
649:
644:
640:
636:
633:
613:
601:
599:
584:
577:
574:
568:
561:
558:
555:
550:
547:
544:
537:
531:
528:
521:
499:
492:
489:
483:
476:
473:
470:
465:
462:
459:
452:
446:
443:
436:
414:
407:
404:
398:
392:
389:
383:
377:
374:
367:
345:
338:
335:
329:
323:
320:
314:
308:
305:
298:
276:
269:
266:
260:
254:
251:
245:
239:
236:
229:
207:
200:
197:
191:
185:
182:
176:
170:
167:
160:
146:
144:
142:
138:
134:
130:
126:
123:with smaller
122:
118:
114:
110:
106:
101:
99:
95:
91:
87:
83:
79:
75:
70:
68:
64:
61:
57:
53:
50:in which the
49:
46:
42:
38:
37:number theory
30:
26:
21:
3245:
3227:
3212:
3197:, retrieved
3194:cut-the-knot
3188:
3174:
3147:
3110:
3100:
3094:
3071:
3067:
3048:
3036:
3031:
3004:
3000:
2990:
2972:
2955:
2922:
2918:
2914:
2910:
2906:
2902:
2898:
2894:
2884:
2879:
2875:
2867:
2863:
2859:
2855:
2849:
2742:
2559:
2552:is reached.
2549:
2545:
2541:
2537:
2535:
2530:
2526:
2522:
2518:
2514:
2512:
2507:
2503:
2499:
2495:
2491:
2487:
2481:
2470:
2466:
2462:
2458:
2454:
2452:
2447:
2439:
2435:
2431:
2427:
2423:
2417:
2412:
2408:
2404:
2397:
2390:
2386:
2382:
2378:
2374:
2372:
2364:
2360:
2353:
2349:
2345:
2341:
2337:
2333:
2329:
2322:
2318:
2314:
2310:
2306:
2302:
2298:
2291:
2287:
2283:
2279:
2275:
2271:
2267:
2263:
2259:
2255:
2251:
2244:
2237:
2233:
2213:
2211:
2206:
2199:
2195:
2191:
2184:
2180:
2173:
2169:
2165:
2158:
2151:
2144:
2140:
2134:
2122:
2117:
2113:
2109:
2105:
2101:
2094:
2090:
2083:
2070:
1598:
605:
150:
140:
128:
125:denominators
120:
112:
102:
71:
40:
34:
31:= 1, 2, 3, 4
28:
24:
3278:Numberphile
3269:Numberphile
2348:); replace
2317:); replace
67:search tree
56:one-for-one
54:correspond
3295:Categories
3259:PlanetMath
3199:2008-09-03
3133:1161.68043
3060:References
141:Farey tree
94:gear ratio
90:clockmaker
3247:MathWorld
3157:1301.6807
3103:: 193–220
3074:: 186–194
2817:−
2675:∑
2623:…
2486:of order
1931:−
1915:…
1830:…
1755:−
1739:…
1675:…
1262:−
1246:…
1120:−
1106:…
1044:−
1030:…
878:…
772:⋱
3089:(1858),
3023:14237968
2971:(1994),
2929:See also
2827:′
2810:′
2779:′
2771:′
2222:mediants
2157:) where
2089:+ ... +
109:mediants
60:positive
52:vertices
3162:Bibcode
2913:) and (
2862:(or if
2336:, then
2305:, then
2076:⁄
2063:⁄
2053:⁄
2043:⁄
1317:⁄
84: (
76: (
58:to the
3131:
3121:
3021:
2979:
2243:Until
906:where
80:) and
43:is an
39:, the
3152:arXiv
3019:S2CID
2947:Notes
127:than
3283:OEIS
3119:ISBN
3041:here
2977:ISBN
2878:and
2762:<
2482:The
2262:and
2250:Let
2236:and
926:and
290:and
86:1861
78:1858
48:tree
27:for
3257:at
3129:Zbl
3009:doi
2560:If
2446:to
2352:by
2328:If
2321:by
2297:If
2286:)/(
2125:+ 1
2098:− 1
428:is
119:to
107:or
35:In
3297::
3276:,
3267:,
3244:,
3240:,
3216:,
3210:,
3192:,
3186:,
3160:,
3150:,
3127:,
3117:,
3101:55
3099:,
3093:,
3070:,
3017:,
3005:16
3003:,
2967:;
2963:;
2921:)/
2905:/(
2450:.
2415:.
2363:=
2294:).
2266:=
2254:=
2127:.
2065:16
2061:23
2055:11
2051:16
2041:13
1577:13
1335:16
1332:23
1319:16
1315:23
598:.
143:.
69:.
3261:.
3232:.
3221:.
3203:.
3164::
3154::
3105:.
3076:.
3072:3
3043:.
3026:.
3011::
2923:b
2919:b
2915:a
2911:b
2907:a
2903:a
2899:b
2897:/
2895:a
2880:r
2876:q
2868:q
2864:q
2860:q
2856:q
2846:.
2834:1
2831:=
2824:q
2820:p
2814:q
2807:p
2776:q
2768:p
2757:q
2754:p
2739:.
2727:1
2724:=
2716:k
2712:q
2706:k
2702:p
2697:1
2690:n
2685:1
2682:=
2679:k
2646:n
2642:q
2636:n
2632:p
2626:,
2620:,
2613:2
2609:q
2603:2
2599:p
2593:,
2586:1
2582:q
2576:1
2572:p
2550:n
2546:n
2542:n
2538:n
2531:i
2527:i
2523:i
2519:i
2508:n
2504:n
2500:n
2496:n
2492:n
2488:n
2471:q
2467:q
2463:q
2459:q
2455:q
2448:x
2440:b
2436:x
2432:b
2430:/
2428:a
2424:x
2413:q
2409:q
2405:M
2400:M
2398:H
2396:,
2393:M
2391:L
2387:H
2385:,
2383:L
2379:q
2375:M
2365:M
2361:q
2354:M
2350:H
2346:M
2344:,
2342:L
2338:q
2334:q
2330:M
2323:M
2319:L
2315:H
2313:,
2311:M
2307:q
2303:q
2299:M
2292:d
2288:b
2284:c
2280:a
2276:M
2272:d
2270:/
2268:c
2264:H
2260:b
2258:/
2256:a
2252:L
2245:q
2238:H
2234:L
2214:q
2207:q
2202:q
2200:H
2196:q
2192:q
2187:q
2185:H
2181:q
2176:q
2174:L
2170:q
2166:q
2161:q
2159:L
2154:q
2152:H
2150:,
2147:q
2145:L
2141:q
2123:d
2118:d
2114:q
2110:q
2106:q
2102:q
2095:k
2091:a
2087:0
2084:a
2078:1
2074:1
2045:9
2026:k
2006:k
1986:q
1966:q
1946:.
1943:]
1940:2
1937:,
1934:1
1926:k
1922:a
1918:,
1912:,
1907:2
1903:a
1899:,
1894:1
1890:a
1886:;
1881:0
1877:a
1873:[
1852:]
1849:1
1846:+
1841:k
1837:a
1833:,
1827:,
1822:2
1818:a
1814:,
1809:1
1805:a
1801:;
1796:0
1792:a
1788:[
1767:]
1764:1
1761:,
1758:1
1750:k
1746:a
1742:,
1736:,
1731:2
1727:a
1723:,
1718:1
1714:a
1710:;
1705:0
1701:a
1697:[
1694:=
1691:]
1686:k
1682:a
1678:,
1672:,
1667:2
1663:a
1659:,
1654:1
1650:a
1646:;
1641:0
1637:a
1633:[
1630:=
1627:q
1607:q
1585:.
1580:9
1572:=
1562:4
1559:1
1554:+
1551:2
1539:1
1528:+
1525:1
1522:=
1519:]
1516:4
1513:,
1510:2
1507:;
1504:1
1501:[
1498:=
1495:]
1492:1
1489:,
1486:3
1483:,
1480:2
1477:;
1474:1
1471:[
1451:,
1448:]
1445:2
1442:,
1439:3
1436:,
1433:2
1430:;
1427:1
1424:[
1421:=
1406:2
1403:1
1398:+
1395:3
1383:1
1372:+
1369:2
1357:1
1346:+
1343:1
1340:=
1297:1
1294:1
1271:.
1268:]
1265:1
1257:k
1253:a
1249:,
1243:,
1238:2
1234:a
1230:,
1225:1
1221:a
1217:;
1212:0
1208:a
1204:[
1184:q
1164:1
1161:=
1158:q
1137:,
1134:]
1131:1
1128:+
1123:1
1117:k
1113:a
1109:,
1103:,
1098:2
1094:a
1090:,
1085:1
1081:a
1077:;
1072:0
1068:a
1064:[
1061:=
1058:]
1055:1
1052:,
1047:1
1041:k
1037:a
1033:,
1027:,
1022:2
1018:a
1014:,
1009:1
1005:a
1001:;
996:0
992:a
988:[
966:i
962:a
939:0
935:a
914:k
894:]
889:k
885:a
881:,
875:,
870:2
866:a
862:,
857:1
853:a
849:;
844:0
840:a
836:[
833:=
803:k
799:a
786:1
775:+
760:1
749:+
744:3
740:a
727:1
716:+
711:2
707:a
694:1
683:+
678:1
674:a
661:1
650:+
645:0
641:a
637:=
634:q
614:q
585:)
578:f
575:e
569:,
562:f
559:+
556:d
551:e
548:+
545:c
538:,
532:d
529:c
522:(
500:)
493:d
490:c
484:,
477:d
474:+
471:b
466:c
463:+
460:a
453:,
447:b
444:a
437:(
415:)
408:f
405:e
399:,
393:d
390:c
384:,
378:b
375:a
368:(
346:)
339:0
336:1
330:,
324:1
321:2
315:,
309:1
306:1
299:(
277:)
270:1
267:1
261:,
255:2
252:1
246:,
240:1
237:0
230:(
208:)
201:0
198:1
192:,
186:1
183:1
177:,
171:1
168:0
161:(
129:q
121:q
113:q
29:i
25:i
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
