The problem asks for the number of reduced fractions \(a/b\) that satisfy
$$\frac{1}{3} \lt \frac{a}{b} \lt \frac{1}{2}, \qquad b \le 12000.$$
So we are not listing all fractions with bounded denominator; we are counting only the reduced ones that fall inside one specific interval. The implementations do not scan every denominator and test coprimality. Instead, they treat \(\left(\frac13,\frac12\right)\) as a Stern-Brocot interval and count the admissible mediants generated inside it.
The natural state is an interval whose endpoints are neighboring reduced fractions. For such an interval, the next fraction that can appear inside it is its mediant, and that observation leads directly to the recurrence used by the implementation.
Let the current interval be
$$\frac{a}{b} \lt \frac{c}{d}, \qquad bc-ad=1.$$
The initial interval \(\frac13 \lt \frac12\) already has this property, because \(3\cdot 1 - 1\cdot 2 = 1\). Fractions with determinant \(1\) in this sense are neighbors in a Farey sequence and adjacent vertices in the Stern-Brocot tree.
The mediant of the two endpoints is
$$\frac{a+c}{b+d}.$$
It lies strictly between the endpoints because
$$\frac{a}{b} \lt \frac{a+c}{b+d} \lt \frac{c}{d}.$$
It is also automatically reduced. If some integer \(g\) divided both \(a+c\) and \(b+d\), then \(g\) would divide
$$d(a+c)-c(b+d)=ad-bc=-1,$$
so \(g=1\). This is why the algorithm never performs a \(\gcd\) check.
The pruning rule in the code depends on a stronger fact: among all reduced fractions strictly between \(\frac{a}{b}\) and \(\frac{c}{d}\), the mediant has the smallest possible denominator.
Take any reduced fraction \(\frac{x}{y}\) with
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}.$$
Define
$$m=cy-dx,\qquad n=bx-ay.$$
Both numbers are positive because \(\frac{x}{y}\) lies strictly inside the interval. Using \(bc-ad=1\), we get
$$ma+nc = a(cy-dx)+c(bx-ay)=x(bc-ad)=x,$$
$$mb+nd = b(cy-dx)+d(bx-ay)=y(bc-ad)=y.$$
Hence
$$x=ma+nc,\qquad y=mb+nd.$$
Since \(m,n \ge 1\), it follows that
$$y=mb+nd \ge b+d.$$
Equality holds only when \(m=n=1\), which gives \(\frac{x}{y}=\frac{a+c}{b+d}\). Therefore the mediant is the unique interior reduced fraction with the smallest denominator. If \(b+d\gt N\), then no reduced fraction in that interval can have denominator at most \(N\), so the whole branch can be discarded immediately.
Once the mediant is inserted, the interval splits into
$$\left(\frac{a}{b},\frac{a+c}{b+d}\right), \qquad \left(\frac{a+c}{b+d},\frac{c}{d}\right).$$
Both child intervals still satisfy the same determinant condition:
$$b(a+c)-a(b+d)=bc-ad=1,$$
$$ (b+d)c-(a+c)d=bc-ad=1.$$
So exactly the same reasoning applies recursively. Every admissible reduced fraction lies either to the left of the mediant or to the right of it, never both. That means the search space is partitioned without overlap, and every fraction in the target interval appears exactly once in this subtree.
Let
$$T_N\!\left(\frac{a}{b},\frac{c}{d}\right)$$
denote the number of reduced fractions \(\frac{x}{y}\) with \(y\le N\) and
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d},$$
under the invariant \(bc-ad=1\). Then the exact recurrence is
$$ T_N\!\left(\frac{a}{b},\frac{c}{d}\right)= \begin{cases} 0, & b+d \gt N,\\[4pt] 1 + T_N\!\left(\frac{a}{b},\frac{a+c}{b+d}\right) + T_N\!\left(\frac{a+c}{b+d},\frac{c}{d}\right), & b+d \le N. \end{cases} $$
The answer to the problem is therefore
$$T_{12000}\!\left(\frac13,\frac12\right).$$
This is not merely a heuristic tree walk. It is an exact decomposition of all reduced fractions in the interval, ordered by the Stern-Brocot structure.
Start with \(\frac13\) and \(\frac12\). Their mediant is \(\frac25\), and \(5 \le 8\), so \(\frac25\) contributes one count.
The left child interval is \(\left(\frac13,\frac25\right)\). Its mediant is \(\frac38\), and \(8 \le 8\), so that contributes another count. The next mediants below it have denominators \(11\) and \(13\), so that branch stops.
The right child interval is \(\left(\frac25,\frac12\right)\). Its mediant is \(\frac37\), and \(7 \le 8\), so it also counts. Its children would have denominators \(12\) and \(9\), both too large, so that branch stops as well.
The complete set is therefore
$$\left\{\frac38,\frac25,\frac37\right\},$$
so the count is \(3\). This is exactly the first checkpoint used by the implementations. Extending the same tree to \(N=12\) produces \(7\) fractions, matching the second checkpoint.
The C++, Python, and Java implementations all start from the same state: the interval whose endpoints are \(\frac13\) and \(\frac12\). For each interval, the implementation computes the mediant numerator and denominator by simple addition. If the new denominator exceeds the limit, it returns \(0\) for that branch. Otherwise it counts that mediant and continues into the left and right child intervals.
The C++ and Java implementations express this logic directly as a recursive depth-first search. The Python implementation performs the same traversal with an explicit stack of intervals, which avoids recursion-depth issues while preserving the exact same recurrence and the exact same count.
Before solving the full case \(N=12000\), the code verifies the small benchmark cases \(N=8 \mapsto 3\) and \(N=12 \mapsto 7\). Those checkpoints confirm that the interval split, the stopping rule, and the one-count-per-mediant logic are all aligned with the mathematics above.
Each valid fraction in the interval is generated exactly once, and each rejected branch ends after a constant amount of work. If \(A(N)\) denotes the number of reduced fractions in \(\left(\frac13,\frac12\right)\) with denominator at most \(N\), then the running time is \(O(A(N))\). For this problem, \(A(N)\) grows on the order of \(N^2\), so the algorithm is effectively quadratic in the bound, but with no wasted \(\gcd\) checks over irrelevant pairs.
The memory usage is \(O(H)\), where \(H\) is the depth of the search stack. In the recursive C++ and Java versions this is call-stack depth; in the Python version it is the size of the explicit stack. The worst-case depth is \(O(N)\) because some branches increase denominators only gradually, but the storage is still tiny compared with enumerating all candidate numerators and denominators directly.
Gesucht ist die Anzahl der vollständig gekürzten Brüche \(a/b\), für die
$$\frac{1}{3} \lt \frac{a}{b} \lt \frac{1}{2}, \qquad b \le 12000.$$
Damit zählen wir nicht einfach alle Brüche mit beschränktem Nenner, sondern nur die reduzierten Brüche in genau diesem Intervall. Die Implementierungen laufen deshalb nicht alle Nenner durch und testen den ggT. Stattdessen betrachten sie \(\left(\frac13,\frac12\right)\) als Intervall im Stern-Brocot-Baum beziehungsweise in einer Farey-Folge und zählen die darin entstehenden Medianten.
Der passende Zustand ist ein Intervall, dessen Endpunkte benachbarte reduzierte Brüche sind. In einem solchen Intervall ist der nächste mögliche Innenpunkt der Mediant der Endpunkte, und genau daraus ergibt sich die verwendete Rekursion.
Betrachte ein aktuelles Intervall
$$\frac{a}{b} \lt \frac{c}{d}, \qquad bc-ad=1.$$
Schon das Startintervall \(\frac13 \lt \frac12\) erfüllt diese Bedingung, denn \(3\cdot 1 - 1\cdot 2 = 1\). Brüche mit Determinante \(1\) in diesem Sinn sind Farey-Nachbarn und benachbarte Knoten im Stern-Brocot-Baum.
Der Mediant der beiden Endpunkte ist
$$\frac{a+c}{b+d}.$$
Er liegt strikt zwischen den Endpunkten:
$$\frac{a}{b} \lt \frac{a+c}{b+d} \lt \frac{c}{d}.$$
Außerdem ist er automatisch vollständig gekürzt. Würde eine Zahl \(g\) sowohl \(a+c\) als auch \(b+d\) teilen, dann würde \(g\) auch
$$d(a+c)-c(b+d)=ad-bc=-1$$
teilen, also muss \(g=1\) sein. Darum braucht der Algorithmus nirgendwo einen ggT-Test.
Die Abbruchbedingung des Codes beruht auf einem stärkeren Satz: Unter allen reduzierten Brüchen im offenen Intervall zwischen \(\frac{a}{b}\) und \(\frac{c}{d}\) besitzt der Mediant den kleinsten möglichen Nenner.
Sei dazu \(\frac{x}{y}\) ein beliebiger reduzierter Bruch mit
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}.$$
Definiere
$$m=cy-dx,\qquad n=bx-ay.$$
Wegen der strikten Lage im Intervall sind beide Zahlen positiv. Mit \(bc-ad=1\) folgt
$$ma+nc = a(cy-dx)+c(bx-ay)=x(bc-ad)=x,$$
$$mb+nd = b(cy-dx)+d(bx-ay)=y(bc-ad)=y.$$
Also gilt
$$x=ma+nc,\qquad y=mb+nd.$$
Da \(m,n \ge 1\), erhält man sofort
$$y=mb+nd \ge b+d.$$
Gleichheit ist nur für \(m=n=1\) möglich, also genau beim Mediant \(\frac{a+c}{b+d}\). Wenn also \(b+d\gt N\) ist, dann existiert in diesem Intervall überhaupt kein reduzierter Bruch mit Nenner \(\le N\), und der gesamte Teilbaum kann verworfen werden.
Fügt man den Mediant ein, zerfällt das Intervall in
$$\left(\frac{a}{b},\frac{a+c}{b+d}\right), \qquad \left(\frac{a+c}{b+d},\frac{c}{d}\right).$$
Beide Kinder erfüllen wieder dieselbe Determinantenbedingung:
$$b(a+c)-a(b+d)=bc-ad=1,$$
$$ (b+d)c-(a+c)d=bc-ad=1.$$
Damit lässt sich dieselbe Argumentation rekursiv fortsetzen. Jeder zulässige reduzierte Bruch liegt entweder links vom Mediant oder rechts davon, niemals in beiden Teilintervallen zugleich. Die Rekursion zerlegt die Menge also ohne Überschneidungen, und jeder gesuchte Bruch erscheint genau einmal.
Sei
$$T_N\!\left(\frac{a}{b},\frac{c}{d}\right)$$
die Anzahl der reduzierten Brüche \(\frac{x}{y}\) mit \(y\le N\) und
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d},$$
wobei \(bc-ad=1\) gilt. Dann lautet die exakte Rekursion
$$ T_N\!\left(\frac{a}{b},\frac{c}{d}\right)= \begin{cases} 0, & b+d \gt N,\\[4pt] 1 + T_N\!\left(\frac{a}{b},\frac{a+c}{b+d}\right) + T_N\!\left(\frac{a+c}{b+d},\frac{c}{d}\right), & b+d \le N. \end{cases} $$
Die gesuchte Antwort ist also
$$T_{12000}\!\left(\frac13,\frac12\right).$$
Das ist keine bloße Heuristik, sondern eine exakte Zerlegung aller reduzierten Brüche im Zielintervall entlang der Struktur des Stern-Brocot-Baums.
Wir beginnen mit \(\frac13\) und \(\frac12\). Deren Mediant ist \(\frac25\), und weil \(5 \le 8\), zählt \(\frac25\) mit.
Das linke Kindintervall ist \(\left(\frac13,\frac25\right)\). Sein Mediant ist \(\frac38\), und auch \(8 \le 8\), also zählt \(\frac38\) ebenfalls. Die nächsten Medianten darunter hätten die Nenner \(11\) und \(13\); dieser Ast endet also dort.
Das rechte Kindintervall ist \(\left(\frac25,\frac12\right)\). Sein Mediant ist \(\frac37\), und \(7 \le 8\), also zählt auch dieser Bruch. Die beiden Kinder darunter hätten die Nenner \(12\) und \(9\), also zu groß.
Die vollständige Menge lautet damit
$$\left\{\frac38,\frac25,\frac37\right\},$$
also ist die Anzahl gleich \(3\). Genau das ist der erste Prüfpunkt der Implementierungen. Für \(N=12\) wächst die Anzahl auf \(7\), was dem zweiten Prüfpunkt entspricht.
Die C++-, Python- und Java-Implementierungen starten alle mit demselben Zustand: dem Intervall mit den Endpunkten \(\frac13\) und \(\frac12\). Für jedes Intervall wird durch bloße Addition der Endpunktzähler und -nenner der Mediant gebildet. Ist dessen Nenner größer als die Schranke, liefert dieser Ast \(0\). Andernfalls zählt der Mediant selbst und die Suche setzt sich in den beiden Kindintervallen fort.
In C++ und Java ist diese Logik als rekursive Tiefensuche formuliert. Die Python-Version führt dieselbe Traversierung mit einem expliziten Stack von Intervallen aus. Dadurch wird die Rekursionstiefe des Interpreters vermieden, während die zugrunde liegende Rekursion mathematisch unverändert bleibt.
Vor dem Vollfall \(N=12000\) prüfen die Implementierungen die kleinen Testwerte \(N=8 \mapsto 3\) und \(N=12 \mapsto 7\). Diese Kontrollwerte bestätigen, dass Intervall-Split, Abbruchregel und Eins-pro-Mediant-Zählung korrekt zusammenpassen.
Jeder gültige Bruch im Intervall wird genau einmal erzeugt, und jeder verworfene Ast endet nach konstantem Aufwand. Bezeichnet \(A(N)\) die Anzahl der reduzierten Brüche in \(\left(\frac13,\frac12\right)\) mit Nenner höchstens \(N\), dann beträgt die Laufzeit \(O(A(N))\). Für dieses Problem wächst \(A(N)\) in der Größenordnung von \(N^2\), also ist das Verfahren effektiv quadratisch in der Schranke, vermeidet aber alle unnötigen ggT-Tests über irrelevante Kandidaten.
Der Speicherbedarf ist \(O(H)\), wobei \(H\) die Tiefe des Suchstapels ist. In den rekursiven C++- und Java-Versionen ist das die Aufruftiefe, in Python die Größe des expliziten Stacks. Im Worst Case ist \(H=O(N)\), weil manche Äste die Nenner nur langsam wachsen lassen. Trotzdem bleibt der Speicherbedarf sehr klein im Vergleich zu einer direkten Enumeration aller möglichen Zähler-Nenner-Paare.
İstenen şey, şu koşulu sağlayan sadeleştirilmiş kesirlerin sayısıdır:
$$\frac{1}{3} \lt \frac{a}{b} \lt \frac{1}{2}, \qquad b \le 12000.$$
Yani paydası sınırlı bütün kesirleri saymıyoruz; sadece bu aralıkta kalan ve zaten indirgenmiş olanları sayıyoruz. Uygulamalar bu yüzden her paydayı gezip EBOB kontrolü yapmıyor. Bunun yerine \(\left(\frac13,\frac12\right)\) aralığını Stern-Brocot ağacındaki bir alt aralık olarak görüyor ve içeride oluşan uygun medyanları tek tek sayıyor.
Doğru durum uzayı, uç noktaları komşu indirgenmiş kesirlerden oluşan bir aralıktır. Böyle bir aralıkta içeride ortaya çıkabilecek ilk kesir, uçların medyanıdır; kullanılan özyineleme doğrudan bu gözlemden gelir.
Güncel aralığı
$$\frac{a}{b} \lt \frac{c}{d}, \qquad bc-ad=1$$
şeklinde düşünelim. Başlangıç aralığı \(\frac13 \lt \frac12\) zaten bu özelliği taşır, çünkü \(3\cdot 1 - 1\cdot 2 = 1\). Bu anlamda determinantı \(1\) olan kesir çiftleri Farey dizisinde komşudur ve Stern-Brocot ağacında yan yanadır.
Bu iki ucun medyanı
$$\frac{a+c}{b+d}$$
olur. Bu kesir uçların tam arasında yer alır:
$$\frac{a}{b} \lt \frac{a+c}{b+d} \lt \frac{c}{d}.$$
Ayrıca otomatik olarak indirgenmiştir. Eğer bir \(g\) sayısı hem \(a+c\) hem de \(b+d\) sayısını bölseydi, şu ifadeyi de bölmesi gerekirdi:
$$d(a+c)-c(b+d)=ad-bc=-1.$$
Dolayısıyla \(g=1\) olmak zorundadır. Bu yüzden algoritmanın hiçbir noktasında ayrıca EBOB hesabı yapılmaz.
Koddaki budama kuralı daha güçlü bir gerçeğe dayanır: \(\frac{a}{b}\) ile \(\frac{c}{d}\) arasındaki tüm indirgenmiş kesirler içinde en küçük paydaya sahip olan tek kesir medyandır.
Aralık içinde herhangi bir indirgenmiş \(\frac{x}{y}\) kesri alalım:
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}.$$
Şimdi
$$m=cy-dx,\qquad n=bx-ay$$
tanımlarını yapalım. Kesir aralığın içinde olduğu için bu iki sayı pozitiftir. \(bc-ad=1\) eşitliğiyle birlikte
$$ma+nc = a(cy-dx)+c(bx-ay)=x(bc-ad)=x,$$
$$mb+nd = b(cy-dx)+d(bx-ay)=y(bc-ad)=y$$
elde edilir. Yani
$$x=ma+nc,\qquad y=mb+nd.$$
\(m,n \ge 1\) olduğundan hemen
$$y=mb+nd \ge b+d$$
sonucuna ulaşırız. Eşitlik ancak \(m=n=1\) iken olur; bu da tam olarak \(\frac{x}{y}=\frac{a+c}{b+d}\) demektir. Dolayısıyla \(b+d\gt N\) ise bu aralıkta paydası en fazla \(N\) olan hiçbir indirgenmiş kesir yoktur ve ilgili dal doğrudan kesilebilir.
Medyan eklendiğinde aralık ikiye ayrılır:
$$\left(\frac{a}{b},\frac{a+c}{b+d}\right), \qquad \left(\frac{a+c}{b+d},\frac{c}{d}\right).$$
Bu iki alt aralık da aynı determinant koşulunu korur:
$$b(a+c)-a(b+d)=bc-ad=1,$$
$$ (b+d)c-(a+c)d=bc-ad=1.$$
Böylece aynı mantık özyinelemeli olarak sürer. Uygun her indirgenmiş kesir ya medyanın solunda kalır ya sağında kalır; iki alt aralıkta birden yer alamaz. Bu nedenle arama uzayı çakışmasız biçimde parçalanır ve hedef aralıktaki her kesir tam bir kez sayılır.
Şu niceliği tanımlayalım:
$$T_N\!\left(\frac{a}{b},\frac{c}{d}\right).$$
Bu ifade, \(bc-ad=1\) değişmezi altında
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}, \qquad y\le N$$
koşullarını sağlayan indirgenmiş \(\frac{x}{y}\) kesirlerinin sayısını göstersin. O zaman tam özyineleme
$$ T_N\!\left(\frac{a}{b},\frac{c}{d}\right)= \begin{cases} 0, & b+d \gt N,\\[4pt] 1 + T_N\!\left(\frac{a}{b},\frac{a+c}{b+d}\right) + T_N\!\left(\frac{a+c}{b+d},\frac{c}{d}\right), & b+d \le N. \end{cases} $$
şeklindedir. Sorunun cevabı da
$$T_{12000}\!\left(\frac13,\frac12\right)$$
olur. Bu, rastgele bir ağaç dolaşımı değil; Stern-Brocot yapısına göre tüm hedef kesirlerin tam ayrışımıdır.
\(\frac13\) ile \(\frac12\) arasından başlarız. İlk medyan \(\frac25\) olur ve \(5 \le 8\) olduğu için sayılır.
Sol alt aralık \(\left(\frac13,\frac25\right)\) olur. Bunun medyanı \(\frac38\) ve \(8 \le 8\) olduğu için bu da sayılır. Bunun altındaki sonraki medyanların paydaları \(11\) ve \(13\) çıkar; dolayısıyla o dal burada durur.
Sağ alt aralık \(\left(\frac25,\frac12\right)\) olur. Bunun medyanı \(\frac37\) ve \(7 \le 8\) olduğu için o da sayılır. Çocuk dalların paydaları \(12\) ve \(9\) olduğundan onlar da elenir.
Dolayısıyla tüm küme
$$\left\{\frac38,\frac25,\frac37\right\}$$
olur ve sayı \(3\) çıkar. Bu, uygulamalardaki ilk kontrol örneğidir. Aynı ağaç \(N=12\) için genişletildiğinde sayı \(7\) olur; ikinci kontrol de bunu doğrular.
C++, Python ve Java uygulamalarının hepsi aynı başlangıç durumuyla başlar: uçları \(\frac13\) ve \(\frac12\) olan aralık. Her adımda uçların payları ve paydaları toplanarak medyan oluşturulur. Yeni payda üst sınırı aşıyorsa o daldan \(0\) döner. Aşmıyorsa medyanın kendisi için bir sayı eklenir ve arama sol ve sağ alt aralıklarda sürdürülür.
C++ ve Java sürümleri bu mantığı doğrudan özyinelemeli derinlik öncelikli arama olarak yazar. Python sürümü ise aynı aralık çiftlerini açık bir yığında tutar. Böylece yorumlayıcı özyineleme sınırına takılmadan tamamen aynı matematik yürütülmüş olur.
Tam çözümden önce \(N=8 \mapsto 3\) ve \(N=12 \mapsto 7\) kontrolleri yapılır. Bu küçük testler, aralık bölme mantığının, budama koşulunun ve her geçerli medyan için bir kez sayma fikrinin doğru uygulandığını gösterir.
Aralıktaki her geçerli kesir tam bir kez üretilir ve reddedilen her dal sabit sayıda işlemden sonra sonlanır. \(\left(\frac13,\frac12\right)\) aralığında paydası en fazla \(N\) olan indirgenmiş kesir sayısına \(A(N)\) dersek, çalışma süresi \(O(A(N))\) olur. Bu problemde \(A(N)\) büyüklük olarak \(N^2\) mertebesindedir; yani yöntem pratikte ikinci dereceden büyür, ama ilgisiz adaylar üzerinde boş yere EBOB testi yapmaz.
Bellek kullanımı \(O(H)\) düzeyindedir; burada \(H\) arama yığınının derinliğidir. Özyinelemeli C++ ve Java sürümlerinde bu çağrı derinliğidir, Python sürümünde ise açık yığın boyudur. En kötü durumda bazı dallarda paydalar yavaş arttığı için \(H=O(N)\) olabilir; yine de bu maliyet, tüm pay-payda adaylarını açıkça taramaya göre çok küçüktür.
Hay que contar las fracciones reducidas \(a/b\) que cumplen
$$\frac{1}{3} \lt \frac{a}{b} \lt \frac{1}{2}, \qquad b \le 12000.$$
Por lo tanto, no se trata de enumerar todas las fracciones con denominador acotado, sino solo las irreducibles que caen dentro de ese intervalo concreto. Las implementaciones no recorren todos los denominadores ni comprueban coprimalidad con \(\gcd\). En su lugar, interpretan \(\left(\frac13,\frac12\right)\) como un intervalo del árbol de Stern-Brocot y cuentan los mediantes válidos que aparecen dentro de él.
El estado correcto es un intervalo cuyos extremos son fracciones reducidas vecinas. En un intervalo así, la siguiente fracción interior posible es el mediant de los extremos, y de esa observación sale directamente la recurrencia utilizada por la implementación.
Consideremos el intervalo actual
$$\frac{a}{b} \lt \frac{c}{d}, \qquad bc-ad=1.$$
El intervalo inicial \(\frac13 \lt \frac12\) ya cumple esta propiedad, porque \(3\cdot 1 - 1\cdot 2 = 1\). Las fracciones con determinante \(1\) en este sentido son vecinas en una sucesión de Farey y vértices adyacentes en el árbol de Stern-Brocot.
El mediant de los extremos es
$$\frac{a+c}{b+d}.$$
Esta fracción queda estrictamente entre ambas:
$$\frac{a}{b} \lt \frac{a+c}{b+d} \lt \frac{c}{d}.$$
Además ya está reducida. Si un entero \(g\) dividiera a la vez \(a+c\) y \(b+d\), también dividiría
$$d(a+c)-c(b+d)=ad-bc=-1,$$
de modo que forzosamente \(g=1\). Por eso el algoritmo no necesita hacer pruebas de \(\gcd\).
La regla de poda del código usa un hecho más fuerte: entre todas las fracciones reducidas estrictamente interiores al intervalo, el mediant es la única que tiene denominador mínimo.
Tomemos una fracción reducida cualquiera \(\frac{x}{y}\) con
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}.$$
Definimos
$$m=cy-dx,\qquad n=bx-ay.$$
Ambos números son positivos porque \(\frac{x}{y}\) está estrictamente dentro del intervalo. Usando \(bc-ad=1\), obtenemos
$$ma+nc = a(cy-dx)+c(bx-ay)=x(bc-ad)=x,$$
$$mb+nd = b(cy-dx)+d(bx-ay)=y(bc-ad)=y.$$
Por tanto
$$x=ma+nc,\qquad y=mb+nd.$$
Como \(m,n \ge 1\), se sigue que
$$y=mb+nd \ge b+d.$$
La igualdad solo ocurre cuando \(m=n=1\), es decir, precisamente para \(\frac{x}{y}=\frac{a+c}{b+d}\). Así, si \(b+d\gt N\), no puede existir ninguna fracción reducida interior con denominador \(\le N\), y toda esa rama puede descartarse de inmediato.
Cuando insertamos el mediant, el intervalo se parte en
$$\left(\frac{a}{b},\frac{a+c}{b+d}\right), \qquad \left(\frac{a+c}{b+d},\frac{c}{d}\right).$$
Ambos hijos siguen cumpliendo la misma condición:
$$b(a+c)-a(b+d)=bc-ad=1,$$
$$ (b+d)c-(a+c)d=bc-ad=1.$$
Eso permite repetir exactamente el mismo razonamiento. Toda fracción reducida admisible cae o bien a la izquierda del mediant o bien a la derecha, nunca en ambas partes. Así, la recursión particiona el conjunto sin solapamientos y cada fracción del intervalo objetivo aparece exactamente una vez.
Definamos
$$T_N\!\left(\frac{a}{b},\frac{c}{d}\right)$$
como el número de fracciones reducidas \(\frac{x}{y}\) con \(y\le N\) tales que
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d},$$
bajo el invariante \(bc-ad=1\). Entonces la recurrencia exacta es
$$ T_N\!\left(\frac{a}{b},\frac{c}{d}\right)= \begin{cases} 0, & b+d \gt N,\\[4pt] 1 + T_N\!\left(\frac{a}{b},\frac{a+c}{b+d}\right) + T_N\!\left(\frac{a+c}{b+d},\frac{c}{d}\right), & b+d \le N. \end{cases} $$
La respuesta pedida es, por tanto,
$$T_{12000}\!\left(\frac13,\frac12\right).$$
No es un recorrido heurístico del árbol, sino una descomposición exacta de todas las fracciones reducidas del intervalo siguiendo la estructura de Stern-Brocot.
Comenzamos con \(\frac13\) y \(\frac12\). Su mediant es \(\frac25\), y como \(5 \le 8\), esa fracción cuenta.
El subintervalo izquierdo es \(\left(\frac13,\frac25\right)\). Su mediant es \(\frac38\), y también cumple \(8 \le 8\), así que añade otro conteo. Los siguientes mediants por debajo tendrían denominadores \(11\) y \(13\), luego esa rama termina ahí.
El subintervalo derecho es \(\left(\frac25,\frac12\right)\). Su mediant es \(\frac37\), y como \(7 \le 8\), también cuenta. Sus hijos tendrían denominadores \(12\) y \(9\), ambos demasiado grandes.
El conjunto completo es entonces
$$\left\{\frac38,\frac25,\frac37\right\},$$
de modo que el total es \(3\). Ese es exactamente el primer punto de control usado por las implementaciones. Al ampliar el mismo árbol hasta \(N=12\), el recuento sube a \(7\), que coincide con el segundo control.
Las implementaciones en C++, Python y Java parten del mismo estado inicial: el intervalo con extremos \(\frac13\) y \(\frac12\). Para cada intervalo, calculan el numerador y el denominador del mediant mediante sumas simples. Si el nuevo denominador supera el límite, esa rama aporta \(0\). Si no, el mediant suma una unidad y la exploración continúa en los subintervalos izquierdo y derecho.
Las versiones de C++ y Java expresan esta idea como una búsqueda en profundidad recursiva. La versión de Python recorre exactamente los mismos intervalos, pero usa una pila explícita para evitar problemas de profundidad de recursión sin cambiar la matemática subyacente.
Antes del caso completo \(N=12000\), el código verifica los casos pequeños \(N=8 \mapsto 3\) y \(N=12 \mapsto 7\). Esos puntos de control confirman que la división del intervalo, la condición de corte y la regla de contar una vez por mediant están implementadas correctamente.
Cada fracción válida del intervalo se genera exactamente una vez, y cada rama rechazada termina tras un trabajo constante. Si \(A(N)\) es el número de fracciones reducidas en \(\left(\frac13,\frac12\right)\) con denominador a lo sumo \(N\), entonces el tiempo total es \(O(A(N))\). En este problema, \(A(N)\) crece del orden de \(N^2\), así que el algoritmo es efectivamente cuadrático en el límite, pero evita comprobar \(\gcd\) sobre candidatos que nunca llegarían a contribuir.
La memoria es \(O(H)\), donde \(H\) es la profundidad de la pila de búsqueda. En C++ y Java ese coste aparece como profundidad de recursión; en Python, como tamaño de la pila explícita. En el peor caso, \(H=O(N)\) porque hay ramas donde los denominadores aumentan lentamente, pero aun así el almacenamiento es muy pequeño frente a una enumeración directa de todos los numeradores y denominadores posibles.
题目要求统计所有满足下式的既约分数 \(a/b\)：
$$\frac{1}{3} \lt \frac{a}{b} \lt \frac{1}{2}, \qquad b \le 12000.$$
也就是说，我们并不是要枚举所有分母不超过 \(12000\) 的分数，而是只统计严格落在这个区间中的最简真分数。实现并没有按分母逐个枚举再做 \(\gcd\) 判定，而是把 \(\left(\frac13,\frac12\right)\) 看成 Stern-Brocot 树中的一个区间，只在这个区间里递归生成并统计合法的中项分数。
最合适的状态，不是“当前分母是多少”，而是“当前区间的两个端点是谁”。只要端点是一对相邻的既约分数，那么区间里最先出现、也最重要的内部候选就是它们的 mediant。题目的整个递推公式正是从这里展开的。
设当前区间为
$$\frac{a}{b} \lt \frac{c}{d}, \qquad bc-ad=1.$$
初始区间 \(\frac13 \lt \frac12\) 本身就满足这个条件，因为 \(3\cdot 1 - 1\cdot 2 = 1\)。在 Farey 序列里，这样的两项是相邻项；在 Stern-Brocot 树里，它们对应相邻的边界。
这两个端点的 mediant 是
$$\frac{a+c}{b+d}.$$
它必然严格落在两端之间：
$$\frac{a}{b} \lt \frac{a+c}{b+d} \lt \frac{c}{d}.$$
更重要的是，它天然已经是既约分数。因为如果某个整数 \(g\) 同时整除 \(a+c\) 和 \(b+d\)，那么它也必须整除
$$d(a+c)-c(b+d)=ad-bc=-1,$$
这只可能发生在 \(g=1\)。因此算法根本不需要额外做 \(\gcd\) 检查。
代码中的剪枝条件依赖于一个更强的事实：在区间 \(\left(\frac{a}{b},\frac{c}{d}\right)\) 内部，所有既约分数里分母最小的那个，恰好就是 mediant，而且它是唯一的。
任取一个满足
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}$$
的既约分数 \(\frac{x}{y}\)。定义
$$m=cy-dx,\qquad n=bx-ay.$$
由于 \(\frac{x}{y}\) 严格位于区间内部，所以 \(m\) 和 \(n\) 都是正整数。再利用 \(bc-ad=1\)，可得
$$ma+nc = a(cy-dx)+c(bx-ay)=x(bc-ad)=x,$$
$$mb+nd = b(cy-dx)+d(bx-ay)=y(bc-ad)=y.$$
因此
$$x=ma+nc,\qquad y=mb+nd.$$
因为 \(m,n \ge 1\)，于是马上得到
$$y=mb+nd \ge b+d.$$
只有当 \(m=n=1\) 时才会取等号，这时 \(\frac{x}{y}\) 恰好就是 \(\frac{a+c}{b+d}\)。所以 mediant 是区间内分母最小的唯一既约分数。由此立刻得到关键剪枝：如果 \(b+d\gt N\)，那么该区间里根本不存在任何分母不超过 \(N\) 的合法分数，整个分支可以直接返回 \(0\)。
插入 mediant 之后，原区间被分成两个子区间：
$$\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,$$
$$ (b+d)c-(a+c)d=bc-ad=1.$$
因此同样的论证可以一层层递归下去。任意一个目标既约分数，不是在 mediant 左边，就是在 mediant 右边，而且不可能同时属于两边。也就是说，整个搜索空间被无重叠地拆分开来，每个符合条件的分数都只会被计算一次。
定义
$$T_N\!\left(\frac{a}{b},\frac{c}{d}\right)$$
表示在不变量 \(bc-ad=1\) 下，所有满足
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}, \qquad y\le N$$
的既约分数 \(\frac{x}{y}\) 的个数。那么精确递推就是
$$ T_N\!\left(\frac{a}{b},\frac{c}{d}\right)= \begin{cases} 0, & b+d \gt N,\\[4pt] 1 + T_N\!\left(\frac{a}{b},\frac{a+c}{b+d}\right) + T_N\!\left(\frac{a+c}{b+d},\frac{c}{d}\right), & b+d \le N. \end{cases} $$
题目的答案因此就是
$$T_{12000}\!\left(\frac13,\frac12\right).$$
这不是一种近似或经验性的树遍历，而是对目标区间内全部既约分数的精确分解。
从 \(\frac13\) 和 \(\frac12\) 开始。它们的 mediant 是 \(\frac25\)，分母 \(5 \le 8\)，所以先计入一个。
左侧子区间是 \(\left(\frac13,\frac25\right)\)。它的 mediant 是 \(\frac38\)，分母 \(8 \le 8\)，所以再计入一个。继续往下时，后继 mediant 的分母会变成 \(11\) 和 \(13\)，都超过上界，因此左支到此停止。
右侧子区间是 \(\left(\frac25,\frac12\right)\)。它的 mediant 是 \(\frac37\)，分母 \(7 \le 8\)，也要计入。它的两个子区间对应的下一个 mediant 分母分别是 \(12\) 和 \(9\)，同样都超界，所以右支也停止。
因此全部合法分数恰好是
$$\left\{\frac38,\frac25,\frac37\right\},$$
总数为 \(3\)。这正好对应实现中的第一个检查点。把同一棵子树继续展开到 \(N=12\) 时，计数会变成 \(7\)，对应第二个检查点。
C++、Python 和 Java 的实现都从同一个初始状态开始，也就是端点为 \(\frac13\) 和 \(\frac12\) 的区间。对每个区间，程序只做加法就能得到 mediant 的分子和分母。如果新分母超过上界，该分支直接贡献 \(0\)。如果没有超过，就先把这个 mediant 计入答案，然后分别进入左、右两个子区间继续处理。
C++ 和 Java 版本把这件事直接写成递归的深度优先搜索。Python 版本用一个显式栈保存尚未处理的区间，数学上仍然完全对应同一个递推，只是避免了解释器的递归深度限制。
在求解完整的 \(N=12000\) 之前，代码先验证两个小规模结果：\(N=8\) 时答案为 \(3\)，\(N=12\) 时答案为 \(7\)。这两个检查点正好对应上面的树展开过程，因此能确认区间分裂、剪枝规则和“一次 mediant 记一次”的实现都是正确的。
区间中的每一个合法分数只会生成一次，而每个被剪掉的分支也只需要常数时间就能结束。如果用 \(A(N)\) 表示 \(\left(\frac13,\frac12\right)\) 中分母不超过 \(N\) 的既约分数个数，那么总时间复杂度就是 \(O(A(N))\)。对这个问题而言，\(A(N)\) 的增长量级是 \(N^2\)，所以整体上可以看成与上界平方同阶，但它避免了对大量无关候选做 \(\gcd\) 判断。
空间复杂度是 \(O(H)\)，其中 \(H\) 是搜索栈的最大深度。递归版 C++ 和 Java 的 \(H\) 体现为调用栈深度，Python 则体现为显式栈大小。最坏情况下某些分支的分母增长较慢，因此 \(H\) 可能达到 \(O(N)\)，但即便如此，所需内存仍然远小于直接枚举全部分子分母组合。
Нужно посчитать количество несократимых дробей \(a/b\), для которых выполняется
$$\frac{1}{3} \lt \frac{a}{b} \lt \frac{1}{2}, \qquad b \le 12000.$$
То есть нас интересуют не все дроби с ограниченным знаменателем, а только приведенные дроби, лежащие внутри одного конкретного интервала. Поэтому реализации не перебирают все знаменатели и не проверяют взаимную простоту через \(\gcd\). Вместо этого они рассматривают \(\left(\frac13,\frac12\right)\) как интервал в дереве Штерна-Броко и считают допустимые медианты внутри него.
Правильное состояние здесь задается не отдельным знаменателем, а текущим интервалом, концы которого являются соседними приведенными дробями. В таком интервале следующей возможной внутренней дробью является mediant концов, и именно это приводит к рекуррентной формуле, используемой в коде.
Рассмотрим интервал
$$\frac{a}{b} \lt \frac{c}{d}, \qquad bc-ad=1.$$
Начальный интервал \(\frac13 \lt \frac12\) уже обладает этим свойством, поскольку \(3\cdot 1 - 1\cdot 2 = 1\). Такие пары являются соседними дробями в последовательности Фарея и соседними границами в дереве Штерна-Броко.
Их mediant равен
$$\frac{a+c}{b+d}.$$
Он строго лежит между концами:
$$\frac{a}{b} \lt \frac{a+c}{b+d} \lt \frac{c}{d}.$$
Кроме того, он автоматически несократим. Если бы некоторое число \(g\) делило и \(a+c\), и \(b+d\), то оно делило бы и
$$d(a+c)-c(b+d)=ad-bc=-1,$$
что невозможно, кроме случая \(g=1\). Поэтому алгоритму не нужен отдельный расчет \(\gcd\).
Правило остановки в коде основано на более сильном утверждении: среди всех несократимых дробей строго внутри интервала \(\left(\frac{a}{b},\frac{c}{d}\right)\) mediant имеет наименьший возможный знаменатель, и такой знаменатель достигается только у него.
Пусть \(\frac{x}{y}\) - любая несократимая дробь, для которой
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}.$$
Определим
$$m=cy-dx,\qquad n=bx-ay.$$
Обе величины положительны, потому что \(\frac{x}{y}\) находится строго внутри интервала. Используя равенство \(bc-ad=1\), получаем
$$ma+nc = a(cy-dx)+c(bx-ay)=x(bc-ad)=x,$$
$$mb+nd = b(cy-dx)+d(bx-ay)=y(bc-ad)=y.$$
Следовательно,
$$x=ma+nc,\qquad y=mb+nd.$$
Так как \(m,n \ge 1\), сразу следует
$$y=mb+nd \ge b+d.$$
Равенство возможно только при \(m=n=1\), то есть ровно для дроби \(\frac{x}{y}=\frac{a+c}{b+d}\). Значит, если \(b+d\gt N\), то внутри интервала вообще нет допустимой дроби со знаменателем \(\le N\), и всю ветвь можно отбросить сразу.
После вставки mediant интервал распадается на два подинтервала:
$$\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,$$
$$ (b+d)c-(a+c)d=bc-ad=1.$$
Поэтому рассуждение можно повторять рекурсивно. Каждая подходящая несократимая дробь лежит либо слева от mediant, либо справа, но не в обеих частях сразу. Таким образом, множество всех решений разбивается без пересечений, и каждая нужная дробь учитывается ровно один раз.
Обозначим через
$$T_N\!\left(\frac{a}{b},\frac{c}{d}\right)$$
число несократимых дробей \(\frac{x}{y}\), удовлетворяющих условиям
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}, \qquad y\le N,$$
при инварианте \(bc-ad=1\). Тогда точная рекурсия имеет вид
$$ T_N\!\left(\frac{a}{b},\frac{c}{d}\right)= \begin{cases} 0, & b+d \gt N,\\[4pt] 1 + T_N\!\left(\frac{a}{b},\frac{a+c}{b+d}\right) + T_N\!\left(\frac{a+c}{b+d},\frac{c}{d}\right), & b+d \le N. \end{cases} $$
Следовательно, ответ к задаче равен
$$T_{12000}\!\left(\frac13,\frac12\right).$$
Это не приближенный обход дерева, а точное разбиение всех приведенных дробей внутри нужного интервала по структуре дерева Штерна-Броко.
Начинаем с \(\frac13\) и \(\frac12\). Их mediant равен \(\frac25\), и поскольку \(5 \le 8\), эта дробь учитывается.
Левый подинтервал - \(\left(\frac13,\frac25\right)\). Его mediant равен \(\frac38\), и здесь тоже \(8 \le 8\), значит, добавляется еще одна дробь. Следующие mediant ниже по этому пути имели бы знаменатели \(11\) и \(13\), поэтому левая ветвь на этом заканчивается.
Правый подинтервал - \(\left(\frac25,\frac12\right)\). Его mediant равен \(\frac37\), и \(7 \le 8\), значит, он тоже учитывается. У его детей знаменатели были бы \(12\) и \(9\), то есть оба слишком велики.
Итак, полный набор равен
$$\left\{\frac38,\frac25,\frac37\right\},$$
поэтому ответ равен \(3\). Это в точности первый контрольный пример из реализаций. Если продолжить то же дерево до \(N=12\), получится \(7\), что совпадает со вторым контрольным значением.
Во всех трех реализациях, на C++, Python и Java, стартовое состояние одинаково: интервал с концами \(\frac13\) и \(\frac12\). Для каждого интервала программа просто складывает числители и знаменатели концов, получая mediant. Если новый знаменатель превышает предел, эта ветвь дает \(0\). Иначе сам mediant добавляет единицу к ответу, после чего поиск продолжается в левом и правом подинтервалах.
В версиях на C++ и Java эта логика записана как рекурсивный обход в глубину. Версия на Python проходит те же интервалы с явным стеком, что избавляет от ограничений глубины рекурсии, но сохраняет ту же самую математику и тот же итоговый подсчет.
Перед полным запуском для \(N=12000\) код проверяет два маленьких контрольных случая: \(N=8 \mapsto 3\) и \(N=12 \mapsto 7\). Они подтверждают правильность разбиения интервала, условия отсечения и принципа "каждый допустимый mediant считается один раз".
Каждая допустимая дробь внутри интервала генерируется ровно один раз, а каждая отброшенная ветвь завершается после константного числа операций. Если \(A(N)\) обозначает количество несократимых дробей в \(\left(\frac13,\frac12\right)\) со знаменателем не больше \(N\), то время работы равно \(O(A(N))\). Для этой задачи \(A(N)\) растет как \(N^2\), так что метод фактически квадратичен по ограничению, но не тратит время на лишние проверки \(\gcd\) для неподходящих кандидатов.
Память составляет \(O(H)\), где \(H\) - глубина поискового стека. В рекурсивных версиях на C++ и Java это глубина вызовов, а в Python - размер явного стека. В худшем случае \(H=O(N)\), потому что на некоторых ветвях знаменатели растут медленно. Тем не менее объем памяти остается очень маленьким по сравнению с прямым перебором всех возможных числителей и знаменателей.
المطلوب هو عد الكسور المختزلة \(a/b\) التي تحقق
$$\frac{1}{3} \lt \frac{a}{b} \lt \frac{1}{2}, \qquad b \le 12000.$$
إذن نحن لا نحصي جميع الكسور ذات المقامات المحدودة، بل فقط الكسور في أبسط صورة والتي تقع داخل هذا المجال المحدد. لهذا السبب لا تقوم التطبيقات بالمرور على كل مقام ثم فحص \(\gcd\). بدلاً من ذلك تتعامل مع \(\left(\frac13,\frac12\right)\) باعتباره مجالًا داخل شجرة Stern-Brocot، ثم تعد جميع الوسائط الصالحة التي تظهر داخله.
الحالة الرياضية الطبيعية هنا ليست "ما هو المقام الحالي؟" بل "ما هما طرفا المجال الحالي؟". إذا كان طرفا المجال كسرين مختزلين متجاورين، فإن أول كسر داخلي محتمل هو mediant الخاص بهما، ومن هذه الملاحظة يخرج التكرار المستخدم في الحل كله.
لنفرض أن المجال الحالي هو
$$\frac{a}{b} \lt \frac{c}{d}, \qquad bc-ad=1.$$
المجال الابتدائي \(\frac13 \lt \frac12\) يحقق هذه الخاصية بالفعل لأن \(3\cdot 1 - 1\cdot 2 = 1\). مثل هذين الكسرين يكونان جارين في متتالية Farey، كما يمثلان حدين متجاورين في شجرة Stern-Brocot.
الـ mediant للطرفين هو
$$\frac{a+c}{b+d}.$$
وهذا الكسر يقع دائمًا بين الطرفين:
$$\frac{a}{b} \lt \frac{a+c}{b+d} \lt \frac{c}{d}.$$
وهو أيضًا مختزل تلقائيًا. فإذا كان هناك عدد صحيح \(g\) يقسم كلًا من \(a+c\) و\(b+d\)، فسوف يقسم كذلك
$$d(a+c)-c(b+d)=ad-bc=-1,$$
وهذا لا يحدث إلا عند \(g=1\). لذلك لا تحتاج الخوارزمية إلى أي اختبار إضافي للقاسم المشترك الأكبر.
قاعدة الإيقاف في الشيفرة تعتمد على حقيقة أقوى: من بين جميع الكسور المختزلة الواقعة strictly داخل المجال \(\left(\frac{a}{b},\frac{c}{d}\right)\)، يكون mediant هو الكسر الوحيد ذو أصغر مقام ممكن.
خذ أي كسر مختزل \(\frac{x}{y}\) يحقق
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}.$$
عرّف
$$m=cy-dx,\qquad n=bx-ay.$$
كلا العددين موجبان لأن \(\frac{x}{y}\) يقع strictly داخل المجال. وباستخدام العلاقة \(bc-ad=1\) نحصل على
$$ma+nc = a(cy-dx)+c(bx-ay)=x(bc-ad)=x,$$
$$mb+nd = b(cy-dx)+d(bx-ay)=y(bc-ad)=y.$$
أي أن
$$x=ma+nc,\qquad y=mb+nd.$$
وبما أن \(m,n \ge 1\)، فإن
$$y=mb+nd \ge b+d.$$
وتتحقق المساواة فقط عندما \(m=n=1\)، أي عندما يكون \(\frac{x}{y}=\frac{a+c}{b+d}\). لذلك فإن mediant هو الكسر الداخلي الوحيد ذو أصغر مقام. ومن هنا تأتي قاعدة القطع الأساسية: إذا كان \(b+d\gt N\)، فلا يوجد داخل هذا المجال أي كسر مختزل مقامه لا يتجاوز \(N\)، ويمكن حذف هذا الفرع بالكامل فورًا.
عندما ندرج mediant ينقسم المجال إلى مجالين فرعيين:
$$\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,$$
$$ (b+d)c-(a+c)d=bc-ad=1.$$
لذلك يتكرر المنطق نفسه بصورة عودية. كل كسر صالح يقع إما إلى يسار mediant أو إلى يمينه، ولا يمكن أن يقع في الفرعين معًا. بهذا تتجزأ مجموعة الحلول من دون أي تداخل، ويُحصى كل كسر مطلوب مرة واحدة فقط.
لنعرّف
$$T_N\!\left(\frac{a}{b},\frac{c}{d}\right)$$
على أنه عدد الكسور المختزلة \(\frac{x}{y}\) التي تحقق
$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}, \qquad y\le N,$$
مع بقاء الشرط \(bc-ad=1\) صحيحًا. عندئذ تكون العلاقة الدقيقة هي
$$ T_N\!\left(\frac{a}{b},\frac{c}{d}\right)= \begin{cases} 0, & b+d \gt N,\\[4pt] 1 + T_N\!\left(\frac{a}{b},\frac{a+c}{b+d}\right) + T_N\!\left(\frac{a+c}{b+d},\frac{c}{d}\right), & b+d \le N. \end{cases} $$
إذن جواب المسألة هو
$$T_{12000}\!\left(\frac13,\frac12\right).$$
هذا ليس تجوالًا تجريبيًا داخل الشجرة، بل تفكيك دقيق لجميع الكسور المختزلة في المجال المطلوب وفق بنية Stern-Brocot نفسها.
نبدأ من \(\frac13\) و\(\frac12\). الـ mediant الأول هو \(\frac25\)، وبما أن \(5 \le 8\)، فإنه يُحسب.
الفرع الأيسر هو \(\left(\frac13,\frac25\right)\). الـ mediant هناك هو \(\frac38\)، وبما أن \(8 \le 8\)، فإنه يُحسب أيضًا. بعد ذلك تصبح مقامات الوسائط التالية \(11\) و\(13\)، ولذلك يتوقف هذا الفرع.
الفرع الأيمن هو \(\left(\frac25,\frac12\right)\). الـ mediant فيه هو \(\frac37\)، وبما أن \(7 \le 8\)، فإنه يُحسب كذلك. أمّا الفرعان التاليان فينتجان مقامين \(12\) و\(9\)، وكلاهما أكبر من الحد.
إذن المجموعة الكاملة هي
$$\left\{\frac38,\frac25,\frac37\right\},$$
ومن ثم يكون العدد هو \(3\). وهذا يطابق أول نقطة تحقق في التطبيقات. وإذا واصلنا توسيع الشجرة نفسها حتى \(N=12\)، فسيصبح العدد \(7\)، وهو ما يطابق نقطة التحقق الثانية.
تبدأ تطبيقات C++ وPython وJava كلها من الحالة نفسها: المجال ذو الطرفين \(\frac13\) و\(\frac12\). في كل خطوة تُحسب قيمة mediant بجمع البسطين وجمع المقامين فقط. إذا تجاوز المقام الجديد الحد، فإن هذا الفرع يعيد \(0\). وإذا لم يتجاوزه، يُضاف mediant نفسه إلى العد، ثم تستمر العملية على المجالين الفرعيين الأيسر والأيمن.
في C++ وJava كُتبت هذه الفكرة مباشرة على شكل بحث عمقي عودي. أما في Python فاستُخدم مكدس صريح يحتوي على المجالات غير المعالجة. هذا يغيّر أسلوب التنفيذ فقط، لكنه يحافظ على العلاقة العودية نفسها وعلى النتيجة نفسها تمامًا.
قبل حل الحالة الكاملة \(N=12000\)، تتحقق الشيفرة من حالتين صغيرتين: \(N=8 \mapsto 3\) و\(N=12 \mapsto 7\). هاتان النتيجتان تؤكدان أن تقسيم المجال، وشرط الإيقاف، وفكرة احتساب mediant مرة واحدة كلها منسجمة مع الاشتقاق الرياضي.
كل كسر صالح داخل المجال يُولَّد مرة واحدة فقط، وكل فرع مرفوض ينتهي بعد عمل ثابت. إذا رمزنا بعدد الكسور المختزلة في \(\left(\frac13,\frac12\right)\) ذات المقام الذي لا يتجاوز \(N\) بالرمز \(A(N)\)، فإن زمن التنفيذ يساوي \(O(A(N))\). وفي هذه المسألة ينمو \(A(N)\) من رتبة \(N^2\)، لذا يمكن اعتبار الخوارزمية تربيعية عمليًا في حد المقام، لكنها تتجنب كل اختبارات \(\gcd\) غير الضرورية على أزواج لا تساهم أصلًا في الجواب.
استهلاك الذاكرة هو \(O(H)\)، حيث \(H\) هو عمق مكدس البحث. في نسختي C++ وJava يظهر ذلك كعمق استدعاء عودي، وفي Python يظهر كحجم المكدس الصريح. وفي أسوأ الحالات قد يصل \(H\) إلى \(O(N)\) لأن بعض الفروع تزيد المقامات ببطء، ومع ذلك يبقى حجم التخزين صغيرًا جدًا مقارنة بعدّ جميع المرشحين من البسوط والمقامات مباشرة.