For a denominator bound \(B\), a rational \(r/s\) with \(s \le B\) is called a best approximation to a real number \(x\) if it minimizes \(|x-r/s|\) among all rationals whose denominators do not exceed \(B\). A rational number \(x\) is called ambiguous if there exists at least one bound \(B\) for which two distinct rationals are tied as best approximations.
The problem asks for the number of reduced rationals \(x=p/q\) such that \(0 \lt x \lt 1/100\), \(q \le 10^8\), and \(x\) is ambiguous. The successful strategy is not to enumerate all fractions with denominator up to \(10^8\), but to characterize exactly which rationals can be ambiguous and count only those.
The central objects are neighboring Farey fractions. Every ambiguous rational in the target range comes from one Farey gap, and the denominator condition on \(x\) becomes a simple product condition on the two endpoint denominators.
Assume a denominator bound \(B\) gives two distinct best approximations \(a/b\) and \(c/d\) with \(a/b \lt x \lt c/d\) and \(b,d \le B\). There cannot be any reduced fraction \(u/v\) with \(v \le B\) strictly between them, because such a fraction would be closer to \(x\) than at least one endpoint. Therefore \(a/b\) and \(c/d\) must be adjacent in the Farey sequence of order \(B\), which is equivalent to
$$bc-ad=1.$$
Since the two errors are equal, \(x\) must be exactly the midpoint of the interval:
$$x=\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right)=\frac{ad+bc}{2bd}.$$
The converse is equally important. If \(a/b \lt c/d\) are Farey neighbors and \(B\) satisfies \(\max(b,d)\le B \lt b+d\), then no reduced fraction with denominator at most \(B\) lies between them. At the midpoint, both endpoints are therefore equally close and both are best approximations. So ambiguous rationals are exactly the midpoints of neighboring Farey fractions.
The midpoint formula does not simplify unexpectedly. From \(bc-ad=1\), the products \(bc\) and \(ad\) have opposite parity, so \(ad+bc\) is odd. Also,
$$\gcd(ad+bc,b)=\gcd(ad,b)=1,\qquad \gcd(ad+bc,d)=\gcd(bc,d)=1.$$
Hence \(\gcd(ad+bc,2bd)=1\), and the midpoint is already in lowest terms with denominator
$$q=2bd.$$
This is why the denominator limit \(q \le Q\) becomes
$$2bd \le Q \qquad\Longleftrightarrow\qquad bd \le \left\lfloor\frac{Q}{2}\right\rfloor,$$
with \(Q=10^8\). In other words, the whole denominator constraint is encoded by the product of the two Farey-neighbor denominators.
The Stern-Brocot tree starts from the neighboring pair \(0/1 \lt 1/1\). A node stores one neighboring interval \((a/b,c/d)\), and its children are obtained from the mediant
$$\frac{a+c}{b+d}:$$
$$\left(\frac{a}{b},\frac{c}{d}\right)\to\left(\frac{a}{b},\frac{a+c}{b+d}\right),\qquad \left(\frac{a+c}{b+d},\frac{c}{d}\right).$$
The determinant invariant is preserved:
$$b(a+c)-a(b+d)=bc-ad=1,\qquad (b+d)c-(a+c)d=bc-ad=1.$$
So every visited node is again a pair of Farey neighbors. Moreover, every positive reduced rational appears in exactly one interval of the Stern-Brocot tree, so every ambiguous midpoint has one unique node that generates it. This gives a one-to-one search space for counting.
For a current node \((a/b,c/d)\), the midpoint belongs to the answer exactly when
$$\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right) \lt \frac{1}{100},$$
which the implementations rewrite as the integer inequality
$$ (ad+bc)\cdot 100 \lt 2bd. $$
Two monotonicity properties justify pruning whole subtrees.
If \(bd \gt Q/2\), then the current midpoint denominator already exceeds \(Q\), and both children have strictly larger products, namely \(b(b+d)\) and \((b+d)d\). No descendant can come back under the limit.
If the left endpoint already satisfies \(a/b \ge 1/100\), then the entire interval lies at or above the threshold, and every descendant remains inside that interval. By contrast, a midpoint that is currently too large does not allow pruning by itself, because descendants closer to the left edge may still drop below \(1/100\).
Consider the neighboring fractions
$$\frac{1}{101} \lt \frac{2}{201},\qquad 101\cdot 2 - 1\cdot 201 = 1.$$
Their midpoint is
$$x=\frac{1}{2}\left(\frac{1}{101}+\frac{2}{201}\right)=\frac{403}{40602}\approx 0.0099256,$$
so it lies below \(1/100\). The reduced denominator is exactly
$$q=2\cdot 101\cdot 201=40602.$$
Because \(1/101\) and \(2/201\) are Farey neighbors, no reduced fraction with denominator below \(101+201=302\) lies between them. Therefore any denominator bound \(B\) with \(201 \le B \lt 302\) makes these two fractions equally good best approximations, so \(403/40602\) is ambiguous. This is precisely the kind of midpoint counted by the algorithm.
The C++, Python, and Java implementations represent one Stern-Brocot interval by four integers \(a,b,c,d\). They avoid floating-point arithmetic completely: the denominator test uses the product bound \(bd \le Q/2\), the threshold pruning compares \(a/b\) against \(1/100\) by cross-multiplication, and the midpoint test checks \((ad+bc)\cdot 100 \lt 2bd\).
The main search is an explicit depth-first traversal with a stack. When a node survives the pruning tests, the implementation forms the mediant \((a+c)/(b+d)\), pushes the two child intervals, and increments the answer if the midpoint itself satisfies the threshold. Because each Stern-Brocot node corresponds to exactly one neighboring Farey pair, each increment counts exactly one ambiguous rational.
The C++ and Java implementations add a parallel front end for the largest input. They first expand the tree breadth-first until they have a moderate frontier of seed intervals, count the ambiguous midpoints seen during that prefix expansion, and then distribute the remaining subtrees across worker threads. The Python implementation performs the same traversal and the same exact tests in a single serial pass.
Let \(V\) be the number of Stern-Brocot intervals that are actually popped from the stack before pruning stops them. The serial algorithm runs in \(O(V)\) time, because each visited node performs only a constant amount of integer arithmetic and either terminates immediately or creates two children.
Memory usage is \(O(H)\) for the explicit stack, where \(H\) is the maximum search depth reached before pruning. In the parallel versions there is additional storage for the seed frontier, but total work remains linear in the number of visited nodes. The essential gain is structural: the search follows only Farey gaps whose midpoint denominator can still fit under \(10^8\) and whose interval has not moved entirely past \(1/100\), instead of scanning a gigantic set of unrelated rationals.
Zu einer Nennergrenze \(B\) heißt ein Bruch \(r/s\) mit \(s \le B\) eine beste Approximation einer reellen Zahl \(x\), wenn \(|x-r/s|\) unter allen Brüchen mit Nenner höchstens \(B\) minimal ist. Eine rationale Zahl \(x\) heißt mehrdeutig, wenn es mindestens eine Grenze \(B\) gibt, für die zwei verschiedene Brüche gleichzeitig beste Approximationen sind.
Gesucht ist die Anzahl der vollständig gekürzten rationalen Zahlen \(x=p/q\) mit \(0 \lt x \lt 1/100\), \(q \le 10^8\) und dieser Mehrdeutigkeitseigenschaft. Die Lösung zählt nicht blind alle Brüche bis \(10^8\), sondern beschreibt zuerst exakt, welche rationalen Zahlen überhaupt mehrdeutig sein können.
Die entscheidenden Objekte sind benachbarte Farey-Brüche. Jede gesuchte rationale Zahl entsteht als Mittelpunkt genau einer Farey-Lücke, und die Nennerbedingung für \(x\) wird dadurch zu einer einfachen Produktbedingung an den beiden Randbrüchen.
Angenommen, für eine Nennergrenze \(B\) gibt es zwei verschiedene beste Approximationen \(a/b\) und \(c/d\) mit \(a/b \lt x \lt c/d\) sowie \(b,d \le B\). Dann darf kein vollständig gekürzter Bruch \(u/v\) mit \(v \le B\) strikt dazwischen liegen, denn dieser wäre zu \(x\) näher als mindestens einer der beiden Randpunkte. Also müssen \(a/b\) und \(c/d\) in der Farey-Folge der Ordnung \(B\) benachbart sein, also
$$bc-ad=1.$$
Da beide Fehler gleich groß sind, muss \(x\) genau der Mittelpunkt des Intervalls sein:
$$x=\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right)=\frac{ad+bc}{2bd}.$$
Umgekehrt gilt: Sind \(a/b \lt c/d\) Farey-Nachbarn und erfüllt \(B\) die Schranke \(\max(b,d)\le B \lt b+d\), dann liegt kein gekürzter Bruch mit Nenner höchstens \(B\) zwischen ihnen. Im Mittelpunkt sind daher beide Randbrüche gleich nah an \(x\) und beide beste Approximationen. Genau die Mittelpunkte benachbarter Farey-Brüche sind also die mehrdeutigen rationalen Zahlen.
Die Mittelpunktformel vereinfacht sich nicht weiter. Aus \(bc-ad=1\) folgt, dass \(bc\) und \(ad\) verschiedene Parität haben; daher ist \(ad+bc\) ungerade. Außerdem gilt
$$\gcd(ad+bc,b)=\gcd(ad,b)=1,\qquad \gcd(ad+bc,d)=\gcd(bc,d)=1.$$
Damit ist \(\gcd(ad+bc,2bd)=1\), und der Mittelpunkt liegt bereits vollständig gekürzt mit Nenner
$$q=2bd$$
vor. Die Bedingung \(q \le Q\) wird deshalb zu
$$2bd \le Q \qquad\Longleftrightarrow\qquad bd \le \left\lfloor\frac{Q}{2}\right\rfloor,$$
wobei im Problem \(Q=10^8\) ist. Die Nennergrenze für \(x\) ist also exakt eine Produktgrenze für die beiden Farey-Nenner.
Der Stern-Brocot-Baum beginnt mit dem Nachbarpaar \(0/1 \lt 1/1\). Ein Knoten speichert ein Intervall \((a/b,c/d)\) aus Farey-Nachbarn, und seine beiden Kinder entstehen über die Mediante
$$\frac{a+c}{b+d}:$$
$$\left(\frac{a}{b},\frac{c}{d}\right)\to\left(\frac{a}{b},\frac{a+c}{b+d}\right),\qquad \left(\frac{a+c}{b+d},\frac{c}{d}\right).$$
Die Determinanteninvariante bleibt erhalten:
$$b(a+c)-a(b+d)=bc-ad=1,\qquad (b+d)c-(a+c)d=bc-ad=1.$$
Jeder besuchte Knoten ist also wieder ein Paar benachbarter Farey-Brüche. Außerdem erscheint jede positive vollständig gekürzte rationale Zahl in genau einem Intervall des Stern-Brocot-Baums. Damit besitzt jeder mehrdeutige Mittelpunkt genau einen Knoten, der ihn erzeugt, und die Suche zählt nichts doppelt.
Für einen Knoten \((a/b,c/d)\) gehört sein Mittelpunkt genau dann zur Lösung, wenn
$$\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right) \lt \frac{1}{100},$$
also äquivalent
$$ (ad+bc)\cdot 100 \lt 2bd. $$
Zwei Monotonieeigenschaften erlauben es, ganze Teilbäume sicher zu verwerfen.
Falls \(bd \gt Q/2\), ist bereits der Nenner des aktuellen Mittelpunkts zu groß, und in den beiden Kindern steigen die Produkte auf \(b(b+d)\) bzw. \((b+d)d\). Kein Nachkomme kann also die Nennergrenze wieder unterschreiten.
Falls der linke Rand schon \(a/b \ge 1/100\) erfüllt, liegt das gesamte Intervall ab der Schwelle, und alle Nachkommen bleiben darin. Dagegen reicht ein momentan zu großer Mittelpunkt nicht als Abschneidekriterium, weil linke Nachkommen noch näher an den linken Rand rücken und dadurch wieder unter \(1/100\) fallen können.
Betrachte die Farey-Nachbarn
$$\frac{1}{101} \lt \frac{2}{201},\qquad 101\cdot 2 - 1\cdot 201 = 1.$$
Ihr Mittelpunkt ist
$$x=\frac{1}{2}\left(\frac{1}{101}+\frac{2}{201}\right)=\frac{403}{40602}\approx 0.0099256,$$
also tatsächlich kleiner als \(1/100\). Der gekürzte Nenner ist genau
$$q=2\cdot 101\cdot 201=40602.$$
Weil zwischen diesen beiden Farey-Nachbarn kein gekürzter Bruch mit Nenner kleiner als \(101+201=302\) liegen kann, liefern alle Grenzen \(B\) mit \(201 \le B \lt 302\) zwei gleich gute beste Approximationen, nämlich \(1/101\) und \(2/201\). Genau solche Mittelpunkte zählt das Programm.
Die C++-, Python- und Java-Implementierungen repräsentieren ein Stern-Brocot-Intervall durch vier ganze Zahlen \(a,b,c,d\). Alle Tests werden rein ganzzahlig per Kreuzmultiplikation ausgeführt: eine Prüfung setzt \(bd \le Q/2\) um, eine zweite vergleicht den linken Rand \(a/b\) mit \(1/100\), und eine dritte entscheidet über den Mittelpunkt mittels \((ad+bc)\cdot 100 \lt 2bd\).
Die eigentliche Suche ist eine iterative Tiefensuche mit explizitem Stack. Überlebt ein Knoten die Abschneideregeln, bildet die Implementierung die Mediante \((a+c)/(b+d)\), erzeugt daraus die beiden Kindintervalle und erhöht den Zähler, wenn der aktuelle Mittelpunkt selbst unter der Schranke liegt. Weil jeder Stern-Brocot-Knoten genau einem Farey-Nachbarpaar entspricht, steht jede Zählererhöhung für genau eine mehrdeutige rationale Zahl.
Die C++- und Java-Versionen ergänzen für den größten Eingabewert einen parallelen Vorspann. Zunächst wird der Baum breitensuchartig bis zu einer moderaten Menge von Startintervallen expandiert; die dabei schon gefundenen Mittelpunkte werden sofort mitgezählt. Anschließend bearbeiten mehrere Threads die restlichen Teilbäume unabhängig voneinander. Die Python-Version durchläuft dieselbe Struktur seriell mit demselben mathematischen Kriteriensatz.
Sei \(V\) die Anzahl der Stern-Brocot-Intervalle, die tatsächlich vom Stack entnommen werden, bevor sie abgeschnitten werden. Dann läuft der serielle Algorithmus in \(O(V)\), weil jeder besuchte Knoten nur konstante viele ganzzahlige Operationen ausführt und anschließend entweder endet oder genau zwei Kinder erzeugt.
Der Speicherbedarf beträgt \(O(H)\) für den expliziten Stack, wobei \(H\) die maximale vor dem Abschneiden erreichte Tiefe ist. In den parallelen Versionen kommt Speicher für die Startfront hinzu, doch die Gesamtarbeit bleibt linear in der Zahl der besuchten Knoten. Der entscheidende Gewinn ist strukturell: Untersucht werden nur Farey-Lücken, deren Mittelpunkt überhaupt noch einen Nenner bis \(10^8\) haben kann und deren Intervall noch nicht vollständig rechts von \(1/100\) liegt.
Bir payda sınırı \(B\) verildiğinde, \(s \le B\) koşulunu sağlayan \(r/s\) rasyoneli, \(|x-r/s|\) değerini bu sınır altındaki tüm rasyoneller arasında en küçük yapıyorsa \(x\) sayısının en iyi yaklaşımıdır. Bir rasyonel \(x\), en az bir \(B\) değeri için iki farklı en iyi yaklaşıma sahip oluyorsa ambiguous kabul edilir.
İstenen şey, \(0 \lt x \lt 1/100\) aralığında bulunan, \(x=p/q\) biçiminde indirgenmiş ve \(q \le 10^8\) koşulunu sağlayan ambiguous rasyonellerin sayısıdır. Doğru yaklaşım, paydası \(10^8\)'e kadar olan tüm kesirleri taramak değil, hangi rasyonellerin ambiguous olabileceğini tam olarak karakterize etmektir.
Bu problemin temel nesneleri komşu Farey kesirleridir. Hedef aralıktaki her ambiguous rasyonel, tek bir Farey aralığının orta noktasından gelir ve \(x\)'in paydasına ait koşul, iki uç paydanın çarpımına indirgenir.
Bir \(B\) sınırı için \(a/b\) ve \(c/d\) kesirleri \(a/b \lt x \lt c/d\) olacak şekilde iki farklı en iyi yaklaşım olsun; ayrıca \(b,d \le B\) olsun. O zaman \(v \le B\) sağlayan indirgenmiş bir \(u/v\) kesri bu ikisinin arasında kesinlikle yer alamaz; çünkü böyle bir kesir, en az bir uca göre \(x\)'e daha yakın olurdu. Demek ki \(a/b\) ile \(c/d\), \(B\) mertebeli Farey dizisinde komşudur ve bu da
$$bc-ad=1$$
eşitliğine denktir. İki hata da eşit olduğundan, \(x\) tam olarak bu aralığın orta noktası olmak zorundadır:
$$x=\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right)=\frac{ad+bc}{2bd}.$$
Tersi de doğrudur. Eğer \(a/b \lt c/d\) Farey komşularıysa ve \(B\) sayısı \(\max(b,d)\le B \lt b+d\) koşulunu sağlıyorsa, paydası en fazla \(B\) olan hiçbir indirgenmiş kesir bu iki kesrin arasına giremez. Bu durumda orta noktada her iki uç da eşit uzaklıktadır ve ikisi de en iyi yaklaşımdır. Dolayısıyla ambiguous rasyoneller, Farey komşularının orta noktalarıyla tam olarak aynıdır.
Orta nokta formülü sonradan sadeleşmez. \(bc-ad=1\) olduğundan \(bc\) ile \(ad\) ters paritelidir; bu yüzden \(ad+bc\) tektir. Ayrıca
$$\gcd(ad+bc,b)=\gcd(ad,b)=1,\qquad \gcd(ad+bc,d)=\gcd(bc,d)=1.$$
Böylece \(\gcd(ad+bc,2bd)=1\) olur ve orta nokta zaten indirgenmiş halde
$$q=2bd$$
paydasına sahiptir. Bu nedenle \(q \le Q\) koşulu doğrudan
$$2bd \le Q \qquad\Longleftrightarrow\qquad bd \le \left\lfloor\frac{Q}{2}\right\rfloor$$
şekline dönüşür. Problemde \(Q=10^8\) olduğundan, asıl sınır uç kesirlerin paydalarının çarpımı üzerindedir.
Stern-Brocot ağacı komşu çift \(0/1 \lt 1/1\) ile başlar. Her düğüm bir komşu aralık \((a/b,c/d)\) tutar ve çocuklar mediant
$$\frac{a+c}{b+d}$$
kullanılarak oluşturulur:
$$\left(\frac{a}{b},\frac{c}{d}\right)\to\left(\frac{a}{b},\frac{a+c}{b+d}\right),\qquad \left(\frac{a+c}{b+d},\frac{c}{d}\right).$$
Determinant değişmezi korunur:
$$b(a+c)-a(b+d)=bc-ad=1,\qquad (b+d)c-(a+c)d=bc-ad=1.$$
Dolayısıyla ziyaret edilen her düğüm yine bir Farey komşu çifti verir. Ayrıca her pozitif indirgenmiş rasyonel, Stern-Brocot ağacında tam bir aralıkta ortaya çıkar. Bu yüzden her ambiguous orta noktanın tek bir temsilcisi vardır ve ağaçta çift sayım oluşmaz.
Bir \((a/b,c/d)\) düğümünün orta noktası tam olarak şu durumda çözüme girer:
$$\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right) \lt \frac{1}{100},$$
yani tamsayı aritmetiğiyle
$$ (ad+bc)\cdot 100 \lt 2bd. $$
Alt ağaçları güvenle atmayı sağlayan iki monotonicity özelliği vardır.
Eğer \(bd \gt Q/2\) ise, mevcut orta noktanın paydası zaten \(Q\)'yu aşmıştır. Çocuklarda bu çarpımlar sırasıyla \(b(b+d)\) ve \((b+d)d\) olur; yani daha da büyür. Dolayısıyla hiçbir torun tekrar sınırın altına inemez.
Eğer sol uç \(a/b \ge 1/100\) ise, bütün aralık eşik değerinin sağında kalır ve tüm torunlar da aynı aralığın içinde yer alır. Buna karşılık mevcut orta noktanın büyük olması tek başına budama sebebi değildir; çünkü sol tarafa daha yakın çocuk orta noktaları yeniden \(1/100\)'ün altına düşebilir.
Şu Farey komşularını alalım:
$$\frac{1}{101} \lt \frac{2}{201},\qquad 101\cdot 2 - 1\cdot 201 = 1.$$
Orta nokta
$$x=\frac{1}{2}\left(\frac{1}{101}+\frac{2}{201}\right)=\frac{403}{40602}\approx 0.0099256$$
olur; yani gerçekten \(1/100\)'den küçüktür. İndirgenmiş payda tam olarak
$$q=2\cdot 101\cdot 201=40602$$
çıkar. Bu iki kesir Farey komşusu olduğu için, paydası \(101+201=302\)'den küçük olan hiçbir indirgenmiş kesir aralarına giremez. O halde \(201 \le B \lt 302\) aralığındaki herhangi bir payda sınırı için \(1/101\) ile \(2/201\) eşit derecede iyi iki yaklaşım verir. Programın saydığı nesne tam olarak bu tür orta noktalardır.
C++, Python ve Java uygulamaları bir Stern-Brocot aralığını dört tamsayı \(a,b,c,d\) ile temsil eder. Hiçbir yerde kayan nokta kullanılmaz: payda sınırı \(bd \le Q/2\) testiyle, eşik budaması \(a/b\) ile \(1/100\)'ün çapraz çarpım karşılaştırmasıyla, orta nokta testi ise \((ad+bc)\cdot 100 \lt 2bd\) eşitsizliğiyle yapılır.
Ana arama, çağrı yığınına güvenmek yerine açık bir yığın üzerinde iteratif derinlik öncelikli dolaşımdır. Bir düğüm budamadan kurtulursa, uygulama mediant \((a+c)/(b+d)\)'yi kurar, sol ve sağ çocuk aralıklarını yığına ekler ve mevcut orta nokta eşik altındaysa sayacı artırır. Her Stern-Brocot düğümü tek bir Farey komşu çiftiyle eşleştiği için, her artış tek bir ambiguous rasyonel sayar.
C++ ve Java sürümleri büyük girdi için paralel bir ön uç da ekler. Önce ağaç genişlik öncelikli biçimde belli sayıda tohum aralığa kadar büyütülür; bu ilk genişleme sırasında rastlanan uygun orta noktalar hemen sayılır. Daha sonra kalan alt ağaçlar iş parçacıkları arasında paylaştırılır. Python sürümü aynı matematiği ve aynı budama kurallarını tek geçişte seri olarak uygular.
\(V\), budama gerçekleşmeden önce yığından gerçekten çıkarılan Stern-Brocot düğümlerinin sayısı olsun. Serbest çalışan sürümün süresi \(O(V)\)'dir; çünkü her düğümde yalnızca sabit sayıda tamsayı işlemi yapılır ve düğüm ya hemen durur ya da iki çocuk üretir.
Bellek kullanımı açık yığın için \(O(H)\)'dir; burada \(H\), budamadan önce ulaşılan en büyük derinliktir. Paralel sürümlerde buna tohum cephesi için ek bellek gelir, fakat toplam iş yine ziyaret edilen düğüm sayısıyla lineerdir. Asıl avantaj, yalnızca paydası \(10^8\)'in altında kalabilecek ve tamamı \(1/100\)'ün sağına taşmamış Farey aralıklarının gezilmesidir.
Dado un límite de denominador \(B\), una fracción racional \(r/s\) con \(s \le B\) es una mejor aproximación de un número real \(x\) si minimiza \(|x-r/s|\) entre todas las fracciones cuyos denominadores no superan \(B\). Un racional \(x\) se llama ambiguo si existe al menos un valor de \(B\) para el cual dos fracciones distintas empatan como mejores aproximaciones.
La tarea es contar los racionales reducidos \(x=p/q\) tales que \(0 \lt x \lt 1/100\), \(q \le 10^8\) y \(x\) es ambiguo. La clave no es recorrer todas las fracciones con denominador hasta \(10^8\), sino describir exactamente qué racionales pueden ser ambiguos y contar solo esos candidatos.
Los objetos centrales son las fracciones vecinas de Farey. Todo racional ambiguo del rango pedido aparece como el punto medio de un hueco de Farey, y la restricción sobre el denominador de \(x\) se convierte en una condición muy simple sobre el producto de los denominadores de los extremos.
Supongamos que, para cierto límite \(B\), las dos mejores aproximaciones a \(x\) son \(a/b\) y \(c/d\), con \(a/b \lt x \lt c/d\) y \(b,d \le B\). No puede existir ninguna fracción reducida \(u/v\) con \(v \le B\) estrictamente entre ellas, porque entonces esa fracción estaría más cerca de \(x\) que al menos uno de los extremos. Por lo tanto, \(a/b\) y \(c/d\) deben ser vecinos en la sucesión de Farey de orden \(B\), lo cual equivale a
$$bc-ad=1.$$
Como los dos errores son iguales, \(x\) tiene que ser exactamente el punto medio del intervalo:
$$x=\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right)=\frac{ad+bc}{2bd}.$$
La recíproca también vale. Si \(a/b \lt c/d\) son vecinos de Farey y \(B\) cumple \(\max(b,d)\le B \lt b+d\), entonces no hay ninguna fracción reducida con denominador a lo sumo \(B\) entre ellas. En el punto medio, ambos extremos quedan a la misma distancia de \(x\) y los dos son mejores aproximaciones. Así, los racionales ambiguos son exactamente los puntos medios de pares vecinos de Farey.
La expresión del punto medio no se simplifica más. De \(bc-ad=1\) se deduce que \(bc\) y \(ad\) tienen paridad opuesta, luego \(ad+bc\) es impar. Además,
$$\gcd(ad+bc,b)=\gcd(ad,b)=1,\qquad \gcd(ad+bc,d)=\gcd(bc,d)=1.$$
Por tanto, \(\gcd(ad+bc,2bd)=1\), y el punto medio ya está en forma reducida con denominador
$$q=2bd.$$
Por eso la restricción \(q \le Q\) se transforma en
$$2bd \le Q \qquad\Longleftrightarrow\qquad bd \le \left\lfloor\frac{Q}{2}\right\rfloor,$$
con \(Q=10^8\). Toda la condición de tamaño queda capturada por el producto de los dos denominadores extremos.
El árbol de Stern-Brocot comienza con el par vecino \(0/1 \lt 1/1\). Un nodo almacena un intervalo \((a/b,c/d)\) formado por vecinos de Farey, y sus hijos se construyen con la mediatriz aritmética o mediant
$$\frac{a+c}{b+d}:$$
$$\left(\frac{a}{b},\frac{c}{d}\right)\to\left(\frac{a}{b},\frac{a+c}{b+d}\right),\qquad \left(\frac{a+c}{b+d},\frac{c}{d}\right).$$
El invariante determinantal se conserva:
$$b(a+c)-a(b+d)=bc-ad=1,\qquad (b+d)c-(a+c)d=bc-ad=1.$$
Así, cada nodo visitado vuelve a ser un par de vecinos de Farey. Además, cada racional positivo reducido aparece en un único intervalo del árbol de Stern-Brocot, de modo que cada punto medio ambiguo tiene un único nodo que lo genera y no hay doble conteo.
Para un nodo \((a/b,c/d)\), su punto medio pertenece a la respuesta exactamente cuando
$$\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right) \lt \frac{1}{100},$$
lo que las implementaciones reescriben como
$$ (ad+bc)\cdot 100 \lt 2bd. $$
Hay dos propiedades monótonas que permiten descartar subárboles completos.
Si \(bd \gt Q/2\), el denominador del punto medio actual ya supera \(Q\), y en los dos hijos los productos pasan a ser \(b(b+d)\) y \((b+d)d\), que son mayores. Ningún descendiente puede volver a quedar dentro del límite.
Si el extremo izquierdo ya cumple \(a/b \ge 1/100\), entonces todo el intervalo queda a la derecha del umbral y todos los descendientes permanecen dentro de él. En cambio, que el punto medio actual sea demasiado grande no basta para podar, porque los descendientes más cercanos al extremo izquierdo todavía pueden caer por debajo de \(1/100\).
Tomemos los vecinos de Farey
$$\frac{1}{101} \lt \frac{2}{201},\qquad 101\cdot 2 - 1\cdot 201 = 1.$$
Su punto medio es
$$x=\frac{1}{2}\left(\frac{1}{101}+\frac{2}{201}\right)=\frac{403}{40602}\approx 0.0099256,$$
que efectivamente está por debajo de \(1/100\). El denominador reducido es exactamente
$$q=2\cdot 101\cdot 201=40602.$$
Como entre esos dos vecinos de Farey no puede aparecer ninguna fracción reducida con denominador inferior a \(101+201=302\), cualquier límite \(B\) con \(201 \le B \lt 302\) hace que \(1/101\) y \(2/201\) sean dos mejores aproximaciones empatadas. Ese es exactamente el tipo de racional ambiguo que cuenta el algoritmo.
Las implementaciones en C++, Python y Java representan un intervalo de Stern-Brocot mediante cuatro enteros \(a,b,c,d\). Todas las comparaciones se hacen con aritmética entera exacta: una prueba aplica el límite \(bd \le Q/2\), otra compara el extremo izquierdo \(a/b\) con \(1/100\), y una tercera decide si el punto medio cumple \((ad+bc)\cdot 100 \lt 2bd\).
La búsqueda principal es un recorrido iterativo en profundidad usando una pila. Cuando un nodo supera las podas, la implementación forma la mediant \((a+c)/(b+d)\), empuja los dos intervalos hijo y suma uno al contador si el punto medio actual está bajo el umbral. Como cada nodo del árbol corresponde a un único par de vecinos de Farey, cada incremento cuenta exactamente un racional ambiguo.
Las versiones en C++ y Java añaden un prefijo paralelo para la entrada grande. Primero expanden el árbol en anchura hasta obtener una frontera moderada de subárboles semilla, contando ya los puntos medios válidos encontrados en esa fase. Después reparten los subárboles restantes entre varios hilos. La versión en Python aplica la misma idea matemática y las mismas podas en una sola pasada serial.
Sea \(V\) el número de intervalos de Stern-Brocot que realmente se extraen de la pila antes de ser descartados. El algoritmo serial tarda \(O(V)\), porque cada nodo visitado realiza solo una cantidad constante de operaciones enteras y luego o bien termina o bien genera dos hijos.
El uso de memoria es \(O(H)\) para la pila explícita, donde \(H\) es la mayor profundidad alcanzada antes de la poda. En las versiones paralelas se añade almacenamiento para la frontera inicial, pero el trabajo total sigue siendo lineal en el número de nodos visitados. El ahorro real proviene de que solo se exploran huecos de Farey cuyo punto medio todavía puede tener denominador a lo sumo \(10^8\) y cuyo intervalo no ha quedado completamente por encima de \(1/100\).
给定一个分母上界 \(B\)，若有理数 \(r/s\) 满足 \(s \le B\)，并且在所有分母不超过 \(B\) 的有理数中使 \(|x-r/s|\) 最小，那么它就是实数 \(x\) 在该上界下的一个最佳逼近。如果存在某个 \(B\)，使得两个不同的有理数同时达到这个最小误差，那么 \(x\) 就称为 ambiguous。
本题要求统计所有既约有理数 \(x=p/q\)，满足 \(0 \lt x \lt 1/100\)、\(q \le 10^8\)，并且 \(x\) 是 ambiguous。真正可行的方法不是遍历所有分母不超过 \(10^8\) 的分数，而是先刻画 ambiguous 有理数的精确结构，再只计数这些结构化候选。
核心对象是 Farey 相邻分数。目标区间中的每一个 ambiguous 有理数，都恰好来自某个 Farey 间隙的中点；而 \(x\) 的分母约束，也会转化成这两个端点分母乘积的简单不等式。
设某个分母上界 \(B\) 下，\(x\) 有两个不同的最佳逼近 \(a/b\) 与 \(c/d\)，并且 \(a/b \lt x \lt c/d\)、\(b,d \le B\)。那么在它们之间不可能还存在一个既约分数 \(u/v\) 满足 \(v \le B\)。否则这个分数会比至少一个端点更接近 \(x\)，从而破坏“最佳逼近”的并列关系。因此 \(a/b\) 与 \(c/d\) 必须是 \(B\) 阶 Farey 序列中的相邻项，也就是
$$bc-ad=1.$$
因为两侧误差相等，\(x\) 必须正好是这个区间的中点：
$$x=\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right)=\frac{ad+bc}{2bd}.$$
反过来也成立。如果 \(a/b \lt c/d\) 是 Farey 相邻分数，且某个上界 \(B\) 满足 \(\max(b,d)\le B \lt b+d\)，那么在分母不超过 \(B\) 的范围内，不会有任何既约分数落在它们之间。于是中点到这两个端点的距离完全相同，而且这两个端点都是真正的最佳逼近。所以 ambiguous 有理数与 Farey 相邻分数的中点完全对应。
中点公式不会再发生额外约分。由 \(bc-ad=1\) 可知，\(bc\) 与 \(ad\) 奇偶性相反，因此 \(ad+bc\) 一定是奇数。同时有
$$\gcd(ad+bc,b)=\gcd(ad,b)=1,\qquad \gcd(ad+bc,d)=\gcd(bc,d)=1.$$
所以 \(\gcd(ad+bc,2bd)=1\)，中点已经是既约形式，其分母正好是
$$q=2bd.$$
这就是为什么题目的约束 \(q \le Q\) 可以直接写成
$$2bd \le Q \qquad\Longleftrightarrow\qquad bd \le \left\lfloor\frac{Q}{2}\right\rfloor,$$
其中 \(Q=10^8\)。换句话说，最终是否可能进入答案，只取决于两个 Farey 端点分母的乘积。
Stern-Brocot 树从相邻对 \(0/1 \lt 1/1\) 开始。一个节点保存一个 Farey 相邻区间 \((a/b,c/d)\)，它的两个子区间由 mediant
$$\frac{a+c}{b+d}$$
生成：
$$\left(\frac{a}{b},\frac{c}{d}\right)\to\left(\frac{a}{b},\frac{a+c}{b+d}\right),\qquad \left(\frac{a+c}{b+d},\frac{c}{d}\right).$$
这里最关键的不变量是
$$b(a+c)-a(b+d)=bc-ad=1,\qquad (b+d)c-(a+c)d=bc-ad=1.$$
因此每个子节点仍然对应一对 Farey 相邻分数。另一方面，任意正既约分数都只会在 Stern-Brocot 树中的一个区间里出现一次，于是每个 ambiguous 中点也只有唯一的生成节点。这保证了遍历时不会漏计，也不会重计。
对当前节点 \((a/b,c/d)\) 来说，它的中点被计入答案，当且仅当
$$\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right) \lt \frac{1}{100},$$
也就是用整数不等式表示为
$$ (ad+bc)\cdot 100 \lt 2bd. $$
整棵子树可以被提前丢弃，依赖于两个单调性事实。
如果 \(bd \gt Q/2\)，那么当前中点的分母已经超过 \(Q\)，而两个子节点对应的乘积会变成 \(b(b+d)\) 和 \((b+d)d\)，只会更大，不可能重新回到合法范围内。
如果左端点已经满足 \(a/b \ge 1/100\)，那么整个区间都落在阈值右侧，所有后代仍然位于这个区间内，因此也都不可能小于 \(1/100\)。相反，如果只是当前中点太大，却不能直接剪枝，因为更靠左的后代中点仍然可能重新落回阈值下方。
考虑一对 Farey 相邻分数
$$\frac{1}{101} \lt \frac{2}{201},\qquad 101\cdot 2 - 1\cdot 201 = 1.$$
它们的中点是
$$x=\frac{1}{2}\left(\frac{1}{101}+\frac{2}{201}\right)=\frac{403}{40602}\approx 0.0099256,$$
确实满足 \(x \lt 1/100\)。而且它的既约分母正好是
$$q=2\cdot 101\cdot 201=40602.$$
由于这两个端点是 Farey 相邻分数，在分母小于 \(101+201=302\) 的范围内，不可能有第三个既约分数插在它们之间。因此只要分母上界 \(B\) 满足 \(201 \le B \lt 302\)，这两个端点就会成为并列的最佳逼近，于是 \(403/40602\) 就是一个 ambiguous 数。这正是程序在树上计数的对象。
C++、Python 和 Java 实现都用四个整数 \(a,b,c,d\) 表示一个 Stern-Brocot 区间。所有判断都通过整数交叉相乘完成，不使用浮点数：一条判断对应分母约束 \(bd \le Q/2\)，一条判断检测左端点 \(a/b\) 是否已经达到 \(1/100\)，另一条判断检测中点是否满足 \((ad+bc)\cdot 100 \lt 2bd\)。
主过程是显式栈上的迭代式深度优先遍历。若当前节点没有被剪掉，实现就计算 mediant \((a+c)/(b+d)\)，把左右两个子区间压栈，并在当前中点落在阈值下方时把答案加一。因为每个 Stern-Brocot 节点都唯一对应一对 Farey 相邻分数，所以每一次加一都严格对应一个 ambiguous 有理数。
C++ 和 Java 实现还为最大输入加入了并行前端。它们先做一段宽度优先扩展，得到一批适中的种子子树，并把这段前缀中已经满足条件的中点先计入答案，然后再把剩余子树分发给多个工作线程。Python 实现使用同样的数学判定和同样的剪枝，只是串行完成整个遍历。
设 \(V\) 为真正从栈中弹出并处理过的 Stern-Brocot 节点数。串行算法的时间复杂度是 \(O(V)\)，因为每个节点只做常数次整数运算，然后要么被终止，要么生成两个子节点。
空间复杂度是 \(O(H)\)，其中 \(H\) 是剪枝前搜索达到的最大深度，对应显式栈的规模。并行版本额外需要存储一层种子前沿，但总工作量仍然与访问节点数线性相关。真正的效率来源在于：程序只探索那些中点分母仍可能不超过 \(10^8\)、并且整个区间尚未完全移到 \(1/100\) 右侧的 Farey 间隙。
Для ограничения на знаменатель \(B\) рациональное число \(r/s\) с \(s \le B\) называется наилучшим приближением числа \(x\), если оно минимизирует \(|x-r/s|\) среди всех рациональных чисел с знаменателем не больше \(B\). Рациональное число \(x\) называется ambiguous, если существует хотя бы одно значение \(B\), при котором две разные дроби одновременно являются наилучшими приближениями.
Нужно посчитать все несократимые рациональные числа \(x=p/q\), для которых \(0 \lt x \lt 1/100\), \(q \le 10^8\), и при этом \(x\) ambiguous. Рабочая идея состоит не в полном переборе дробей до знаменателя \(10^8\), а в точном описании того, какие рациональные числа вообще могут обладать такой неоднозначностью.
Ключевые объекты здесь - соседние дроби Фарея. Каждое ambiguous число в нужном диапазоне возникает как середина одного промежутка между соседями Фарея, а ограничение на знаменатель \(x\) превращается в простое условие на произведение знаменателей концов этого промежутка.
Пусть для некоторого ограничения \(B\) число \(x\) имеет два различных наилучших приближения \(a/b\) и \(c/d\), где \(a/b \lt x \lt c/d\) и \(b,d \le B\). Тогда между ними не может лежать никакая несократимая дробь \(u/v\) с \(v \le B\), потому что она была бы ближе к \(x\), чем хотя бы один из концов. Следовательно, \(a/b\) и \(c/d\) должны быть соседями в последовательности Фарея порядка \(B\), а это эквивалентно равенству
$$bc-ad=1.$$
Так как ошибки у двух приближений совпадают, число \(x\) обязано быть точной серединой интервала:
$$x=\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right)=\frac{ad+bc}{2bd}.$$
Обратное утверждение тоже верно. Если \(a/b \lt c/d\) - соседи Фарея и \(B\) удовлетворяет \(\max(b,d)\le B \lt b+d\), то никакая несократимая дробь со знаменателем не больше \(B\) не попадет между ними. Поэтому в середине интервала оба конца находятся на одинаковом расстоянии от \(x\) и одновременно являются наилучшими приближениями. Значит, ambiguous числа - это в точности середины между соседними дробями Фарея.
Формула середины здесь не упрощается неожиданным образом. Из условия \(bc-ad=1\) следует, что \(bc\) и \(ad\) имеют разную четность, поэтому \(ad+bc\) нечетно. Кроме того,
$$\gcd(ad+bc,b)=\gcd(ad,b)=1,\qquad \gcd(ad+bc,d)=\gcd(bc,d)=1.$$
Следовательно, \(\gcd(ad+bc,2bd)=1\), и дробь уже несократима с знаменателем
$$q=2bd.$$
Поэтому ограничение \(q \le Q\) переписывается как
$$2bd \le Q \qquad\Longleftrightarrow\qquad bd \le \left\lfloor\frac{Q}{2}\right\rfloor,$$
где в задаче \(Q=10^8\). Иными словами, весь контроль над знаменателем сводится к произведению знаменателей двух соседей Фарея.
Дерево Штерна-Броко начинается с соседней пары \(0/1 \lt 1/1\). Узел хранит один интервал \((a/b,c/d)\), образованный соседями Фарея, а дети строятся через медианту
$$\frac{a+c}{b+d}:$$
$$\left(\frac{a}{b},\frac{c}{d}\right)\to\left(\frac{a}{b},\frac{a+c}{b+d}\right),\qquad \left(\frac{a+c}{b+d},\frac{c}{d}\right).$$
Инвариант детерминанта сохраняется:
$$b(a+c)-a(b+d)=bc-ad=1,\qquad (b+d)c-(a+c)d=bc-ad=1.$$
Значит, каждый посещенный узел снова задает пару соседей Фарея. Более того, каждое положительное несократимое рациональное число возникает ровно в одном интервале дерева Штерна-Броко, поэтому у каждого ambiguous середины есть единственный порождающий узел. Это исключает и пропуски, и двойной счет.
Для текущего узла \((a/b,c/d)\) его середина входит в ответ тогда и только тогда, когда
$$\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right) \lt \frac{1}{100},$$
то есть, в чисто целочисленном виде,
$$ (ad+bc)\cdot 100 \lt 2bd. $$
Существует два монотонных факта, которые позволяют безопасно отбрасывать целые поддеревья.
Если \(bd \gt Q/2\), то знаменатель текущей середины уже превышает \(Q\), а у детей произведения становятся \(b(b+d)\) и \((b+d)d\), то есть только растут. Ни один потомок уже не сможет вернуться под лимит.
Если левый конец уже удовлетворяет \(a/b \ge 1/100\), то весь интервал лежит правее порога, и все потомки остаются внутри этого интервала. Но если текущая середина просто слишком велика, этого еще недостаточно для отсечения: более левые потомки могут снова опуститься ниже \(1/100\).
Рассмотрим соседей Фарея
$$\frac{1}{101} \lt \frac{2}{201},\qquad 101\cdot 2 - 1\cdot 201 = 1.$$
Их середина равна
$$x=\frac{1}{2}\left(\frac{1}{101}+\frac{2}{201}\right)=\frac{403}{40602}\approx 0.0099256,$$
то есть действительно меньше \(1/100\). Ее сокращенный знаменатель равен
$$q=2\cdot 101\cdot 201=40602.$$
Поскольку между этими двумя соседями Фарея не существует несократимой дроби со знаменателем меньше \(101+201=302\), любое ограничение \(B\) с \(201 \le B \lt 302\) делает дроби \(1/101\) и \(2/201\) двумя одинаково хорошими наилучшими приближениями. Именно такие середины и подсчитывает алгоритм.
Реализации на C++, Python и Java представляют один интервал дерева Штерна-Броко четырьмя целыми числами \(a,b,c,d\). Все сравнения выполняются без вещественной арифметики: одно условие реализует ограничение \(bd \le Q/2\), второе сравнивает левый конец \(a/b\) с \(1/100\), а третье проверяет середину по формуле \((ad+bc)\cdot 100 \lt 2bd\).
Основной поиск - это итеративный обход в глубину с явным стеком. Если узел не отсекается, реализация строит медианту \((a+c)/(b+d)\), добавляет левый и правый дочерние интервалы в стек и увеличивает счетчик, если текущая середина уже находится ниже порога. Так как каждый узел соответствует ровно одной паре соседей Фарея, каждое увеличение счетчика означает ровно одно ambiguous рациональное число.
Версии на C++ и Java добавляют параллельный префикс для самого большого входа. Сначала дерево немного расширяется в ширину, чтобы получить умеренную фронтирную коллекцию начальных поддеревьев; все подходящие середины, встретившиеся на этом этапе, сразу учитываются. Затем оставшиеся поддеревья распределяются между потоками. Версия на Python выполняет тот же обход и те же точные проверки последовательно.
Пусть \(V\) - число интервалов дерева Штерна-Броко, которые реально извлекаются из стека и обрабатываются до срабатывания отсечения. Тогда последовательный алгоритм работает за \(O(V)\), поскольку каждый посещенный узел выполняет лишь константное число целочисленных операций и затем либо завершается, либо порождает двух потомков.
Память составляет \(O(H)\) для явного стека, где \(H\) - максимальная достигнутая глубина поиска до отсечения. В параллельных версиях добавляется память под стартовый фронтир, но суммарная работа остается линейной по числу посещенных узлов. Главное преимущество состоит в том, что обходятся только те промежутки Фарея, у которых середина еще может иметь знаменатель не больше \(10^8\) и весь интервал еще не ушел целиком правее \(1/100\).
إذا أعطينا حدًا أعلى للمقام \(B\)، فإن الكسر \(r/s\) حيث \(s \le B\) يسمى تقريبًا أفضل للعدد الحقيقي \(x\) إذا كان يحقق أصغر قيمة ممكنة لـ \(|x-r/s|\) بين جميع الكسور التي لا تتجاوز مقاماتها \(B\). ويقال إن العدد النسبي \(x\) ambiguous إذا وُجد حد \(B\) واحد على الأقل يجعل كسرين مختلفين يتعادلان بوصفهما أفضل تقريبين.
المطلوب هو عدُّ جميع الأعداد النسبية المختزلة \(x=p/q\) التي تحقق \(0 \lt x \lt 1/100\) و \(q \le 10^8\) وتملك هذه الخاصية. الفكرة الصحيحة ليست فحص كل الكسور ذات المقامات حتى \(10^8\)، بل توصيف الأعداد ambiguous توصيفًا دقيقًا ثم عدُّ تلك البنية فقط.
العناصر الحاسمة هنا هي الكسور المتجاورة في متتالية فاري. كل عدد ambiguous في المجال المطلوب يظهر بوصفه منتصف فجوة فاري واحدة، كما أن شرط المقام على \(x\) يتحول إلى شرط بسيط على حاصل ضرب مقامي طرفي تلك الفجوة.
افترض أن حدًا ما \(B\) يعطي تقريبين أفضل مختلفين هما \(a/b\) و \(c/d\) بحيث \(a/b \lt x \lt c/d\) و \(b,d \le B\). عندئذ لا يمكن أن يوجد كسر مختزل \(u/v\) مع \(v \le B\) يقع بينهما مباشرة، لأن هذا الكسر سيكون أقرب إلى \(x\) من أحد الطرفين على الأقل. إذن يجب أن يكون \(a/b\) و \(c/d\) متجاورين في متتالية فاري من الرتبة \(B\)، وهذا يكافئ العلاقة
$$bc-ad=1.$$
وبما أن الخطأين متساويان، فلا بد أن يكون \(x\) هو منتصف الفترة تمامًا:
$$x=\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right)=\frac{ad+bc}{2bd}.$$
والعكس صحيح أيضًا. فإذا كان \(a/b \lt c/d\) جارين في فاري، وكان \(B\) يحقق \(\max(b,d)\le B \lt b+d\)، فلا يوجد أي كسر مختزل مقامه لا يتجاوز \(B\) بينهما. وعند المنتصف يكون الطرفان على المسافة نفسها من \(x\)، فيصبحان معًا أفضل تقريبين. لذلك فالأعداد ambiguous هي بالضبط منتصفات الأزواج المتجاورة في فاري.
صيغة المنتصف لا تختزل لاحقًا بشكل مفاجئ. من الشرط \(bc-ad=1\) نعلم أن \(bc\) و \(ad\) مختلفان في الفردية، ولذلك يكون \(ad+bc\) عددًا فرديًا. كذلك لدينا
$$\gcd(ad+bc,b)=\gcd(ad,b)=1,\qquad \gcd(ad+bc,d)=\gcd(bc,d)=1.$$
إذًا \(\gcd(ad+bc,2bd)=1\)، ومن ثم يكون المنتصف في أبسط صورة ومقامه
$$q=2bd.$$
ولهذا يتحول الشرط \(q \le Q\) إلى
$$2bd \le Q \qquad\Longleftrightarrow\qquad bd \le \left\lfloor\frac{Q}{2}\right\rfloor,$$
حيث \(Q=10^8\) في هذه المسألة. أي إن شرط المقام على \(x\) يصبح شرطًا مباشرًا على حاصل ضرب مقامي طرفي الفجوة.
تبدأ شجرة Stern-Brocot من الزوج المتجاور \(0/1 \lt 1/1\). كل عقدة تخزن فترة من الشكل \((a/b,c/d)\) حيث الطرفان جاران في فاري، ويولد الابنان عبر الوسيط
$$\frac{a+c}{b+d}:$$
$$\left(\frac{a}{b},\frac{c}{d}\right)\to\left(\frac{a}{b},\frac{a+c}{b+d}\right),\qquad \left(\frac{a+c}{b+d},\frac{c}{d}\right).$$
ويبقى الثابت المحدد محفوظًا:
$$b(a+c)-a(b+d)=bc-ad=1,\qquad (b+d)c-(a+c)d=bc-ad=1.$$
إذن كل عقدة مزارة تمثل مرة أخرى زوجًا متجاورًا في فاري. وفوق ذلك يظهر كل كسر موجب مختزل في فترة واحدة فقط داخل شجرة Stern-Brocot، ولذلك يمتلك كل منتصف ambiguous عقدة وحيدة تولده، فلا يحدث عدّ مزدوج.
بالنسبة إلى العقدة \((a/b,c/d)\)، فإن منتصفها يدخل في الجواب إذا وفقط إذا
$$\frac{1}{2}\left(\frac{a}{b}+\frac{c}{d}\right) \lt \frac{1}{100},$$
وهو ما تعيد التطبيقات كتابته بصيغة صحيحة تمامًا:
$$ (ad+bc)\cdot 100 \lt 2bd. $$
هناك حقيقتان أحاديتان تسمحان بحذف أفرع كاملة بأمان.
إذا كان \(bd \gt Q/2\)، فمقام المنتصف الحالي تجاوز \(Q\) بالفعل، وفي الطفلين يصبح الحاصل \(b(b+d)\) و \((b+d)d\)، أي أكبر من السابق. لذلك لا يمكن لأي نسل لاحق أن يعود ضمن الحد.
وإذا صار الطرف الأيسر يحقق \(a/b \ge 1/100\)، فإن الفترة كلها أصبحت عند العتبة أو إلى يمينها، وجميع الأحفاد يبقون داخل هذه الفترة. أما كون المنتصف الحالي أكبر من المطلوب فليس سببًا كافيًا للتقليم، لأن الأحفاد الأقرب إلى الطرف الأيسر قد يهبطون مجددًا تحت \(1/100\).
لنأخذ الجارين في فاري
$$\frac{1}{101} \lt \frac{2}{201},\qquad 101\cdot 2 - 1\cdot 201 = 1.$$
منتصفهما هو
$$x=\frac{1}{2}\left(\frac{1}{101}+\frac{2}{201}\right)=\frac{403}{40602}\approx 0.0099256,$$
وهو بالفعل أصغر من \(1/100\). أما مقامه المختزل فهو
$$q=2\cdot 101\cdot 201=40602.$$
وبما أن الكسرين متجاوران في فاري، فلا يمكن لأي كسر مختزل مقامه أصغر من \(101+201=302\) أن يقع بينهما. لذلك فإن أي حد \(B\) يحقق \(201 \le B \lt 302\) يجعل \(1/101\) و \(2/201\) تقريبين أفضل متساويين، ومن ثم يكون \(403/40602\) عددًا ambiguous. هذا بالضبط هو نوع المنتصفات الذي يعدّه البرنامج.
تمثل تطبيقات C++ وPython وJava فترة Stern-Brocot واحدة بالأعداد الصحيحة الأربعة \(a,b,c,d\). كل الاختبارات تنفذ بحسابات صحيحة فقط ومن دون استخدام الأعداد العائمة: اختبار لشرط \(bd \le Q/2\)، واختبار لمقارنة الطرف الأيسر \(a/b\) مع \(1/100\)، واختبار لمنتصف الفترة بواسطة \((ad+bc)\cdot 100 \lt 2bd\).
البحث الرئيسي هو اجتياز عمقي تكراري باستخدام مكدس صريح. إذا نجت العقدة من التقليم، تُحسب mediant على الصورة \((a+c)/(b+d)\)، ثم تُدفع الفترتان الابنتان إلى المكدس، ويزداد العداد إذا كان المنتصف الحالي تحت العتبة. وبما أن كل عقدة من الشجرة تقابل زوجًا وحيدًا من جيران فاري، فإن كل زيادة في العداد تمثل عددًا ambiguous واحدًا بالضبط.
تضيف نسختا C++ وJava مرحلة أمامية متوازية عند الإدخال الكبير. إذ توسعان الشجرة أولًا على نحو عرضي حتى تحصلا على جبهة معتدلة من الفروع البذرية، مع احتساب المنتصفات الصحيحة التي تظهر في هذا التوسع الأولي. ثم توزع بقية الأفرع على عدة خيوط عمل. أما نسخة Python فتنفذ الاجتياز نفسه والقواعد الرياضية نفسها بصورة تسلسلية.
إذا رمزنا بـ \(V\) إلى عدد فترات Stern-Brocot التي تُسحب فعلًا من المكدس وتُفحص قبل أن يوقفها التقليم، فإن الزمن في النسخة التسلسلية يساوي \(O(V)\)، لأن كل عقدة مزارة تنفذ عددًا ثابتًا من العمليات الصحيحة ثم إما تتوقف أو تنتج طفلين.
استهلاك الذاكرة هو \(O(H)\) للمكدس الصريح، حيث \(H\) هو أكبر عمق يصل إليه البحث قبل التقليم. وفي النسخ المتوازية توجد ذاكرة إضافية لجبهة البذور، لكن العمل الكلي يبقى خطيًا في عدد العقد المزارة. الفائدة الحقيقية هي أن البرنامج يستكشف فقط فجوات فاري التي ما زال منتصفها قادرًا على امتلاك مقام لا يتجاوز \(10^8\)، والتي لم تنتقل بكاملها بعد إلى يمين \(1/100\).