We consider reduced proper fractions \(p/q\) with \(q \le 1{,}000{,}000\), list them in increasing order, and look for the fraction immediately to the left of \(3/7\). Equivalently, we want the largest reduced fraction strictly smaller than \(3/7\) whose denominator does not exceed \(10^6\). The winning fraction is \(428570/999997\), so the required numerator is \(428570\).
The implementation does not construct the ordered list explicitly. Instead, it scans all denominators, computes the best possible numerator for each one, and maintains the largest reduced fraction found so far. That turns the ordering question into a clean arithmetic optimization problem.
Fix a denominator \(d\). To stay strictly left of \(3/7\), we need
$$\frac{n}{d} \lt \frac{3}{7} \iff 7n \lt 3d.$$
Since \(3d\) is an integer, the largest integer \(n\) satisfying this strict inequality is obtained by replacing it with \(7n \le 3d - 1\). Therefore the only numerator worth testing for this denominator is
$$n_d = \left\lfloor \frac{3d - 1}{7} \right\rfloor.$$
So every denominator contributes at most one serious candidate.
The ordered set in the problem contains each reduced proper fraction exactly once. If \(\gcd(n_d,d) \ne 1\), then \(n_d/d\) is only a non-reduced copy of a fraction that already appears with a smaller denominator. Such a candidate cannot be the new immediate left neighbor in the reduced list, so the implementations skip it.
Suppose the current best reduced fraction is \(a/b\), and the new candidate is \(n/d\). Because all denominators are positive, we can compare them exactly by cross-multiplication:
$$\frac{n}{d} \gt \frac{a}{b} \iff nb \gt ad.$$
This avoids rounding issues and keeps the whole search in integer arithmetic.
After processing all denominators up to some value \(D\), the stored fraction is the largest reduced fraction below \(3/7\) among all denominators \(2,3,\dots,D\). The invariant is straightforward: when the next denominator arrives, its unique candidate is either discarded because it is not reduced, ignored because it is not better, or promoted because it is larger than the current best. By induction, the invariant remains true until the scan reaches \(10^6\).
The small checkpoint used by the implementations is \(N=8\). Evaluating the formula gives
$$ \begin{aligned} d=3 &\Rightarrow n=1 &&\Rightarrow \frac{1}{3},\\ d=4 &\Rightarrow n=1 &&\Rightarrow \frac{1}{4},\\ d=5 &\Rightarrow n=2 &&\Rightarrow \frac{2}{5},\\ d=6 &\Rightarrow n=2 &&\Rightarrow \frac{2}{6}\ \text{(not reduced)},\\ d=7 &\Rightarrow n=2 &&\Rightarrow \frac{2}{7},\\ d=8 &\Rightarrow n=3 &&\Rightarrow \frac{3}{8}. \end{aligned} $$
Among the reduced fractions strictly below \(3/7\), the largest is \(2/5\). That is why the checkpoint expects the numerator \(2\).
The scan is the method actually implemented, but the final answer can be verified number-theoretically. Adjacent reduced fractions \(a/b \lt c/d\) in a Farey sequence satisfy
$$bc - ad = 1.$$
For the predecessor \(p/q\) of \(3/7\), this becomes
$$3q - 7p = 1.$$
Hence \(3q \equiv 1 \pmod{7}\), so \(q \equiv 5 \pmod{7}\). The largest denominator with that residue and \(q \le 10^6\) is \(q=999997\). Substituting back gives
$$p = \frac{3q - 1}{7} = \frac{3 \cdot 999997 - 1}{7} = 428570.$$
This confirms that the immediate left neighbor is exactly \(428570/999997\).
The C++, Python, and Java implementations keep a current best numerator and denominator, initialized to \(0/1\). They iterate through every denominator from \(2\) up to the limit, compute \(n=\lfloor(3d-1)/7\rfloor\), reject the candidate when \(\gcd(n,d) \ne 1\), and otherwise compare \(n/d\) to the stored best fraction using cross-multiplication.
No fraction list is materialized, and no sorting is needed. Each loop iteration does one formula evaluation, one gcd test, and one exact comparison. The C++ and Python versions also include a small check at \(N=8\); the Java version runs the same scan directly for the full limit.
The denominator scan performs \(N-1\) iterations. Each iteration uses constant-size integer arithmetic plus a gcd computation, so the total running time is \(O(N \log N)\) in the standard arithmetic model. For the fixed bound \(N=10^6\), this is easily fast enough.
The memory usage is \(O(1)\), because the implementation stores only the current best fraction and a handful of loop variables. A closed-form shortcut exists for this particular target, but the implemented scan is simple, exact, and general.
Gesucht ist unter allen vollständig gekürzten echten Brüchen \(p/q\) mit \(q \le 1{,}000{,}000\) der Bruch, der in aufsteigender Reihenfolge unmittelbar links von \(3/7\) steht. Anders formuliert: Wir maximieren \(p/q\) unter den Bedingungen \(p/q \lt 3/7\), \(q \le 10^6\) und \(\gcd(p,q)=1\). Der gesuchte Bruch ist \(428570/999997\), also lautet der geforderte Zähler \(428570\).
Die Implementierungen erzeugen die geordnete Bruchliste nicht explizit. Stattdessen wird jeder mögliche Nenner untersucht, dazu der beste zulässige Zähler berechnet und anschließend der bislang größte reduzierte Bruch gespeichert. So wird aus einem Ordnungsproblem ein reines Ganzzahlproblem.
Fixiere einen Nenner \(d\). Damit \(n/d\) strikt links von \(3/7\) liegt, muss gelten
$$\frac{n}{d} \lt \frac{3}{7} \iff 7n \lt 3d.$$
Da \(3d\) ganzzahlig ist, erhält man den größten möglichen ganzzahligen Zähler durch
$$n_d = \left\lfloor \frac{3d - 1}{7} \right\rfloor.$$
Für jeden Nenner existiert also genau ein Kandidat, der überhaupt optimal sein kann.
In der gesuchten geordneten Liste erscheint jeder vollständig gekürzte Bruch genau einmal. Falls \(\gcd(n_d,d) \ne 1\) ist, dann ist \(n_d/d\) nur eine nicht gekürzte Darstellung eines Bruchs mit kleinerem Nenner. Ein solcher Kandidat kann deshalb keinen neuen unmittelbaren linken Nachbarn erzeugen und wird verworfen.
Sei \(a/b\) der bisher beste Bruch und \(n/d\) der neue Kandidat. Wegen positiver Nenner genügt die Kreuzmultiplikation:
$$\frac{n}{d} \gt \frac{a}{b} \iff nb \gt ad.$$
Dadurch arbeitet die gesamte Suche exakt mit Ganzzahlen und vermeidet jedes Rundungsproblem.
Nachdem alle Nenner bis einschließlich \(D\) verarbeitet wurden, ist der gespeicherte Bruch der größte reduzierte Bruch kleiner als \(3/7\) mit Nenner höchstens \(D\). Für den nächsten Nenner gibt es nur drei Fälle: Der Kandidat ist nicht gekürzt und wird ignoriert, er ist gekürzt aber nicht besser, oder er ist gekürzt und größer als der bisherige Bestwert. Dann ersetzt er diesen. Induktiv bleibt die Invariante bis \(10^6\) erhalten.
Die kleine Kontrollrechnung der Implementierungen verwendet \(N=8\). Die Kandidaten sind
$$ \begin{aligned} d=3 &\Rightarrow n=1 &&\Rightarrow \frac{1}{3},\\ d=4 &\Rightarrow n=1 &&\Rightarrow \frac{1}{4},\\ d=5 &\Rightarrow n=2 &&\Rightarrow \frac{2}{5},\\ d=6 &\Rightarrow n=2 &&\Rightarrow \frac{2}{6}\ \text{(nicht gekürzt)},\\ d=7 &\Rightarrow n=2 &&\Rightarrow \frac{2}{7},\\ d=8 &\Rightarrow n=3 &&\Rightarrow \frac{3}{8}. \end{aligned} $$
Unter den reduzierten Brüchen links von \(3/7\) ist \(2/5\) der größte. Deshalb erwartet die Kontrollrechnung den Zähler \(2\).
Die tatsächlichen Programme benutzen den Nenner-Scan, doch das Endergebnis lässt sich elegant überprüfen. Benachbarte reduzierte Brüche \(a/b \lt c/d\) in einer Farey-Folge erfüllen
$$bc - ad = 1.$$
Für den direkten Vorgänger \(p/q\) von \(3/7\) folgt daraus
$$3q - 7p = 1.$$
Also gilt \(3q \equiv 1 \pmod{7}\) und damit \(q \equiv 5 \pmod{7}\). Der größte solche Nenner mit \(q \le 10^6\) ist \(999997\). Dann erhält man
$$p = \frac{3q - 1}{7} = \frac{3 \cdot 999997 - 1}{7} = 428570.$$
Damit ist der gesuchte linke Nachbar genau \(428570/999997\).
Die C++-, Python- und Java-Implementierungen speichern den bisher besten Zähler und Nenner, beginnend mit \(0/1\). Anschließend laufen sie alle Nenner von \(2\) bis zur Schranke durch, berechnen \(n=\lfloor(3d-1)/7\rfloor\), prüfen \(\gcd(n,d)=1\) und vergleichen den Kandidaten per Kreuzmultiplikation mit dem aktuellen Bestwert.
Es wird weder eine Bruchliste aufgebaut noch etwas sortiert. Jede Schleifeniteration besteht nur aus einer Formel, einem ggT-Test und einem exakten Vergleich. Die C++- und Python-Versionen enthalten zusätzlich eine kleine Kontrolle für \(N=8\); die Java-Version führt denselben Scan direkt mit der Endgrenze aus.
Der Scan betrachtet \(N-1\) Nenner. Pro Schritt fallen konstante Ganzzahlarithmetik und eine ggT-Berechnung an, also insgesamt \(O(N \log N)\) im üblichen Rechenmodell. Für \(N=10^6\) ist das problemlos schnell genug.
Der Speicherbedarf beträgt \(O(1)\), da nur der aktuelle Bestbruch und einige Schleifenvariablen gehalten werden. Für dieses spezielle Ziel gibt es zwar eine geschlossene Abkürzung, aber die implementierte Methode ist einfach, exakt und allgemein einsetzbar.
\(q \le 1{,}000{,}000\) koşulunu sağlayan tüm sadeleşmiş basit kesirleri \(p/q\) artan sıraya koyup \(3/7\)'nin hemen solundaki kesri arıyoruz. Eşdeğer biçimde amaç, \(\gcd(p,q)=1\), \(q \le 10^6\) ve \(p/q \lt 3/7\) koşulları altında en büyük kesri bulmaktır. Kazanan kesir \(428570/999997\) olduğundan istenen pay \(428570\)'tir.
Uygulamalar bütün kesirleri açıkça üretmez. Bunun yerine her payda için o paydayla mümkün olan en büyük uygun payı hesaplar, sonra da şimdiye kadar görülen en iyi sadeleşmiş kesri saklar. Böylece sıralama problemi, bütünüyle tamsayı aritmetiğine indirgenir.
Bir \(d\) paydasını sabitleyelim. Kesrin \(3/7\)'nin solunda kalması için
$$\frac{n}{d} \lt \frac{3}{7} \iff 7n \lt 3d$$
gerekir. \(3d\) bir tamsayı olduğu için bu sıkı eşitsizliği sağlayan en büyük tamsayı pay
$$n_d = \left\lfloor \frac{3d - 1}{7} \right\rfloor$$
olur. Demek ki her payda için gerçekten kontrol etmeye değer yalnızca tek bir aday vardır.
Problemin sıralı listesinde her sadeleşmiş kesir yalnızca bir kez yer alır. Eğer \(\gcd(n_d,d) \ne 1\) ise \(n_d/d\), daha küçük bir payda ile zaten görünen aynı kesrin sadeleşmemiş bir kopyasıdır. Bu yüzden uygulamalar böyle adayları atlar.
Mevcut en iyi kesir \(a/b\), yeni aday ise \(n/d\) olsun. Paydalar pozitif olduğu için karşılaştırma doğrudan çapraz çarpma ile yapılabilir:
$$\frac{n}{d} \gt \frac{a}{b} \iff nb \gt ad.$$
Böylece kayan nokta kullanılmaz ve \(3/7\)'ye çok yakın kesirlerde yuvarlama hatası oluşmaz.
\(D\)'ye kadar olan bütün paydalar işlendiğinde bellekte tutulan kesir, paydası en çok \(D\) olan ve \(3/7\)'den küçük bütün sadeleşmiş kesirler içindeki en büyük değerdir. Sonraki payda geldiğinde aday ya sadeleşmemiş olduğu için elenir, ya mevcut en iyiden küçük kalır, ya da ondan büyüktür ve yeni en iyi olur. Bu nedenle değişmez, \(10^6\)'ya kadar indüksiyonla korunur.
Uygulamaların küçük kontrolü \(N=8\) için yapılır. Formülün verdiği adaylar şunlardır:
$$ \begin{aligned} d=3 &\Rightarrow n=1 &&\Rightarrow \frac{1}{3},\\ d=4 &\Rightarrow n=1 &&\Rightarrow \frac{1}{4},\\ d=5 &\Rightarrow n=2 &&\Rightarrow \frac{2}{5},\\ d=6 &\Rightarrow n=2 &&\Rightarrow \frac{2}{6}\ \text{(sade değil)},\\ d=7 &\Rightarrow n=2 &&\Rightarrow \frac{2}{7},\\ d=8 &\Rightarrow n=3 &&\Rightarrow \frac{3}{8}. \end{aligned} $$
\(3/7\)'nin altında kalan sadeleşmiş adaylar arasında en büyüğü \(2/5\) olur. Bu yüzden kontrol sonucu pay olarak \(2\) beklenir.
Gerçek kod tarama yapar; yine de sonucun doğru olduğunu daha teorik bir yoldan kontrol edebiliriz. Farey dizisinde ardışık sadeleşmiş kesirler \(a/b \lt c/d\) için
$$bc - ad = 1$$
eşitliği geçerlidir. \(3/7\)'nin hemen sol komşusu \(p/q\) için bu
$$3q - 7p = 1$$
şeklini alır. Buradan \(3q \equiv 1 \pmod{7}\), dolayısıyla \(q \equiv 5 \pmod{7}\) elde edilir. \(10^6\)'yı aşmayan en büyük böyle payda \(999997\)'dir ve
$$p = \frac{3q - 1}{7} = \frac{3 \cdot 999997 - 1}{7} = 428570$$
olur. Böylece aranan kesrin tam olarak \(428570/999997\) olduğu doğrulanır.
C++, Python ve Java uygulamaları başlangıçta en iyi kesri \(0/1\) olarak tutar. Sonra \(2\)'den sınıra kadar bütün paydaları dolaşır, \(n=\lfloor(3d-1)/7\rfloor\) değerini hesaplar, \(\gcd(n,d) \ne 1\) ise adayı atar ve aksi halde çapraz çarpma ile mevcut en iyi kesirden büyük olup olmadığını test eder.
Hiçbir zaman bütün kesirler listelenmez ve sıralanmaz. Her döngü adımında yalnızca bir formül, bir ebob hesabı ve bir tam sayı karşılaştırması vardır. C++ ve Python sürümleri ayrıca \(N=8\) için küçük bir doğrulama içerir; Java sürümü aynı taramayı doğrudan son sınırda çalıştırır.
Tarama toplam \(N-1\) payda işler. Her adımda sabit boyutlu tamsayı işlemleri ve bir ebob hesabı bulunduğu için toplam süre standart modelde \(O(N \log N)\) olur. \(N=10^6\) için bu maliyet oldukça düşüktür.
Bellek kullanımı \(O(1)\)'dir; çünkü yalnızca mevcut en iyi kesir ve birkaç döngü değişkeni saklanır. Bu problem için kapalı bir kısayol olsa da uygulanan yöntem basit, kesin ve geneldir.
Tomamos todas las fracciones propias reducidas \(p/q\) con \(q \le 1{,}000{,}000\), las ordenamos de menor a mayor y buscamos la que aparece inmediatamente a la izquierda de \(3/7\). De forma equivalente, queremos maximizar \(p/q\) bajo las condiciones \(p/q \lt 3/7\), \(q \le 10^6\) y \(\gcd(p,q)=1\). La fracción ganadora es \(428570/999997\), así que el numerador pedido es \(428570\).
La implementación no construye la lista ordenada de fracciones. Recorre todos los denominadores posibles, calcula para cada uno el mejor numerador permitido y conserva la fracción reducida más grande encontrada hasta ese momento. El problema de orden se transforma así en una búsqueda entera muy simple.
Fijemos un denominador \(d\). Para que \(n/d\) quede estrictamente a la izquierda de \(3/7\), debe cumplirse
$$\frac{n}{d} \lt \frac{3}{7} \iff 7n \lt 3d.$$
Como \(3d\) es entero, el mayor entero que satisface esa desigualdad estricta es
$$n_d = \left\lfloor \frac{3d - 1}{7} \right\rfloor.$$
Por lo tanto, cada denominador aporta como mucho un único candidato serio.
La lista del problema contiene cada fracción reducida una sola vez. Si \(\gcd(n_d,d) \ne 1\), entonces \(n_d/d\) no es un nuevo término, sino una copia no reducida de una fracción con denominador menor. Ese candidato no puede convertirse en el vecino inmediato buscado y se descarta.
Sea \(a/b\) la mejor fracción encontrada hasta ahora y \(n/d\) el nuevo candidato. Como los denominadores son positivos, basta comparar productos cruzados:
$$\frac{n}{d} \gt \frac{a}{b} \iff nb \gt ad.$$
Esto evita errores de redondeo y mantiene toda la lógica en aritmética entera.
Después de procesar todos los denominadores hasta \(D\), la fracción almacenada es la mayor fracción reducida menor que \(3/7\) entre todas las que tienen denominador a lo sumo \(D\). Al examinar el siguiente denominador, su candidato o bien se descarta por no estar reducido, o bien no mejora el máximo actual, o bien lo supera y pasa a ser la nueva mejor fracción. Ese razonamiento inductivo garantiza que el resultado final es correcto.
La comprobación pequeña usada por las implementaciones toma \(N=8\). Los candidatos son
$$ \begin{aligned} d=3 &\Rightarrow n=1 &&\Rightarrow \frac{1}{3},\\ d=4 &\Rightarrow n=1 &&\Rightarrow \frac{1}{4},\\ d=5 &\Rightarrow n=2 &&\Rightarrow \frac{2}{5},\\ d=6 &\Rightarrow n=2 &&\Rightarrow \frac{2}{6}\ \text{(no reducida)},\\ d=7 &\Rightarrow n=2 &&\Rightarrow \frac{2}{7},\\ d=8 &\Rightarrow n=3 &&\Rightarrow \frac{3}{8}. \end{aligned} $$
Entre las fracciones reducidas que quedan por debajo de \(3/7\), la mayor es \(2/5\). Por eso la comprobación espera el numerador \(2\).
El código real usa el barrido por denominadores, pero el resultado puede verificarse con teoría de números. Fracciones reducidas consecutivas \(a/b \lt c/d\) en una secuencia de Farey cumplen
$$bc - ad = 1.$$
Si \(p/q\) es la fracción inmediatamente anterior a \(3/7\), entonces
$$3q - 7p = 1.$$
De aquí se obtiene \(3q \equiv 1 \pmod{7}\), es decir, \(q \equiv 5 \pmod{7}\). El mayor denominador con ese residuo y \(q \le 10^6\) es \(999997\). Sustituyendo,
$$p = \frac{3q - 1}{7} = \frac{3 \cdot 999997 - 1}{7} = 428570.$$
Así se confirma que el vecino inmediato es exactamente \(428570/999997\).
Las implementaciones en C++, Python y Java mantienen el mejor numerador y denominador vistos hasta el momento, empezando en \(0/1\). Luego recorren todos los denominadores desde \(2\) hasta el límite, calculan \(n=\lfloor(3d-1)/7\rfloor\), rechazan el candidato si \(\gcd(n,d) \ne 1\) y, en caso contrario, lo comparan con la mejor fracción actual mediante multiplicación cruzada.
No se materializa ninguna lista de fracciones ni se hace ningún ordenamiento. Cada iteración realiza una evaluación de fórmula, una comprobación de gcd y una comparación exacta. Las versiones de C++ y Python incluyen además una prueba pequeña con \(N=8\); la versión de Java ejecuta directamente el barrido final.
El barrido procesa \(N-1\) denominadores. En cada paso hay aritmética entera de tamaño fijo y un cálculo de gcd, por lo que el coste total es \(O(N \log N)\) en el modelo aritmético habitual. Para \(N=10^6\), esta estrategia es más que suficiente.
El consumo de memoria es \(O(1)\), ya que solo se guardan la mejor fracción actual y unas pocas variables auxiliares. Existe un atajo cerrado para esta fracción objetivo, pero el método implementado es simple, exacto y fácil de generalizar.
我们考虑所有满足 \(q \le 1{,}000{,}000\) 的既约真分数 \(p/q\)，把它们按从小到大的顺序排列，要求找出紧挨在 \(3/7\) 左边的那个分数。等价地说，就是在 \(\gcd(p,q)=1\)、\(q \le 10^6\)、\(p/q \lt 3/7\) 的条件下，求最大的分数。最终得到的分数是 \(428570/999997\)，因此题目要求的分子是 \(428570\)。
实现并不会显式生成整张有序分数表，而是逐个扫描分母。对每个分母，只计算那个“仍然小于 \(3/7\) 的最大分子”，然后维护当前找到的最佳既约分数。这样，原本的排序问题就变成了一个非常直接的整数优化问题。
先固定一个分母 \(d\)。如果 \(n/d\) 必须严格位于 \(3/7\) 左边，那么必须满足
$$\frac{n}{d} \lt \frac{3}{7} \iff 7n \lt 3d.$$
由于 \(3d\) 是整数，把严格不等式改写成 \(7n \le 3d-1\) 后，就能直接得到满足条件的最大整数分子：
$$n_d = \left\lfloor \frac{3d - 1}{7} \right\rfloor.$$
这说明每个分母实际上只需要检查一个候选值。
题目中的有序列表只包含既约分数。如果 \(\gcd(n_d,d) \ne 1\)，那么 \(n_d/d\) 只是某个更小分母分数的未约分写法，并不会在“既约分数的有序表”里提供一个新的位置。因此这些候选值必须跳过。
设当前最佳分数为 \(a/b\)，新候选分数为 \(n/d\)。由于分母都为正数，比较大小时不需要转成小数，只要做交叉相乘：
$$\frac{n}{d} \gt \frac{a}{b} \iff nb \gt ad.$$
这样整个过程都保持在整数范围内，不会因为浮点误差而把接近 \(3/7\) 的候选搞错。
当程序已经处理完所有不超过 \(D\) 的分母后，保存下来的那一个分数一定是“所有分母至多为 \(D\)、且严格小于 \(3/7\) 的既约分数”中的最大者。原因很简单：对新的分母只有一个候选，它要么因为不既约而被丢弃，要么虽然既约但不够大，要么真的更大并更新当前最优值。于是这个性质会一直保持到 \(D=10^6\)。
实现中的小规模校验使用 \(N=8\)。按公式计算得到
$$ \begin{aligned} d=3 &\Rightarrow n=1 &&\Rightarrow \frac{1}{3},\\ d=4 &\Rightarrow n=1 &&\Rightarrow \frac{1}{4},\\ d=5 &\Rightarrow n=2 &&\Rightarrow \frac{2}{5},\\ d=6 &\Rightarrow n=2 &&\Rightarrow \frac{2}{6}\ \text{（不是既约分数）},\\ d=7 &\Rightarrow n=2 &&\Rightarrow \frac{2}{7},\\ d=8 &\Rightarrow n=3 &&\Rightarrow \frac{3}{8}. \end{aligned} $$
在所有严格小于 \(3/7\) 的既约候选里，最大的就是 \(2/5\)。所以这个校验要求返回的分子是 \(2\)。
代码本身采用的是分母扫描法，但最终结果还可以用 Farey 序列的相邻性质做验证。若 \(a/b \lt c/d\) 是 Farey 序列中的相邻既约分数，则满足
$$bc - ad = 1.$$
如果 \(p/q\) 正好是 \(3/7\) 的左邻项，就有
$$3q - 7p = 1.$$
于是 \(3q \equiv 1 \pmod{7}\)，也就是 \(q \equiv 5 \pmod{7}\)。在所有不超过 \(10^6\) 的这类分母里，最大的一个是 \(999997\)。代回去可得
$$p = \frac{3q - 1}{7} = \frac{3 \cdot 999997 - 1}{7} = 428570.$$
因此可以确认，紧挨在 \(3/7\) 左边的分数确实是 \(428570/999997\)。
C++、Python 和 Java 实现都维护“当前最佳分子、当前最佳分母”这两个整数，初值为 \(0/1\)。随后它们从 \(2\) 开始扫描到上界，对每个分母计算 \(n=\lfloor(3d-1)/7\rfloor\)，如果 \(\gcd(n,d) \ne 1\) 就跳过，否则用交叉相乘比较 \(n/d\) 是否优于当前最佳分数。
整个过程中既不会生成完整分数列表，也不会做排序。每次循环只需要一次公式计算、一次 gcd 检查和一次精确比较。C++ 与 Python 版本还带有 \(N=8\) 的小型校验；Java 版本则直接执行最终扫描。
扫描一共处理 \(N-1\) 个分母。每一步包含常数次整数运算和一次 gcd 计算，因此在通常的算术模型下，总时间复杂度为 \(O(N \log N)\)。对 \(N=10^6\) 来说，这个代价非常容易接受。
空间复杂度为 \(O(1)\)，因为程序只保存当前最佳分数和少量循环变量。这个特定目标其实还能推出闭式捷径，但实现选择了更直接、更稳妥、也更容易推广的扫描方法。
Рассматриваются все несократимые правильные дроби \(p/q\) с условием \(q \le 1{,}000{,}000\). Если упорядочить их по возрастанию, нужно найти дробь, стоящую непосредственно слева от \(3/7\). Иными словами, требуется максимизировать \(p/q\) при условиях \(p/q \lt 3/7\), \(q \le 10^6\) и \(\gcd(p,q)=1\). Итоговая дробь равна \(428570/999997\), поэтому искомый числитель равен \(428570\).
В реализации не строится весь упорядоченный список дробей. Вместо этого перебираются все возможные знаменатели, для каждого вычисляется наилучший допустимый числитель, а затем поддерживается максимальная несократимая дробь, найденная к текущему моменту. Так задача про порядок превращается в задачу на целочисленные вычисления.
Зафиксируем знаменатель \(d\). Чтобы дробь \(n/d\) была строго меньше \(3/7\), необходимо
$$\frac{n}{d} \lt \frac{3}{7} \iff 7n \lt 3d.$$
Так как \(3d\) является целым числом, максимальный допустимый целый числитель задается формулой
$$n_d = \left\lfloor \frac{3d - 1}{7} \right\rfloor.$$
Значит, для каждого знаменателя существует ровно один кандидат, который имеет смысл проверять.
В требуемом списке каждая дробь присутствует только в несократимом виде. Если \(\gcd(n_d,d) \ne 1\), то дробь \(n_d/d\) представляет собой лишь несокращенную запись некоторой дроби с меньшим знаменателем. Такой кандидат не может стать новым непосредственным левым соседом, поэтому он отбрасывается.
Пусть текущая лучшая дробь равна \(a/b\), а новый кандидат равен \(n/d\). При положительных знаменателях их можно сравнить точно через перекрестное умножение:
$$\frac{n}{d} \gt \frac{a}{b} \iff nb \gt ad.$$
Это полностью избавляет от проблем округления и оставляет всю логику в целочисленной арифметике.
После обработки всех знаменателей до \(D\) сохраненная дробь является наибольшей несократимой дробью, меньшей \(3/7\), среди всех знаменателей не больше \(D\). Когда рассматривается следующий знаменатель, его единственный кандидат либо отбрасывается как сократимый, либо не превосходит текущий максимум, либо превосходит его и заменяет. По индукции этот инвариант сохраняется до самого конца перебора.
Небольшая проверка в реализациях использует \(N=8\). Формула дает следующие кандидаты:
$$ \begin{aligned} d=3 &\Rightarrow n=1 &&\Rightarrow \frac{1}{3},\\ d=4 &\Rightarrow n=1 &&\Rightarrow \frac{1}{4},\\ d=5 &\Rightarrow n=2 &&\Rightarrow \frac{2}{5},\\ d=6 &\Rightarrow n=2 &&\Rightarrow \frac{2}{6}\ \text{(сократима)},\\ d=7 &\Rightarrow n=2 &&\Rightarrow \frac{2}{7},\\ d=8 &\Rightarrow n=3 &&\Rightarrow \frac{3}{8}. \end{aligned} $$
Среди несократимых дробей, лежащих левее \(3/7\), максимальна дробь \(2/5\). Поэтому в проверке ожидается числитель \(2\).
Программы действительно используют полный перебор знаменателей, но итог легко проверить и теоретически. Для соседних несократимых дробей \(a/b \lt c/d\) в последовательности Фарея выполняется
$$bc - ad = 1.$$
Если \(p/q\) является непосредственным предшественником \(3/7\), то получаем
$$3q - 7p = 1.$$
Отсюда следует \(3q \equiv 1 \pmod{7}\), то есть \(q \equiv 5 \pmod{7}\). Наибольший такой знаменатель, не превосходящий \(10^6\), равен \(999997\). Тогда
$$p = \frac{3q - 1}{7} = \frac{3 \cdot 999997 - 1}{7} = 428570.$$
Это подтверждает, что искомая дробь действительно равна \(428570/999997\).
Реализации на C++, Python и Java хранят текущий лучший числитель и знаменатель, начиная с \(0/1\). Затем они перебирают все знаменатели от \(2\) до заданного предела, вычисляют \(n=\lfloor(3d-1)/7\rfloor\), отбрасывают кандидат при \(\gcd(n,d) \ne 1\) и в противном случае сравнивают \(n/d\) с текущим максимумом через перекрестное умножение.
Никакой список дробей не строится и никакая сортировка не выполняется. Каждая итерация делает всего одну подстановку в формулу, одну проверку gcd и одно точное сравнение. В версиях на C++ и Python есть дополнительная маленькая проверка при \(N=8\); версия на Java сразу выполняет финальный перебор.
Перебор обрабатывает \(N-1\) знаменателей. На каждом шаге есть арифметика фиксированного размера и одно вычисление gcd, поэтому суммарное время равно \(O(N \log N)\) в стандартной модели вычислений. Для \(N=10^6\) этого более чем достаточно.
Память имеет порядок \(O(1)\), поскольку сохраняются только текущая лучшая дробь и несколько служебных переменных. Для данной целевой дроби существует и замкнутая формула, однако реализованный перебор проще, полностью точен и хорошо обобщается.
نأخذ جميع الكسور الصحيحة المختزلة \(p/q\) التي تحقق \(q \le 1{,}000{,}000\)، ثم نرتبها تصاعديا، ونبحث عن الكسر الواقع مباشرة إلى يسار \(3/7\). وبصياغة مكافئة: نريد أكبر كسر يحقق \(p/q \lt 3/7\) مع الشرطين \(q \le 10^6\) و \(\gcd(p,q)=1\). الكسر الفائز هو \(428570/999997\)، ولذلك فإن البسط المطلوب هو \(428570\).
التنفيذ لا يبني القائمة المرتبة لكل الكسور. بدلا من ذلك، يمر على كل مقام ممكن، ويحسب له أفضل بسط ما زال أصغر من \(3/7\)، ثم يحتفظ بأكبر كسر مختزل تم الوصول إليه حتى تلك اللحظة. وبهذا تتحول المسألة من ترتيب كسور إلى مسألة تحسين صحيحة مباشرة.
لنثبت مقاما \(d\). لكي يكون \(n/d\) واقعا إلى يسار \(3/7\) يجب أن يتحقق
$$\frac{n}{d} \lt \frac{3}{7} \iff 7n \lt 3d.$$
وبما أن \(3d\) عدد صحيح، فإن أكبر بسط صحيح يحقق هذا الشرط الصارم هو
$$n_d = \left\lfloor \frac{3d - 1}{7} \right\rfloor.$$
إذن لكل مقام مرشح واحد فقط يستحق الفحص.
القائمة المطلوبة تحتوي كل كسر مختزل مرة واحدة فقط. فإذا كان \(\gcd(n_d,d) \ne 1\)، فإن \(n_d/d\) ليس كسرا جديدا، بل مجرد نسخة غير مختزلة من كسر يظهر أصلا بمقام أصغر. لذلك تتجاوز التطبيقات هذه الحالات.
لنفترض أن أفضل كسر حالي هو \(a/b\)، وأن المرشح الجديد هو \(n/d\). بما أن المقامات موجبة، يمكن المقارنة بدقة تامة عبر الضرب التبادلي:
$$\frac{n}{d} \gt \frac{a}{b} \iff nb \gt ad.$$
بهذه الطريقة لا تظهر أي مشكلة تقريب عند الاقتراب كثيرا من \(3/7\).
بعد الانتهاء من جميع المقامات حتى \(D\)، يكون الكسر المخزن هو أكبر كسر مختزل أصغر من \(3/7\) بين كل الكسور ذات المقام الذي لا يتجاوز \(D\). وعندما نصل إلى المقام التالي، فإن مرشحه الوحيد إما يرفض لأنه غير مختزل، أو يبقى أصغر من أفضل قيمة حالية، أو يتجاوزها فيصبح هو الأفضل الجديد. وبالاستقراء يبقى هذا الثابت صحيحا حتى نهاية المسح عند \(10^6\).
التحقق الصغير داخل التطبيقات يستخدم \(N=8\). وتعطي الصيغة المرشحين الآتيين:
$$ \begin{aligned} d=3 &\Rightarrow n=1 &&\Rightarrow \frac{1}{3},\\ d=4 &\Rightarrow n=1 &&\Rightarrow \frac{1}{4},\\ d=5 &\Rightarrow n=2 &&\Rightarrow \frac{2}{5},\\ d=6 &\Rightarrow n=2 &&\Rightarrow \frac{2}{6},\\ d=7 &\Rightarrow n=2 &&\Rightarrow \frac{2}{7},\\ d=8 &\Rightarrow n=3 &&\Rightarrow \frac{3}{8}. \end{aligned} $$
المرشح عند \(d=6\) وهو \(2/6\) يستبعد لأنه غير مختزل. وبعد ذلك يبقى أكبر كسر مختزل تحت \(3/7\) هو \(2/5\)، ولهذا السبب تتوقع عملية التحقق أن يكون البسط هو \(2\).
الكود نفسه يعتمد على المسح المباشر، لكن يمكن التحقق من النتيجة نظريا. إذا كان \(a/b \lt c/d\) كسرين مختزلين متجاورين في متتالية فاري، فإنهما يحققان
$$bc - ad = 1.$$
وبالنسبة إلى الكسر \(p/q\) الواقع مباشرة قبل \(3/7\)، نحصل على
$$3q - 7p = 1.$$
ومن ثم \(3q \equiv 1 \pmod{7}\)، أي \(q \equiv 5 \pmod{7}\). أكبر مقام من هذا الشكل لا يتجاوز \(10^6\) هو \(999997\). وبالتعويض ينتج
$$p = \frac{3q - 1}{7} = \frac{3 \cdot 999997 - 1}{7} = 428570.$$
وهذا يؤكد أن الجار الأيسر الحقيقي هو \(428570/999997\).
تحتفظ تطبيقات C++ وPython وJava بأفضل بسط ومقام تم العثور عليهما، وتبدأ من \(0/1\). ثم تمر على كل مقام من \(2\) حتى الحد الأعلى، وتحسب \(n=\lfloor(3d-1)/7\rfloor\)، وترفض المرشح إذا كان \(\gcd(n,d) \ne 1\)، وإلا تقارنه بأفضل كسر حالي بواسطة الضرب التبادلي.
لا يتم إنشاء قائمة كاملة للكسور، ولا توجد أي عملية فرز. كل دورة تحتوي فقط على تطبيق الصيغة، وحساب gcd، ومقارنة صحيحة تماما. كما أن نسختي C++ وPython تضيفان تحققا صغيرا عند \(N=8\)، بينما تنفذ نسخة Java المسح النهائي مباشرة.
المسح يعالج \(N-1\) مقاما. وفي كل خطوة توجد عمليات صحيحة ثابتة الحجم مع حساب gcd واحد، لذا يكون الزمن الكلي \(O(N \log N)\) في النموذج الحسابي المعتاد. وعند \(N=10^6\) يبقى هذا سريعا جدا.
استهلاك الذاكرة هو \(O(1)\)، لأن التنفيذ لا يخزن إلا أفضل كسر حالي وبعض المتغيرات البسيطة. توجد صيغة مغلقة لهذا الهدف الخاص، لكن الطريقة المنفذة أبسط وأكثر مباشرة وتحافظ على الدقة الكاملة.