For a fixed denominator \(d\), the proper fractions are
$$\frac{1}{d},\frac{2}{d},\dots,\frac{d-1}{d}.$$
A proper fraction is resilient exactly when it is already in lowest terms, so the number of resilient fractions with denominator \(d\) is \(\varphi(d)\). Therefore the resilience of \(d\) is
$$R(d)=\frac{\varphi(d)}{d-1}.$$
The goal is to find the smallest denominator \(d\) such that
$$R(d) \lt \frac{15499}{94744}.$$
Brute force is a poor fit, because most denominators are obviously far from optimal. The successful approach is to search directly through the prime factorizations that can plausibly minimize \(d\).
The decisive fact is that resilience is governed much more by the distinct prime divisors of \(d\) than by their exponents. The implementations are built around that separation.
A numerator \(n\) gives a resilient fraction \(n/d\) precisely when \(\gcd(n,d)=1\). Among the \(d-1\) possible numerators \(1 \le n \lt d\), exactly \(\varphi(d)\) are coprime to \(d\). That turns the original counting problem into a purely multiplicative number-theory problem: once \(\varphi(d)\) is known, the resilience follows immediately.
If
$$d=\prod_{i=1}^{k} p_i^{e_i},$$
then Euler's product formula gives
$$\varphi(d)=d\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)=\prod_{i=1}^{k} p_i^{e_i-1}(p_i-1).$$
Hence
$$R(d)=\frac{d}{d-1}\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right).$$
This identity is the heart of the search. The product \(\prod (1-1/p_i)\) depends only on which primes divide \(d\), not on how large the exponents are. Raising an exponent does not change \(\varphi(d)/d\); it only replaces the prefactor \(d/(d-1)\) by a slightly smaller number that is closer to 1. So introducing a new distinct prime causes the main drop in resilience, while increasing an existing exponent is a fine-tuning move once the denominator is already close to the target.
This also explains why the search starts with the smallest primes. A new prime \(p\) multiplies \(\varphi(d)/d\) by \(1-1/p\), and that reduction is strongest for small \(p\). Minimal candidates therefore come from products of consecutive small primes, possibly followed by extra powers of those same primes.
Suppose two primes satisfy \(p \lt q\), and two exponents satisfy \(a \gt b\). Then
$$p^a q^b \lt p^b q^a.$$
So if a denominator uses the same two primes and the same two exponents, it is always smaller when the larger exponent is attached to the smaller prime. More generally, for a fixed set of primes and a fixed multiset of exponents, the smallest denominator is obtained when the exponents are non-increasing along the increasing prime list:
$$e_1 \ge e_2 \ge e_3 \ge \cdots.$$
That ordering is not merely a convenience. It is a correctness argument for the DFS: any candidate that breaks this rule can be rearranged into a smaller denominator with the same distinct-prime set, so it cannot be the minimal solution.
Instead of dividing, the implementations test the target inequality as
$$\varphi(d)\cdot 94744 \lt 15499\cdot(d-1).$$
This avoids floating-point rounding and keeps the search exact.
A small checkpoint illustrates the mechanism. If the threshold were \(4/10\), then \(d=6=2\cdot 3\) gives
$$\varphi(6)=2,\qquad R(6)=\frac{2}{5}=\frac{4}{10},$$
so the strict inequality still fails. But \(d=12=2^2\cdot 3\) gives
$$\varphi(12)=4,\qquad R(12)=\frac{4}{11}\lt\frac{4}{10}.$$
That is exactly the pattern exploited in the full problem: a squarefree product of small primes pushes the resilience down quickly, and then an extra power of a small prime can be the final adjustment that crosses the line with the smallest possible denominator.
The C++, Python, and Java implementations perform a depth-first search over increasing primes. The state carried by the recursion is the current denominator \(d\), the current totient \(\varphi(d)\), the position in the prime list, the maximum exponent allowed for the next prime, and the best valid denominator found so far.
The search never recomputes \(\varphi(d)\) from scratch. When a prime \(p\) is attached for the first time, the update is
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)(p-1).$$
If the same prime is extended from exponent \(e\) to exponent \(e+1\), the update becomes
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)p.$$
Those two rules are the main invariant of the recursion and come directly from the prime-power formula for \(\varphi\).
At each node, the implementation first checks whether the current denominator already meets the target. If it does, that denominator becomes the new global best and the branch stops, because multiplying by more primes can only increase \(d\). If the current denominator is already at least as large as the best known answer, the branch is also discarded immediately.
The next recursive call receives the current exponent as the upper bound for the next prime, enforcing the canonical condition \(e_1 \ge e_2 \ge \cdots\). This removes duplicate exponent permutations automatically. The implementations only need a short initial list of consecutive primes, up to 31, because the optimum is found inside that heavily pruned search space. The C++ implementation widens the cross-multiplication to 128-bit integer arithmetic, Python uses arbitrary-precision integers, and Java remains safely within 64-bit range for this target.
Without pruning, the problem is combinatorial in the possible exponent vectors. A useful way to describe the explored set is: the DFS visits only tuples
$$e_1 \ge e_2 \ge \cdots \ge 0,\qquad \prod_i p_i^{e_i} \lt d_{\text{best}},$$
where \(d_{\text{best}}\) is the best denominator known at that stage of the search. The exponent-order restriction removes all reorderings of the same multiset, and the best-value bound cuts off large branches before they expand.
Memory usage is \(O(k)\), where \(k\) is the recursion depth, because only one search path is stored at a time. For the actual target, \(k\) is a small constant and the visited tree is tiny in practice. The algorithm is fast precisely because it searches near-optimal factorizations instead of scanning all integers.
Für einen festen Nenner \(d\) sind die echten Brüche
$$\frac{1}{d},\frac{2}{d},\dots,\frac{d-1}{d}.$$
Ein echter Bruch ist genau dann resilient, wenn er bereits vollständig gekürzt ist. Deshalb gibt es zu einem Nenner \(d\) genau \(\varphi(d)\) resiliente Brüche, und die Resilienz ist
$$R(d)=\frac{\varphi(d)}{d-1}.$$
Gesucht ist der kleinste Nenner \(d\) mit
$$R(d) \lt \frac{15499}{94744}.$$
Ein naiver Durchlauf über alle Nenner wäre unökonomisch, weil fast alle Kandidaten offensichtlich nicht minimal sein können. Die Lösung durchsucht stattdessen direkt diejenigen Primfaktorzerlegungen, die einen minimalen Nenner liefern könnten.
Der zentrale Punkt ist, dass die Resilienz viel stärker von den verschiedenen Primteilern eines Nenners abhängt als von deren Exponenten. Genau diese Trennung nutzt die Implementierung aus.
Ein Zähler \(n\) erzeugt genau dann einen resilienten Bruch \(n/d\), wenn \(\gcd(n,d)=1\) gilt. Unter den \(d-1\) möglichen Zählern \(1 \le n \lt d\) sind also genau \(\varphi(d)\) zu \(d\) teilerfremd. Damit wird das ursprüngliche Zählproblem vollständig in eine Aussage über die Eulersche Phi-Funktion übersetzt.
Schreibe
$$d=\prod_{i=1}^{k} p_i^{e_i}.$$
Dann gilt nach der Produktformel für die Phi-Funktion
$$\varphi(d)=d\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)=\prod_{i=1}^{k} p_i^{e_i-1}(p_i-1).$$
Somit folgt
$$R(d)=\frac{d}{d-1}\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right).$$
Das ist die entscheidende Struktur. Das Produkt \(\prod (1-1/p_i)\) hängt nur davon ab, welche Primzahlen \(d\) teilen, nicht von ihren Exponenten. Eine Erhöhung eines Exponenten ändert \(\varphi(d)/d\) also nicht; sie ersetzt lediglich den Vorfaktor \(d/(d-1)\) durch eine etwas kleinere Zahl, die näher an 1 liegt. Neue verschiedene Primzahlen erzeugen daher den großen Sprung nach unten, während zusätzliche Potenzen bereits vorhandener Primzahlen nur die Feinanpassung übernehmen.
Darum beginnt die Suche auch mit den kleinsten Primzahlen. Ein neuer Primfaktor \(p\) multipliziert \(\varphi(d)/d\) mit \(1-1/p\), und dieser Effekt ist für kleine \(p\) am stärksten. Minimale Kandidaten bestehen deshalb aus Produkten aufeinanderfolgender kleiner Primzahlen, gegebenenfalls ergänzt durch weitere Potenzen derselben kleinen Primzahlen.
Seien \(p \lt q\) zwei Primzahlen und \(a \gt b\) zwei Exponenten. Dann ist
$$p^a q^b \lt p^b q^a.$$
Wenn also derselbe Exponentenmultimenge verwendet wird, ist der Nenner immer kleiner, wenn der größere Exponent bei der kleineren Primzahl steht. Allgemein erhält man für eine feste Primmenge und eine feste Exponentenmultimenge den kleinsten Nenner genau dann, wenn die Exponenten entlang der aufsteigenden Primzahlen nicht wachsen:
$$e_1 \ge e_2 \ge e_3 \ge \cdots.$$
Das ist kein bloßer Stil, sondern ein Korrektheitsargument für die Tiefensuche. Jeder Kandidat, der diese Ordnung verletzt, kann zu einem kleineren Nenner mit derselben Primmenge umgeordnet werden und ist daher niemals optimal.
Statt zu dividieren, prüfen die Implementierungen die Zielbedingung in der exakten Form
$$\varphi(d)\cdot 94744 \lt 15499\cdot(d-1).$$
Damit wird jede Gleitkommaunsicherheit vermieden.
Ein kleines Kontrollbeispiel zeigt das Prinzip. Für die Schwelle \(4/10\) ergibt \(d=6=2\cdot 3\)
$$\varphi(6)=2,\qquad R(6)=\frac{2}{5}=\frac{4}{10},$$
also noch keine strenge Unterschreitung. Dagegen liefert \(d=12=2^2\cdot 3\)
$$\varphi(12)=4,\qquad R(12)=\frac{4}{11}\lt\frac{4}{10}.$$
Genau dieses Verhalten nutzt der vollständige Algorithmus aus: Ein quadratfreies Produkt kleiner Primzahlen bringt die Resilienz schnell in die Nähe der Zielgrenze, und eine zusätzliche Potenz einer kleinen Primzahl kann dann die letzte nötige Absenkung erzeugen.
Die C++-, Python- und Java-Implementierungen führen eine Tiefensuche über aufsteigende Primzahlen aus. Der Rekursionszustand besteht aus dem aktuellen Nenner \(d\), dem aktuellen Wert \(\varphi(d)\), der Position in der Primliste, dem maximal zulässigen Exponenten für die nächste Primzahl und dem bisher besten gefundenen gültigen Nenner.
Die Suche berechnet \(\varphi(d)\) nie neu von Grund auf. Wenn eine Primzahl \(p\) erstmals angehängt wird, gilt
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)(p-1).$$
Wird dieselbe Primzahl von Exponent \(e\) auf \(e+1\) erhöht, dann lautet die Aktualisierung
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)p.$$
Diese beiden Regeln sind das zentrale Invariant der gesamten Rekursion und folgen direkt aus der Primzahlpotenzformel für \(\varphi\).
An jedem Knoten prüft die Implementierung zuerst, ob der aktuelle Nenner die Zielungleichung bereits erfüllt. Falls ja, wird er als neuer globaler Bestwert gespeichert, und der Zweig endet sofort, denn weitere Primfaktoren würden den Nenner nur vergrößern. Falls der aktuelle Nenner schon mindestens so groß ist wie die beste bekannte Lösung, wird der Zweig ebenfalls sofort abgeschnitten.
Die nächste Rekursionsebene erhält den gerade verwendeten Exponenten als Obergrenze für die nächste Primzahl. So wird die kanonische Ordnung \(e_1 \ge e_2 \ge \cdots\) automatisch erzwungen und jede bloße Umordnung derselben Exponenten vermieden. Die Implementierungen benötigen nur die ersten aufeinanderfolgenden kleinen Primzahlen bis 31, weil die optimale Lösung innerhalb dieses stark beschnittenen Suchraums gefunden wird. In C++ wird die Kreuzmultiplikation zur Sicherheit auf 128-Bit erweitert, Python verwendet beliebig große Ganzzahlen, und Java bleibt für diese Zielgröße sicher im 64-Bit-Bereich.
Ohne Abschneidungen wäre die Suche kombinatorisch in der Menge möglicher Exponentenvektoren. Zweckmäßig lässt sich der tatsächlich besuchte Raum so beschreiben: Die DFS betrachtet nur Tupel
$$e_1 \ge e_2 \ge \cdots \ge 0,\qquad \prod_i p_i^{e_i} \lt d_{\text{best}},$$
wobei \(d_{\text{best}}\) der aktuell beste bekannte Nenner ist. Die Exponentenordnung eliminiert alle Permutationen derselben Multimenge, und die Bestwert-Schranke kappt große Teilbäume schon vor ihrer Entfaltung.
Der Speicherbedarf ist \(O(k)\), wobei \(k\) die Rekursionstiefe bezeichnet, denn es wird immer nur ein Pfad im Suchbaum gehalten. Für das konkrete Problem ist \(k\) eine kleine Konstante, und der tatsächlich besuchte Suchbaum ist sehr klein. Die Methode ist schnell, weil sie direkt nahe-optimalen Faktorisierungen folgt statt alle ganzen Zahlen zu prüfen.
Sabit bir \(d\) paydası için ilgili basit kesirler
$$\frac{1}{d},\frac{2}{d},\dots,\frac{d-1}{d}$$
şeklindedir. Bir kesir ancak sade haldeyse dirençlidir; dolayısıyla paydası \(d\) olan dirençli kesirlerin sayısı \(\varphi(d)\) olur. Bu yüzden dirençlilik
$$R(d)=\frac{\varphi(d)}{d-1}$$
olarak tanımlanır. Aranan şey
$$R(d) \lt \frac{15499}{94744}$$
eşitsizliğini sağlayan en küçük \(d\)'dir. Bütün paydaları sırayla deneyip totient hesaplamak verimsizdir; asıl iş, gerçekten en küçük cevabı üretebilecek asal çarpan yapılarında yapılır.
Bu problemde belirleyici olan nokta, dirençliliğin üslerden çok farklı asal bölenler tarafından belirlenmesidir. Çözümün tamamı bu ayrımı kullanır.
Bir \(n/d\) kesrinin dirençli olması tam olarak \(\gcd(n,d)=1\) koşuluna eşdeğerdir. \(1 \le n \lt d\) aralığında toplam \(d-1\) aday pay vardır ve bunların tam \(\varphi(d)\) tanesi \(d\) ile aralarında asaldır. Böylece problem doğrudan \(\varphi(d)\)'yi kontrol eden bir sayı kuramı problemine dönüşür.
Eğer
$$d=\prod_{i=1}^{k} p_i^{e_i}$$
ise Euler çarpım formülü
$$\varphi(d)=d\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)=\prod_{i=1}^{k} p_i^{e_i-1}(p_i-1)$$
verir. Dolayısıyla
$$R(d)=\frac{d}{d-1}\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right).$$
Bu formül aramanın merkezindedir. \(\prod (1-1/p_i)\) çarpanı yalnızca hangi asalların kullanıldığına bağlıdır; üslerin büyüklüğüne bağlı değildir. Bir üssü artırmak \(\varphi(d)/d\) oranını değiştirmez; sadece \(d/(d-1)\) ön çarpanını 1'e biraz daha yakın, biraz daha küçük bir değere çeker. Yani yeni bir farklı asal, dirençlilikteki büyük düşüşü yaratır; aynı asala ek bir kuvvet vermek ise hedef çizgisine yaklaşmış bir adayda ince ayar görevi görür.
Aramanın küçük asallarla başlamasının nedeni de budur. Yeni bir asal \(p\), \(\varphi(d)/d\) oranını \(1-1/p\) ile çarpar ve bu azaltma küçük \(p\) için daha güçlüdür. Bu yüzden minimal adaylar tipik olarak art arda gelen küçük asalların çarpımıyla başlar, gerekirse bunlara yine küçük asal kuvvetleri eklenir.
\(p \lt q\) ve \(a \gt b\) olsun. O zaman
$$p^a q^b \lt p^b q^a.$$
Yani aynı iki asal ve aynı iki üs kullanılıyorsa, büyük üssü küçük asala vermek her zaman daha küçük bir payda üretir. Genel durumda da, sabit bir asal kümesi ve sabit bir üs çokluğu için en küçük payda ancak üsler artan asal sırası boyunca azalmıyorsa elde edilir:
$$e_1 \ge e_2 \ge e_3 \ge \cdots.$$
Bu koşul sadece estetik değildir; DFS'in doğruluk gerekçesidir. Bu düzeni bozan her aday, aynı asal kümesini koruyup daha küçük bir paydaya dönüştürülebilir; dolayısıyla minimum çözüm olamaz.
Bölme yapmak yerine uygulamalar hedefi şu tam sayı eşitsizliğiyle test eder:
$$\varphi(d)\cdot 94744 \lt 15499\cdot(d-1).$$
Böylece kayan nokta hatası tamamen ortadan kalkar.
Küçük bir örnek mekanizmayı açıkça gösterir. Eşik \(4/10\) olsaydı, \(d=6=2\cdot 3\) için
$$\varphi(6)=2,\qquad R(6)=\frac{2}{5}=\frac{4}{10}$$
elde edilir; ama aranan koşul sıkı eşitsizlik olduğu için bu yetmez. Buna karşılık \(d=12=2^2\cdot 3\) için
$$\varphi(12)=4,\qquad R(12)=\frac{4}{11}\lt\frac{4}{10}.$$
Gerçek problemde de aynı desen görülür: küçük asallardan oluşan karefree bir çekirdek oranı hızla aşağı çeker, ardından küçük bir asalın fazladan kuvveti son sınırı aşan en küçük paydayı verebilir.
C++, Python ve Java uygulamaları artan asallar üzerinde derinlik öncelikli bir arama yapar. Rekürsiyonun taşıdığı durum; mevcut payda \(d\), mevcut \(\varphi(d)\), asal listesindeki konum, bir sonraki asalda izin verilen en büyük üs ve şimdiye kadar bulunan en iyi geçerli paydadır.
Arama, \(\varphi(d)\)'yi her dalda baştan hesaplamaz. Bir asal \(p\) ilk kez eklendiğinde güncelleme
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)(p-1)$$
şeklindedir. Aynı asalın üssü \(e\)'den \(e+1\)'e çıkarıldığında ise
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)p$$
kullanılır. Bu iki kural, rekürsiyon boyunca korunan temel invarianttır.
Her düğümde önce mevcut paydanın hedefi sağlayıp sağlamadığına bakılır. Sağlıyorsa yeni küresel en iyi değer olur ve dal hemen sonlandırılır; çünkü sonradan gelecek her asal çarpımı paydayı yalnızca büyütür. Mevcut payda zaten bilinen en iyi çözümden büyük ya da eşitse o dal da anında budanır.
Bir sonraki rekürsif çağrı, biraz önce kullanılan üssü yeni üst sınır olarak alır; böylece \(e_1 \ge e_2 \ge \cdots\) düzeni otomatik olarak korunur ve aynı üslerin permütasyonları hiç üretilmez. Uygulamalar yalnızca 31'e kadar olan ilk birkaç ardışık asala ihtiyaç duyar; çünkü güçlü budama altında optimum çözüm o aralıkta yakalanır. C++ sürümü karşılaştırmayı taşma riskine karşı 128-bit ile genişletir, Python sürümü sınırsız büyüklükte tamsayılar kullanır, Java sürümü ise bu hedef için güvenli biçimde 64-bit aralığında kalır.
Budama yapılmasa arama, olası üs vektörleri açısından kombinatoriyel olurdu. Gerçekte ziyaret edilen uzay daha iyi şöyle tarif edilir:
$$e_1 \ge e_2 \ge \cdots \ge 0,\qquad \prod_i p_i^{e_i} \lt d_{\text{best}},$$
burada \(d_{\text{best}}\), o ana kadar bulunmuş en iyi paydadır. Üs sıralama koşulu aynı çokluğun bütün yeniden dizilimlerini ortadan kaldırır; en iyi değer sınırı da büyük dalları büyümeden keser.
Bellek kullanımı \(O(k)\)'dir; çünkü yalnızca tek bir arama yolu rekürsiyon yığında tutulur ve \(k\) de derinliği belirtir. Bu problemde \(k\) küçük bir sabittir ve pratikte gezilen ağaç çok küçüktür. Algoritma hızlıdır, çünkü bütün tamsayıları taramak yerine yalnızca en iyi sonuca yakın olabilecek çarpanlaşmaları inceler.
Para un denominador fijo \(d\), las fracciones propias son
$$\frac{1}{d},\frac{2}{d},\dots,\frac{d-1}{d}.$$
Una fracción propia es resiliente exactamente cuando ya está en su forma irreducible. Por eso, el número de fracciones resilientes con denominador \(d\) es \(\varphi(d)\), y la resiliencia vale
$$R(d)=\frac{\varphi(d)}{d-1}.$$
El objetivo es encontrar el menor denominador \(d\) que cumpla
$$R(d) \lt \frac{15499}{94744}.$$
Probar todos los denominadores en orden no es una buena estrategia, porque la mayoría ni siquiera se acerca al mínimo buscado. La solución recorre directamente las factorizaciones primas que pueden producir un candidato óptimo.
La observación clave es que la resiliencia depende mucho más del conjunto de primos distintos que dividen a \(d\) que de los exponentes concretos de esos primos. Toda la búsqueda se organiza alrededor de esa idea.
Un numerador \(n\) produce una fracción resiliente \(n/d\) si y solo si \(\gcd(n,d)=1\). Entre los \(d-1\) numeradores posibles con \(1 \le n \lt d\), exactamente \(\varphi(d)\) son coprimos con \(d\). Así, el problema original de contar fracciones se convierte en un problema multiplicativo sobre \(\varphi(d)\).
Si escribimos
$$d=\prod_{i=1}^{k} p_i^{e_i},$$
entonces la fórmula de Euler da
$$\varphi(d)=d\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)=\prod_{i=1}^{k} p_i^{e_i-1}(p_i-1).$$
Por tanto,
$$R(d)=\frac{d}{d-1}\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right).$$
Esta identidad explica toda la estructura del algoritmo. El producto \(\prod (1-1/p_i)\) depende solo de qué primos aparecen, no de sus exponentes. Aumentar un exponente no cambia \(\varphi(d)/d\); solo sustituye el factor \(d/(d-1)\) por otro ligeramente menor y más cercano a 1. En consecuencia, introducir un nuevo primo produce la caída principal de la resiliencia, mientras que subir un exponente sirve como ajuste fino cuando el candidato ya está muy cerca del umbral.
De ahí también sale el orden natural de búsqueda. Un primo nuevo \(p\) multiplica \(\varphi(d)/d\) por \(1-1/p\), y esa reducción es más fuerte cuando \(p\) es pequeño. Por eso los candidatos mínimos nacen de productos de primos pequeños consecutivos, quizá seguidos por potencias adicionales de esos mismos primos.
Si \(p \lt q\) y \(a \gt b\), entonces
$$p^a q^b \lt p^b q^a.$$
Es decir, con los mismos dos primos y los mismos dos exponentes, el denominador siempre es menor cuando el exponente más grande se asigna al primo más pequeño. En general, para un conjunto fijo de primos y un multiconjunto fijo de exponentes, el denominador mínimo aparece cuando los exponentes no aumentan a medida que los primos crecen:
$$e_1 \ge e_2 \ge e_3 \ge \cdots.$$
Eso justifica matemáticamente la DFS usada por el código. Cualquier candidato que viole este orden puede reordenarse para obtener un denominador menor con la misma estructura esencial, así que no puede ser la respuesta mínima.
En lugar de dividir, las implementaciones comprueban la condición objetivo en la forma exacta
$$\varphi(d)\cdot 94744 \lt 15499\cdot(d-1).$$
Así se evita por completo cualquier error de coma flotante.
Un pequeño ejemplo deja claro el mecanismo. Si el umbral fuera \(4/10\), entonces \(d=6=2\cdot 3\) produce
$$\varphi(6)=2,\qquad R(6)=\frac{2}{5}=\frac{4}{10},$$
de modo que la desigualdad estricta todavía falla. En cambio, \(d=12=2^2\cdot 3\) da
$$\varphi(12)=4,\qquad R(12)=\frac{4}{11}\lt\frac{4}{10}.$$
Eso refleja exactamente el patrón del problema real: un núcleo libre de cuadrados formado por primos pequeños baja el valor muy deprisa, y luego una potencia adicional de un primo pequeño puede ser el ajuste final que cruza el límite con el menor denominador posible.
Las implementaciones en C++, Python y Java ejecutan una búsqueda en profundidad sobre primos crecientes. El estado recursivo guarda el denominador actual \(d\), el valor actual \(\varphi(d)\), la posición dentro de la lista de primos, el máximo exponente permitido para el siguiente primo y el mejor denominador válido encontrado hasta ese momento.
La búsqueda no vuelve a calcular \(\varphi(d)\) desde cero en cada rama. Cuando un primo \(p\) aparece por primera vez, la actualización es
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)(p-1).$$
Si ese mismo primo pasa del exponente \(e\) al exponente \(e+1\), la regla cambia a
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)p.$$
Esas dos transiciones son el invariante central que el algoritmo mantiene durante toda la recursión.
En cada nodo, la implementación comprueba primero si el denominador actual ya satisface la desigualdad objetivo. Si la satisface, pasa a ser el nuevo mejor valor global y la rama termina, porque multiplicar por más primos solo aumentaría \(d\). Si el denominador actual ya es mayor o igual que la mejor respuesta conocida, esa rama también se descarta de inmediato.
La llamada recursiva siguiente recibe como nuevo límite el exponente que acaba de usarse, con lo que queda forzada la condición \(e_1 \ge e_2 \ge \cdots\). Eso elimina automáticamente las permutaciones duplicadas de los mismos exponentes. Las implementaciones solo necesitan los primeros primos consecutivos hasta 31, porque el óptimo aparece dentro de ese espacio de búsqueda muy podado. C++ amplía la comparación para hacer la multiplicación cruzada con enteros de 128 bits, Python usa enteros de precisión arbitraria y Java permanece con seguridad dentro del rango de 64 bits para este objetivo.
Sin poda, el problema sería combinatorio en el conjunto de vectores de exponentes posibles. Una descripción útil del espacio realmente visitado es: la DFS solo recorre tuplas
$$e_1 \ge e_2 \ge \cdots \ge 0,\qquad \prod_i p_i^{e_i} \lt d_{\text{best}},$$
donde \(d_{\text{best}}\) es el mejor denominador conocido en ese punto de la búsqueda. La restricción sobre el orden de los exponentes elimina todas las reordenaciones del mismo multiconjunto, y la cota superior por el mejor valor conocido corta las ramas grandes antes de que crezcan.
El uso de memoria es \(O(k)\), donde \(k\) es la profundidad de la recursión, porque solo se almacena un camino del árbol a la vez. Para el objetivo real, \(k\) es una constante pequeña y el árbol visitado en la práctica es diminuto. El método es rápido porque explora solo factorizaciones cercanas al óptimo en lugar de recorrer todos los enteros.
对固定分母 \(d\) 来说，所有真分数是
$$\frac{1}{d},\frac{2}{d},\dots,\frac{d-1}{d}.$$
题目把其中已经约成最简的真分数称为“有韧性”的分数。分母为 \(d\) 的最简真分数个数正好是 \(\varphi(d)\)，因此分母 \(d\) 的韧性定义为
$$R(d)=\frac{\varphi(d)}{d-1}.$$
要求找到满足
$$R(d) \lt \frac{15499}{94744}$$
的最小分母 \(d\)。如果按顺序枚举所有分母并逐个计算欧拉函数，绝大多数工作都会浪费在明显不可能成为最优解的数上。真正有效的方法，是直接搜索那些有希望给出最小分母的质因数结构。
这道题最重要的事实是：韧性的大小主要由分母包含了哪些不同的质数决定，而不是由这些质数的幂次大小决定。实现正是围绕这一点展开的。
分子 \(n\) 对应的真分数 \(n/d\) 何时是“有韧性”的？答案正是 \(\gcd(n,d)=1\)。在 \(1 \le n \lt d\) 的 \(d-1\) 个候选分子中，恰有 \(\varphi(d)\) 个与 \(d\) 互素，所以题目中的计数对象与欧拉函数完全一致。这样一来，原问题就从“数一数哪些真分数能约分”转化成了“怎样构造一个分母，使 \(\varphi(d)/(d-1)\) 尽可能小”。
设
$$d=\prod_{i=1}^{k} p_i^{e_i},$$
则欧拉乘积公式给出
$$\varphi(d)=d\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)=\prod_{i=1}^{k} p_i^{e_i-1}(p_i-1).$$
因此
$$R(d)=\frac{d}{d-1}\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right).$$
这个恒等式把问题拆成了两部分。第一部分是 \(\prod (1-1/p_i)\)，它只取决于哪些不同的质数整除 \(d\)；第二部分是前面的修正因子 \(d/(d-1)\)，它随着 \(d\) 增大而缓慢下降并趋近于 1。于是可以立刻看出：
第一次引入一个新质数 \(p\) 时，会把 \(\varphi(d)/d\) 乘上 \(1-1/p\)，这是韧性下降的主要来源；如果只是把已经出现过的质数再多乘一次，那么 \(\varphi(d)/d\) 根本不变，只是让 \(d/(d-1)\) 略微减小一点。
这说明搜索的核心策略应该是先用若干个小质数把整体比例压下来，再用小质数的额外幂次做最后的细调。也正因为如此，最小候选几乎一定来自连续的小质数，而不是稀疏地跳到很大的质数。
设 \(p \lt q\)，同时有两个指数 \(a \gt b\)。那么
$$p^a q^b \lt p^b q^a.$$
这意味着：如果使用相同的两个质数和相同的两个指数，把较大的指数放在较小的质数上，总能得到更小的分母。推广到一般情形，对于固定的一组质数和固定的一组指数，多重集合不变时，最小分母一定出现在指数沿着递增质数表满足
$$e_1 \ge e_2 \ge e_3 \ge \cdots$$
的时候。
这不是单纯为了去重而采用的技巧，而是一个真正的最优性结论。任何不满足这个顺序的候选，都可以通过交换指数得到一个更小的分母，同时不改变“用了哪些不同质数”这一关键信息，因此它不可能是最小答案。代码中的 DFS 正是利用了这个事实，只枚举非递增的指数向量。
实现不会直接计算小数，而是把目标条件写成精确的整数不等式
$$\varphi(d)\cdot 94744 \lt 15499\cdot(d-1).$$
这样可以完全避免浮点误差。
一个小例子非常能说明问题。如果目标阈值改成 \(4/10\)，那么
$$d=6=2\cdot 3,\qquad \varphi(6)=2,\qquad R(6)=\frac{2}{5}=\frac{4}{10}.$$
因为题目要求的是严格小于，所以 \(d=6\) 还不够。再看
$$d=12=2^2\cdot 3,\qquad \varphi(12)=4,\qquad R(12)=\frac{4}{11}\lt\frac{4}{10}.$$
这里就出现了完整题目的典型模式：先用 \(2\) 和 \(3\) 这样的最小质数把比例压到临界线附近，再增加一个较小质数的幂次，把前面的修正因子 \(d/(d-1)\) 再往 1 拉近一点，从而越过严格不等式的边界。
C++、Python 和 Java 实现都采用按质数递增顺序进行的深度优先搜索。递归状态里保存当前分母 \(d\)、当前欧拉函数值 \(\varphi(d)\)、当前处理到第几个质数、下一个质数允许使用的最大指数，以及目前已经找到的最优合法分母。
实现不会在每个节点重新分解整数并重算 \(\varphi(d)\)。如果某个质数 \(p\) 第一次加入当前分母，更新规则是
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)(p-1).$$
如果同一个质数的指数从 \(e\) 增加到 \(e+1\)，则更新变为
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)p.$$
这两条递推式正是代码维护的核心不变量。它们直接对应于质数幂在欧拉函数公式中的贡献，因此每走一步都只需要做常数次整数乘法。
每次递归进入一个新状态时，程序先检查当前分母是否已经满足目标不等式。如果满足，那么它立刻成为新的最优值，这条分支就不再继续，因为再乘任何质数只会让分母更大，不可能得到更小的合法答案。如果当前分母已经不小于已知最优值，这个分支也会马上被丢弃。
同时，下一层递归会把当前使用的指数作为下一个质数的上界，这样就自动保证了 \(e_1 \ge e_2 \ge \cdots\) 的规范顺序，所有只是指数排列不同的重复候选都会被排除。实现中只需要一小段连续的小质数，直到 31 为止，因为在这种搜索顺序和剪枝之下，最优解已经会在这个范围内被发现。C++ 版本为了让交叉相乘比较绝对安全，会把整数提升到 128 位；Python 直接使用任意精度整数；Java 在这道题对应的数据范围内用 64 位整数也足够安全。
如果完全不剪枝，搜索的复杂度会随着可选指数向量的数量呈组合爆炸。更准确地说，程序真正访问的状态可以描述为满足
$$e_1 \ge e_2 \ge \cdots \ge 0,\qquad \prod_i p_i^{e_i} \lt d_{\text{best}}$$
的那些向量，其中 \(d_{\text{best}}\) 是当时已知的最优分母。非递增指数条件消除了同一组指数的所有排列，而“当前值不得超过最优解”的上界又会在非常浅的层次就砍掉大量分支。
空间复杂度是 \(O(k)\)，这里 \(k\) 是递归深度，因为任意时刻只保留一条搜索路径。对于本题实际使用的质数个数，\(k\) 是很小的常数，所以内存占用很低。运行时间之所以也很短，不是因为问题本身简单，而是因为算法只探索接近最优结构的因数分解，而不是扫描所有整数。
Для фиксированного знаменателя \(d\) собственные дроби имеют вид
$$\frac{1}{d},\frac{2}{d},\dots,\frac{d-1}{d}.$$
Дробь считается устойчивой, если она уже несократима. Поэтому число устойчивых дробей со знаменателем \(d\) равно \(\varphi(d)\), а сама устойчивость определяется формулой
$$R(d)=\frac{\varphi(d)}{d-1}.$$
Нужно найти наименьший знаменатель \(d\), для которого
$$R(d) \lt \frac{15499}{94744}.$$
Перебирать все знаменатели подряд невыгодно: почти все из них заведомо не могут быть минимальным ответом. Поэтому решение перебирает не числа как таковые, а только те разложения на простые множители, которые могут привести к наименьшему допустимому знаменателю.
Ключевое наблюдение состоит в том, что устойчивость в гораздо большей степени определяется набором различных простых делителей, чем конкретными показателями их степеней. Именно вокруг этого факта построено решение.
Числитель \(n\) даёт устойчивую дробь \(n/d\) тогда и только тогда, когда \(\gcd(n,d)=1\). Среди \(d-1\) возможных числителей \(1 \le n \lt d\) ровно \(\varphi(d)\) взаимно просты со знаменателем. Значит, исходная задача подсчёта дробей полностью сводится к анализу величины \(\varphi(d)\).
Пусть
$$d=\prod_{i=1}^{k} p_i^{e_i}.$$
Тогда по формуле Эйлера
$$\varphi(d)=d\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)=\prod_{i=1}^{k} p_i^{e_i-1}(p_i-1).$$
Следовательно,
$$R(d)=\frac{d}{d-1}\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right).$$
Именно здесь скрыта вся структура задачи. Произведение \(\prod (1-1/p_i)\) зависит только от того, какие различные простые входят в \(d\), но не зависит от величины их показателей. Увеличение показателя не меняет отношение \(\varphi(d)/d\); оно лишь чуть уменьшает множитель \(d/(d-1)\), приближая его к 1. Поэтому добавление нового простого делителя даёт основной спад устойчивости, а увеличение степени уже использованного простого служит только для тонкой настройки.
Отсюда понятно и направление поиска. Новый простой \(p\) умножает \(\varphi(d)/d\) на \(1-1/p\), и этот эффект сильнее всего для маленьких \(p\). Значит, минимальные кандидаты строятся из последовательных маленьких простых чисел, возможно с дополнительными степенями тех же самых маленьких простых.
Пусть \(p \lt q\) и \(a \gt b\). Тогда
$$p^a q^b \lt p^b q^a.$$
То есть при одном и том же наборе простых и одном и том же наборе показателей знаменатель всегда меньше, если больший показатель стоит при меньшем простом. В общем случае, для фиксированного набора простых и фиксированного мультимножества показателей минимальный знаменатель достигается только тогда, когда показатели не возрастают вдоль возрастающих простых:
$$e_1 \ge e_2 \ge e_3 \ge \cdots.$$
Это не просто удобное правило перечисления. Это аргумент корректности для DFS: любой кандидат, нарушающий такой порядок, можно перестроить в меньший знаменатель без изменения существенной структуры, и потому он не может быть оптимальным.
Вместо деления реализации проверяют целочисленное неравенство
$$\varphi(d)\cdot 94744 \lt 15499\cdot(d-1).$$
Так полностью устраняется риск ошибок округления.
Небольшой пример хорошо показывает механизм. Если бы порог был \(4/10\), то для \(d=6=2\cdot 3\)
$$\varphi(6)=2,\qquad R(6)=\frac{2}{5}=\frac{4}{10},$$
и строгого неравенства ещё нет. А для \(d=12=2^2\cdot 3\)
$$\varphi(12)=4,\qquad R(12)=\frac{4}{11}\lt\frac{4}{10}.$$
Это и есть характерная картина полной задачи: сначала произведение маленьких различных простых быстро опускает значение почти к порогу, а затем дополнительная степень маленького простого даёт минимальный знаменатель, который уже пересекает границу.
Реализации на C++, Python и Java выполняют поиск в глубину по возрастающим простым числам. Рекурсивное состояние хранит текущий знаменатель \(d\), текущее значение \(\varphi(d)\), позицию в списке простых, максимально допустимый показатель для следующего простого и лучший корректный знаменатель, найденный к данному моменту.
Алгоритм не пересчитывает \(\varphi(d)\) заново на каждом шаге. Если простой \(p\) добавляется впервые, выполняется обновление
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)(p-1).$$
Если же степень того же простого увеличивается с \(e\) до \(e+1\), используется правило
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)p.$$
Именно эти два перехода составляют главный инвариант всей рекурсии.
В каждой вершине сначала проверяется, удовлетворяет ли текущий знаменатель целевому неравенству. Если удовлетворяет, он становится новым глобальным лучшим значением, и ветвь сразу завершается, потому что дальнейшее умножение на простые числа может только увеличить знаменатель. Если текущий знаменатель уже не меньше лучшего найденного ответа, ветвь тоже отбрасывается немедленно.
Следующий рекурсивный вызов получает текущий показатель как верхнюю границу для следующего простого, поэтому условие \(e_1 \ge e_2 \ge \cdots\) соблюдается автоматически. Так исчезают все дубликаты, различающиеся только перестановкой показателей. Реализациям хватает короткого начального списка последовательных простых до 31, потому что в таком сильно отсечённом пространстве поиск достигает оптимума раньше, чем большие простые становятся нужны. В C++ сравнение выполняется с расширением до 128-битной арифметики, Python использует целые произвольной длины, а Java остаётся в безопасных пределах 64-битного типа для данного порога.
Без отсечений задача имела бы комбинаторную сложность по множеству возможных векторов показателей. Более точное описание реально посещаемых состояний таково: DFS просматривает только наборы
$$e_1 \ge e_2 \ge \cdots \ge 0,\qquad \prod_i p_i^{e_i} \lt d_{\text{best}},$$
где \(d_{\text{best}}\) обозначает лучший знаменатель, известный на текущем этапе. Условие невозрастания устраняет все перестановки одного и того же мультимножества показателей, а верхняя граница по лучшему ответу отсеивает крупные поддеревья ещё до их разрастания.
Память имеет порядок \(O(k)\), где \(k\) равно глубине рекурсии, потому что одновременно хранится только один путь поиска. Для реального целевого порога \(k\) мало и фактически посещаемое дерево очень компактно. Быстродействие достигается не перебором всех чисел, а целенаправленным обходом только почти оптимальных разложений.
للمقام الثابت \(d\)، تكون الكسور الصحيحة الأصغر من 1 هي
$$\frac{1}{d},\frac{2}{d},\dots,\frac{d-1}{d}.$$
ويُعَدُّ الكسر resilient إذا كان في أبسط صورة أصلًا، ولذلك فإن عدد الكسور resilient ذات المقام \(d\) يساوي \(\varphi(d)\). ومن ثم تُعرَّف المتانة بالصيغة
$$R(d)=\frac{\varphi(d)}{d-1}.$$
المطلوب هو إيجاد أصغر مقام \(d\) يحقق
$$R(d) \lt \frac{15499}{94744}.$$
المرور على جميع المقامات واحدًا واحدًا ليس مناسبًا، لأن أغلبها بعيد أصلًا عن أن يكون الحل الأدنى. الفكرة الصحيحة هي البحث مباشرة في التحليلات إلى عوامل أولية التي يمكن أن تنتج أصغر مقام ممكن.
الفكرة الحاسمة هنا أن المتانة تتحدد أساسًا بحسب مجموعة الأوليات المختلفة التي تقسم \(d\)، أكثر بكثير من اعتمادها على قيم الأسس نفسها. ولهذا بُني الحل كله حول الفصل بين هذين الأثرين.
يعطي البسط \(n\) كسرًا resilient من الصورة \(n/d\) إذا وفقط إذا كان \(\gcd(n,d)=1\). وبين جميع البسوط الممكنة \(1 \le n \lt d\)، يوجد بالضبط \(\varphi(d)\) عددًا أوليًا نسبيًا مع \(d\). وهكذا تتحول المسألة من عدّ الكسور غير القابلة للاختزال إلى مسألة نظرية أعداد مضاعِفة تتحكم فيها دالة أويلر مباشرة.
إذا كتبنا
$$d=\prod_{i=1}^{k} p_i^{e_i},$$
فإن صيغة أويلر تعطي
$$\varphi(d)=d\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)=\prod_{i=1}^{k} p_i^{e_i-1}(p_i-1).$$
ومن ثم
$$R(d)=\frac{d}{d-1}\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right).$$
هذه الصيغة هي لبّ الحل. فالجداء \(\prod (1-1/p_i)\) يعتمد فقط على أي أوليات مختلفة تظهر في \(d\)، ولا يعتمد على كِبَر الأسس. زيادة أسٍّ موجود لا تغيّر النسبة \(\varphi(d)/d\) أصلًا؛ بل تجعل العامل \(d/(d-1)\) أصغر قليلًا وأقرب إلى 1. لذلك فإن إدخال أولي جديد هو ما يسبب الهبوط الكبير في المتانة، أما زيادة قوة أولي موجود فهي أداة ضبط دقيقة عندما يكون المرشح قريبًا من الحد المطلوب.
ولهذا يبدأ البحث من أصغر الأوليات. فإضافة أولي جديد \(p\) تضرب \(\varphi(d)/d\) في العامل \(1-1/p\)، وهذا الأثر أقوى كلما كان \(p\) أصغر. لذا فإن أصغر المرشحين ينشأ عادة من جداء أوليات صغيرة متتالية، ثم قد تُضاف قوى أخرى لتلك الأوليات الصغيرة نفسها من أجل الوصول إلى الحد بأصغر مقام.
إذا كان \(p \lt q\) و\(a \gt b\)، فلدينا
$$p^a q^b \lt p^b q^a.$$
أي إن استخدام الأس الأكبر مع الأولي الأصغر يعطي دائمًا مقامًا أصغر عندما تبقى مجموعة الأوليات ومجموعة الأسس نفسها ثابتة. وبصورة عامة، إذا ثبتت الأوليات وثبتت مجموعة الأسس، فإن أصغر مقام يظهر عندما تكون الأسس غير متزايدة مع ازدياد الأوليات:
$$e_1 \ge e_2 \ge e_3 \ge \cdots.$$
هذا ليس مجرد أسلوب لتنظيم التعداد، بل هو سبب صحة البحث العميق نفسه. فأي مرشح يخالف هذا الترتيب يمكن إعادة ترتيبه إلى مقام أصغر مع الحفاظ على البنية الجوهرية نفسها، ولذلك لا يمكن أن يكون هو الحل الأدنى.
بدلًا من إجراء القسمة، تستخدم التطبيقات المقارنة الصحيحة التالية:
$$\varphi(d)\cdot 94744 \lt 15499\cdot(d-1).$$
وبذلك تختفي تمامًا أخطاء الفاصلة العائمة.
يوضح مثال صغير الفكرة جيدًا. لو كان الحد المطلوب هو \(4/10\)، فإن
$$d=6=2\cdot 3,\qquad \varphi(6)=2,\qquad R(6)=\frac{2}{5}=\frac{4}{10}.$$
لكن الشرط في المسألة صارم، لذلك لا يكفي التساوي. أما
$$d=12=2^2\cdot 3,\qquad \varphi(12)=4,\qquad R(12)=\frac{4}{11}\lt\frac{4}{10}$$
فهو يحقق الشرط. وهذا هو النمط نفسه في المسألة الأصلية: جداء أوليات صغيرة مختلفة يهبط بالقيمة بسرعة نحو العتبة، ثم تعطي قوة إضافية لأولي صغير التعديل الأخير الذي يعبر الحد بأصغر مقام.
تنفذ تطبيقات C++ وPython وJava بحثًا عمقيًا على أوليات مرتبة تصاعديًا. وتحمل حالة الاستدعاء العودي المقام الحالي \(d\)، والقيمة الحالية \(\varphi(d)\)، وموقعنا في قائمة الأوليات، وأكبر أس مسموح به للأولي التالي، وأفضل مقام صالح عُثر عليه حتى الآن.
لا تعيد الشيفرة حساب \(\varphi(d)\) من الصفر في كل فرع. عندما يدخل أولي \(p\) لأول مرة، يكون التحديث
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)(p-1).$$
أما إذا زادت قوة الأولي نفسه من \(e\) إلى \(e+1\)، فيصبح التحديث
$$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)p.$$
هاتان العلاقتان هما الثابت الأساسي الذي تحافظ عليه عملية البحث طوال الاستدعاءات العودية.
في كل عقدة، تفحص التطبيقات أولًا هل المقام الحالي يحقق المتباينة المطلوبة أم لا. فإذا حققها، يُسجَّل باعتباره أفضل قيمة عالمية جديدة وتتوقف تلك الشعبة فورًا، لأن ضرب المقام في أوليات إضافية لا يمكن إلا أن يزيده. وإذا كان المقام الحالي أصلًا أكبر من أو مساويًا لأفضل جواب معروف، فتُقصّ تلك الشعبة مباشرة.
ويتلقى الاستدعاء التالي الأس الحالي بصفته حدًا أعلى للأولي التالي، وبذلك يُفرض الترتيب \(e_1 \ge e_2 \ge \cdots\) تلقائيًا وتُحذف جميع الحالات المكررة التي تختلف فقط بترتيب الأسس. وتكتفي التطبيقات بقائمة قصيرة من الأوليات الصغيرة المتتالية حتى 31، لأن الحل الأمثل يظهر داخل هذا الفضاء المقصوص بقوة قبل أن تصبح الأوليات الأكبر ذات صلة. في C++ تُوسَّع المقارنة إلى حساب صحيح 128-بت لزيادة الأمان، وفي Python تُستخدم أعداد صحيحة غير محدودة الحجم، أما Java فتبقى ضمن مجال 64-بت بأمان لهذا الهدف.
من دون قصّ الفروع سيكون البحث ذا طبيعة توافقية بالنسبة إلى جميع متجهات الأسس الممكنة. والوصف الأدق للحالات التي تُزار فعليًا هو أن البحث لا يستكشف إلا المتجهات
$$e_1 \ge e_2 \ge \cdots \ge 0,\qquad \prod_i p_i^{e_i} \lt d_{\text{best}},$$
حيث يمثّل \(d_{\text{best}}\) أفضل مقام معروف عند تلك اللحظة. شرط عدم ازدياد الأسس يزيل كل تبديلات المجموعة نفسها، وحدُّ أفضل جواب يقطع الفروع الكبيرة قبل أن تتضخم.
استهلاك الذاكرة هو \(O(k)\)، حيث \(k\) عمق الاستدعاء العودي، لأن البرنامج يحتفظ بمسار واحد فقط في الشجرة في كل لحظة. وفي المسألة الفعلية تكون \(k\) ثابتة صغيرة، والشجرة التي تُزار عمليًا صغيرة جدًا. ترجع السرعة العملية إلى أن الخوارزمية لا تمسح جميع الأعداد، بل تركز فقط على التحليلات القريبة من البنية المثلى.