For \(n = 43!\), we seek ordered factor triples \((a,b,c)\) satisfying
$$a \le b \le c,\qquad abc = n.$$
The primary objective is to make the triple as balanced as possible, which means minimizing the ratio \(c/a\). If several triples achieve the same optimal ratio, the required output is the smallest possible value of \(a+b+c\).
The implementations do not enumerate every factor triple directly. Instead they work with the prime factorization of \(43!\), search balanced exponent distributions first, and then refine the best result with an exact divisor search.
For each prime \(p \le 43\), the exponent of \(p\) in \(43!\) is given by Legendre's formula
$$e_p = \sum_{k \ge 1} \left\lfloor \frac{43}{p^k} \right\rfloor.$$
Hence
$$43! = 2^{39} 3^{19} 5^9 7^6 11^3 13^3 17^2 19^2 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43.$$
Every admissible triple is therefore equivalent to choosing, for each prime \(p\), three nonnegative exponents \(\alpha_p,\beta_p,\gamma_p\) such that
$$\alpha_p + \beta_p + \gamma_p = e_p,$$
and then setting
$$a = \prod_{p \le 43} p^{\alpha_p},\qquad b = \prod_{p \le 43} p^{\beta_p},\qquad c = \prod_{p \le 43} p^{\gamma_p}.$$
Because the logarithm is strictly increasing, minimizing \(c/a\) is equivalent to minimizing
$$\Delta = \log c - \log a.$$
This turns the multiplicative balancing problem into an additive one. If the three current factors have sorted logarithms
$$L_1 \le L_2 \le L_3,$$
then the current quality of the triple is exactly the log-range \(L_3 - L_1\). A perfectly balanced triple would make that range as small as possible.
Before the expensive search begins, the implementation constructs a valid triple greedily. Prime copies are processed from large to small, and each copy is assigned to the currently smallest logarithmic bucket. This is not guaranteed to be optimal, but it usually produces a fairly balanced triple very quickly.
That first triple provides an initial upper bound on \(\Delta\). Once such a bound exists, later search branches can be discarded as soon as they can no longer beat it.
For one prime power \(p^e\), the number of three-way exponent splits is
$$\binom{e+2}{2},$$
because we are counting nonnegative integer solutions of \(x+y+z=e\). Naively taking the Cartesian product over all primes would be enormous, so the implementation explores these choices with branch-and-bound.
The split candidates for a fixed exponent \(e\) are tried in an order that favors balanced distributions first. The priority is determined by a small spread
$$\max(x,y,z) - \min(x,y,z),$$
and then by closeness to \(e/3\), measured by
$$|3x-e| + |3y-e| + |3z-e|.$$
After each prime is assigned, the three partial factors are re-sorted by size. This is important: only the ordered triple matters in the end, so sorting removes symmetric duplicates and keeps the pruning formulas simple.
Suppose the current sorted logarithms are \(L_1 \le L_2 \le L_3\), and the primes that have not been assigned yet contribute total logarithmic mass \(R\). Even if that remaining mass could be split continuously, the smallest possible final range is obtained by filling the smaller bins first. The resulting optimistic lower bound is
$$\operatorname{LB}(L_1,L_2,L_3,R) = \begin{cases} L_3 - (L_1 + R), & R \le L_2 - L_1, \\ L_3 - \left(L_2 + \frac{R-(L_2-L_1)}{2}\right), & L_2 - L_1 \lt R \le L_2 - L_1 + 2(L_3-L_2), \\ 0, & R > L_2 - L_1 + 2(L_3-L_2). \end{cases}$$
The meaning is straightforward. First use the remaining logarithmic mass to raise the smallest factor until it reaches the middle one. Then use any leftover mass to raise the two smaller factors together toward the largest one. If even that is not enough to beat the best known range, the entire branch is pruned.
This bound is safe because the real problem is more restrictive than the continuous relaxation: prime exponents are discrete and tied to specific primes, so the true achievable range can only be larger.
Phase A already produces an excellent ratio \(R^\ast = c^\ast / a^\ast\). The second phase turns that ratio into a search window for the smallest factor \(a\).
From \(a \le b \le c\) and \(abc = n\), we always have
$$a \le n^{1/3}.$$
Now assume a candidate triple is at least as good as the current best, so \(c/a \le R^\ast\). Because \(b \le c\),
$$n = abc \le a c^2 \le a(R^\ast a)^2 = (R^\ast)^2 a^3,$$
which yields
$$a \ge \left(\frac{n}{(R^\ast)^2}\right)^{1/3}.$$
Therefore phase B only needs to inspect divisors \(a\) inside the narrow interval
$$\left(\frac{n}{(R^\ast)^2}\right)^{1/3} \le a \le n^{1/3}.$$
The implementation enumerates precisely those divisors by walking through the exponent choices for \(a\), again pruning with logarithmic lower and upper bounds.
Once \(a\) is fixed, define
$$q = \frac{n}{a} = bc.$$
For this fixed \(a\), minimizing \(c/a\) is the same as minimizing \(c\), and since \(bc=q\), that is equivalent to maximizing \(b\). The ordering constraint \(b \le c\) becomes
$$b \le \sqrt{q}.$$
So the best possible companion factor is simply the largest divisor of \(q\) that does not exceed \(\sqrt{q}\). Once that \(b\) is found, the third factor is forced:
$$c = \frac{q}{b}.$$
The residual factorization of \(q\) is already known from the chosen exponents of \(a\), so the implementation searches that divisor space directly. It also uses an upper bound from the remaining prime powers to prune branches that cannot improve the current best \(b\).
Logs are used only for pruning. The final comparison between candidate triples is exact. To compare the current candidate \((a,b,c)\) with the best-known triple \((a^\ast,b^\ast,c^\ast)\), it is enough to compare
$$c a^\ast \quad \text{and} \quad c^\ast a.$$
If the ratios are equal, the tie is resolved by the smaller sum \(a+b+c\).
A simple checkpoint is \(n=165=3\cdot 5 \cdot 11\). The only ordered factor triple is \((3,5,11)\), so the optimal sum is \(19\). The implementations verify themselves on small checkpoints of this kind before moving to \(43!\).
The C++, Python, and Java implementations all follow the same structure. First they compute the prime exponents of \(43!\) and precompute prime powers. Then they generate every three-way split for each exponent value and sort those splits so balanced choices are examined first. A greedy construction gives the initial admissible triple.
After that, phase A performs a depth-first branch-and-bound search in log-space, always keeping the three partial factors sorted. Phase B then enumerates only the admissible divisors for the smallest factor, reconstructs the residual factorization, and finds the largest allowed companion divisor below the square-root threshold. The final choice is made with exact integer arithmetic, so floating-point approximation never decides correctness.
If \(n = \prod p^{e_p}\), phase A would naively examine
$$\prod_p \binom{e_p+2}{2}$$
branches, which is exponential in the prime-exponent structure. Phase B is also combinatorial: in the worst case it may inspect many divisors in the admissible interval for \(a\), and for each one it performs a recursive search for the best residual divisor \(b\).
So there is no simple polynomial worst-case bound in \(\log n\). The method is practical here because four ideas remove most of the search space: a strong greedy seed, balanced ordering of exponent splits, the continuous lower bound on the attainable log-range, and pruning inside the residual divisor search. Memory use remains modest and is dominated by the stored prime powers, split tables, and recursion state.
Für \(n = 43!\) suchen wir geordnete Faktordreier \((a,b,c)\) mit
$$a \le b \le c,\qquad abc = n.$$
Das Hauptziel ist, die Dreiergruppe möglichst ausgewogen zu machen, also den Quotienten \(c/a\) zu minimieren. Falls mehrere Dreier denselben optimalen Quotienten besitzen, wird der kleinste Wert von \(a+b+c\) benötigt.
Die Implementierungen durchsuchen nicht blind alle Faktordreier. Stattdessen verwenden sie die Primfaktorzerlegung von \(43!\), untersuchen zuerst ausgeglichene Exponentenverteilungen und verfeinern das beste Ergebnis danach mit einer exakten Teilersuche.
Für jede Primzahl \(p \le 43\) liefert die Legendre-Formel den Exponenten von \(p\) in \(43!\):
$$e_p = \sum_{k \ge 1} \left\lfloor \frac{43}{p^k} \right\rfloor.$$
Daraus folgt
$$43! = 2^{39} 3^{19} 5^9 7^6 11^3 13^3 17^2 19^2 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43.$$
Jedes zulässige Dreier entspricht also der Wahl nichtnegativer Exponenten \(\alpha_p,\beta_p,\gamma_p\) mit
$$\alpha_p + \beta_p + \gamma_p = e_p,$$
woraus
$$a = \prod_{p \le 43} p^{\alpha_p},\qquad b = \prod_{p \le 43} p^{\beta_p},\qquad c = \prod_{p \le 43} p^{\gamma_p}$$
entsteht.
Weil der Logarithmus streng monoton wächst, ist die Minimierung von \(c/a\) äquivalent zur Minimierung von
$$\Delta = \log c - \log a.$$
Damit wird ein multiplikatives Balanceproblem in ein additives Problem verwandelt. Haben die drei aktuellen Faktoren die sortierten Logarithmen
$$L_1 \le L_2 \le L_3,$$
dann ist die Güte des aktuellen Dreiers genau die Spannweite \(L_3 - L_1\).
Vor der eigentlichen Suche erzeugt die Implementierung zunächst ein gültiges Dreier mit einer gierigen Regel. Kopien großer Primzahlen werden der Reihe nach dem momentan kleinsten Logarithmusbehälter zugeordnet. Das ist nicht immer optimal, liefert aber sehr schnell ein ordentlich ausbalanciertes Dreier.
Dieses erste Dreier liefert eine obere Schranke für \(\Delta\). Sobald eine solche Schranke existiert, können spätere Suchzweige verworfen werden, wenn sie sie garantiert nicht mehr unterbieten können.
Für eine einzelne Primzahlpotenz \(p^e\) gibt es
$$\binom{e+2}{2}$$
Möglichkeiten, den Exponenten auf drei Faktoren zu verteilen, denn wir zählen nichtnegative Lösungen von \(x+y+z=e\). Das direkte kartesische Produkt über alle Primzahlen wäre riesig, daher wird mit Branch-and-Bound gesucht.
Die Splits für einen festen Exponenten \(e\) werden so sortiert, dass ausgewogene Verteilungen zuerst kommen. Priorisiert werden kleine Werte von
$$\max(x,y,z) - \min(x,y,z),$$
danach die Nähe zu \(e/3\), gemessen durch
$$|3x-e| + |3y-e| + |3z-e|.$$
Nach jeder Primzahlzuordnung werden die drei partiellen Faktoren neu sortiert. Das ist entscheidend, weil am Ende nur das geordnete Dreier zählt. Durch das Sortieren verschwinden symmetrische Duplikate, und die Schrankenformeln bleiben einfach.
Seien \(L_1 \le L_2 \le L_3\) die aktuellen sortierten Logarithmen, und sei \(R\) die gesamte noch nicht verteilte Log-Masse der restlichen Primzahlen. Selbst wenn man diese Masse kontinuierlich aufteilen dürfte, erhält man die kleinste mögliche Endspannweite, indem man zuerst die kleineren Behälter auffüllt. Daraus ergibt sich die optimistische untere Schranke
$$\operatorname{LB}(L_1,L_2,L_3,R) = \begin{cases} L_3 - (L_1 + R), & R \le L_2 - L_1, \\ L_3 - \left(L_2 + \frac{R-(L_2-L_1)}{2}\right), & L_2 - L_1 \lt R \le L_2 - L_1 + 2(L_3-L_2), \\ 0, & R > L_2 - L_1 + 2(L_3-L_2). \end{cases}$$
Die Interpretation ist einfach. Zuerst hebt man den kleinsten Faktor bis zum mittleren an. Verbleibende Masse hebt dann die beiden kleineren gemeinsam in Richtung des größten an. Wenn schon diese optimistische Schranke die beste bekannte Spannweite nicht mehr schlagen kann, wird der komplette Zweig abgeschnitten.
Die Schranke ist korrekt, weil die echte Aufgabe stärker eingeschränkt ist als die kontinuierliche Relaxation: Exponenten sind diskret und an konkrete Primzahlen gebunden, also kann die tatsächlich erreichbare Spannweite nur größer sein.
Phase A liefert bereits einen sehr guten Quotienten \(R^\ast = c^\ast / a^\ast\). Die zweite Phase wandelt diesen Quotienten in ein Suchfenster für den kleinsten Faktor \(a\) um.
Aus \(a \le b \le c\) und \(abc = n\) folgt immer
$$a \le n^{1/3}.$$
Nehmen wir nun an, ein Kandidat ist mindestens so gut wie das bisher beste Dreier, also \(c/a \le R^\ast\). Wegen \(b \le c\) gilt
$$n = abc \le a c^2 \le a(R^\ast a)^2 = (R^\ast)^2 a^3,$$
also
$$a \ge \left(\frac{n}{(R^\ast)^2}\right)^{1/3}.$$
Damit muss Phase B nur noch Divisoren \(a\) im schmalen Intervall
$$\left(\frac{n}{(R^\ast)^2}\right)^{1/3} \le a \le n^{1/3}$$
betrachten. Genau diese Divisoren erzeugt die Implementierung wieder aus den Primexponenten, ergänzt um logarithmische Unter- und Oberschranken.
Ist \(a\) fest, so setzen wir
$$q = \frac{n}{a} = bc.$$
Für dieses feste \(a\) ist die Minimierung von \(c/a\) gleichbedeutend mit der Minimierung von \(c\), und da \(bc=q\), ist das wiederum gleichbedeutend mit der Maximierung von \(b\). Die Ordnungsbedingung \(b \le c\) wird zu
$$b \le \sqrt{q}.$$
Also ist der beste Begleitfaktor schlicht der größte Teiler von \(q\), der \(\sqrt{q}\) nicht überschreitet. Danach ist
$$c = \frac{q}{b}$$
bereits festgelegt. Die Restfaktorisierung von \(q\) ist aus den gewählten Exponenten von \(a\) bekannt, daher durchsucht die Implementierung genau diesen Teilraum. Zusätzlich verwirft sie Zweige, deren verbleibende Primzahlpotenzen keinen besseren Wert für \(b\) mehr zulassen.
Logarithmen dienen nur zum Pruning. Der endgültige Vergleich zweier Kandidaten erfolgt exakt. Um den Kandidaten \((a,b,c)\) mit dem besten bekannten Dreier \((a^\ast,b^\ast,c^\ast)\) zu vergleichen, genügt der Vergleich von
$$c a^\ast \quad \text{und} \quad c^\ast a.$$
Sind die Quotienten gleich, entscheidet die kleinere Summe \(a+b+c\).
Ein einfacher Kontrollfall ist \(n=165=3\cdot 5 \cdot 11\). Das einzige geordnete Faktordreier ist \((3,5,11)\), also ist die optimale Summe \(19\). Solche und größere Kontrollwerte werden vor \(43!\) geprüft.
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Zuerst werden die Primexponenten von \(43!\) berechnet und die nötigen Primzahlpotenzen vorab gespeichert. Danach werden für jeden Exponentenwert alle Dreifach-Splits erzeugt und so sortiert, dass ausgewogene Verteilungen zuerst untersucht werden. Eine gierige Konstruktion liefert das erste zulässige Dreier.
Anschließend läuft Phase A als Tiefensuche mit Branch-and-Bound im Logarithmusraum, wobei die drei partiellen Faktoren stets sortiert gehalten werden. Phase B erzeugt dann nur noch die zulässigen Divisoren für den kleinsten Faktor, rekonstruiert daraus die Restfaktorisierung und sucht den größten erlaubten Begleitteiler unterhalb der Quadratwurzelgrenze. Die endgültige Auswahl basiert auf exakter Ganzzahlarithmetik; Gleitkommazahlen steuern nur das Pruning.
Für \(n = \prod p^{e_p}\) müsste Phase A naiv
$$\prod_p \binom{e_p+2}{2}$$
Zweige untersuchen, also exponentiell viele im Aufbau der Primexponenten. Phase B ist ebenfalls kombinatorisch: Im schlechtesten Fall müssen viele Divisoren im zulässigen Intervall für \(a\) betrachtet werden, und für jeden davon wird rekursiv nach dem besten Restteiler \(b\) gesucht.
Es gibt daher keine einfache polynomielle Worst-Case-Schranke in \(\log n\). Praktisch funktioniert das Verfahren trotzdem, weil vier Ideen den Suchraum massiv verkleinern: ein guter gieriger Startwert, die ausgewogene Reihenfolge der Splits, die kontinuierliche untere Schranke für die erreichbare Log-Spannweite und zusätzliches Pruning in der Restteilersuche. Der Speicherbedarf bleibt klein und wird vor allem durch Primzahlpotenzen, Split-Tabellen und Rekursionszustände bestimmt.
\(n = 43!\) için
$$a \le b \le c,\qquad abc = n$$
koşulunu sağlayan sıralı çarpan üçlülerini arıyoruz. Asıl amaç, üçlüyü mümkün olduğunca dengeli yapmak, yani \(c/a\) oranını en aza indirmektir. Aynı en iyi oranı veren birden fazla üçlü varsa, bu kez \(a+b+c\) toplamı en küçük olan seçilir.
Uygulamalar bütün üçlüleri doğrudan denemez. Bunun yerine \(43!\)'ün asal çarpan yapısını kullanır, önce dengeli üs dağılımlarını araştırır, sonra da en iyi sonucu tam bir bölen aramasıyla keskinleştirir.
\(p \le 43\) olan her asal için, \(43!\) içindeki üs Legendre formülüyle bulunur:
$$e_p = \sum_{k \ge 1} \left\lfloor \frac{43}{p^k} \right\rfloor.$$
Böylece
$$43! = 2^{39} 3^{19} 5^9 7^6 11^3 13^3 17^2 19^2 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43.$$
Dolayısıyla her geçerli üçlü, her asal \(p\) için \(\alpha_p,\beta_p,\gamma_p \ge 0\) olacak şekilde
$$\alpha_p + \beta_p + \gamma_p = e_p$$
seçiminden oluşur ve
$$a = \prod_{p \le 43} p^{\alpha_p},\qquad b = \prod_{p \le 43} p^{\beta_p},\qquad c = \prod_{p \le 43} p^{\gamma_p}$$
şeklinde kurulur.
Logaritma sıkı artan olduğundan, \(c/a\) oranını küçültmek ile
$$\Delta = \log c - \log a$$
değerini küçültmek aynı şeydir. Böylece çarpımsal denge problemi toplamsal bir probleme dönüşür. Üç kısmi çarpanın sıralı logaritmaları
$$L_1 \le L_2 \le L_3$$
ise mevcut kalitenin ölçüsü doğrudan \(L_3-L_1\) log-açıklığıdır.
Asıl derin aramadan önce uygulama geçerli bir üçlüyü açgözlü biçimde kurar. Büyük asalların her kopyası, o anda logaritması en küçük olan kovaya eklenir. Bu yöntem her zaman optimal değildir, ama çoğu zaman hızlıca iyi dengelenmiş bir üçlü üretir.
Bu ilk üçlü, \(\Delta\) için başlangıç üst sınırını verir. Böyle bir sınır oluştuğunda, artık onu geçemeyecek dallar daha erken budanabilir.
Tek bir \(p^e\) asal kuvveti için, üssü üç faktöre dağıtmanın sayısı
$$\binom{e+2}{2}$$
kadardır; çünkü \(x+y+z=e\) denkleminin negatif olmayan çözümlerini sayıyoruz. Tüm asallar üzerinde bunu doğrudan çarpmak aşırı büyüktür, bu yüzden uygulama branch-and-bound kullanır.
Sabit bir \(e\) için aday bölüşümler, önce dengeli olanlar gelecek şekilde sıralanır. Öncelik
$$\max(x,y,z) - \min(x,y,z)$$
ifadesinin küçük olmasına verilir; ikinci ölçüt ise \(e/3\)'e yakınlıktır:
$$|3x-e| + |3y-e| + |3z-e|.$$
Her asal işlendiğinde üç kısmi çarpan tekrar sıralanır. Bunun nedeni, sonunda sadece sıralı üçlünün önemli olmasıdır. Bu yeniden sıralama simetrik tekrarları kaldırır ve budama formüllerini sadeleştirir.
Geçerli sıralı logaritmalar \(L_1 \le L_2 \le L_3\) olsun ve henüz atanmamış asal kuvvetlerin toplam logaritmik kütlesi \(R\) olsun. Bu kütlenin sürekli biçimde dağıtılabildiğini varsaysak bile, en küçük olası son açıklık önce küçük kovaları doldurarak elde edilir. Böylece iyimser alt sınır
$$\operatorname{LB}(L_1,L_2,L_3,R) = \begin{cases} L_3 - (L_1 + R), & R \le L_2 - L_1, \\ L_3 - \left(L_2 + \frac{R-(L_2-L_1)}{2}\right), & L_2 - L_1 \lt R \le L_2 - L_1 + 2(L_3-L_2), \\ 0, & R > L_2 - L_1 + 2(L_3-L_2). \end{cases}$$
Yorum basittir. Önce en küçük logaritma ortadakine kadar yükseltilir. Kalan kütle varsa bu kez iki küçük kova birlikte büyütülür. Bu iyimser alt sınır bile eldeki en iyi açıklığı yenemiyorsa dalın tamamı budanır.
Bu sınır güvenlidir; çünkü gerçek problem sürekli modele göre daha kısıtlıdır. Üsler ayrık değerlidir ve belirli asallara bağlıdır, dolayısıyla gerçekte erişilebilecek açıklık bu alt sınırdan daha küçük olamaz.
Faz A zaten çok iyi bir oran \(R^\ast = c^\ast / a^\ast\) üretir. İkinci faz bu oranı, en küçük çarpan \(a\) için bir arama penceresine çevirir.
\(a \le b \le c\) ve \(abc=n\) olduğundan her zaman
$$a \le n^{1/3}$$
vardır. Şimdi bir adayın mevcut en iyi çözüm kadar iyi olduğunu, yani \(c/a \le R^\ast\) olduğunu varsayalım. \(b \le c\) olduğu için
$$n = abc \le a c^2 \le a(R^\ast a)^2 = (R^\ast)^2 a^3,$$
ve buradan
$$a \ge \left(\frac{n}{(R^\ast)^2}\right)^{1/3}$$
çıkar. Demek ki Faz B yalnızca
$$\left(\frac{n}{(R^\ast)^2}\right)^{1/3} \le a \le n^{1/3}$$
aralığındaki bölenleri incelemek zorundadır. Uygulama bu bölenleri yine asal üslerinden üretir ve logaritmik alt-üst sınırlarla budar.
\(a\) sabitlendiğinde
$$q = \frac{n}{a} = bc$$
tanımlanır. Bu sabit \(a\) için \(c/a\) oranını küçültmek, \(c\)'yi küçültmekle aynıdır. \(bc=q\) olduğundan bu da \(b\)'yi büyütmek anlamına gelir. Sıralama koşulu \(b \le c\) ise
$$b \le \sqrt{q}$$
şeklindedir. Bu yüzden en iyi yardımcı çarpan, \(q\)'nun \(\sqrt{q}\)'yu aşmayan en büyük bölenidir. Ardından
$$c = \frac{q}{b}$$
zorunlu olarak belirlenir. \(q\)'nun kalan asal üsleri zaten bilindiğinden, uygulama bu bölen uzayını doğrudan arar. Ayrıca kalan asal kuvvetlerin sağlayabileceği üst sınırı kullanarak daha iyi \(b\) veremeyecek dalları keser.
Logaritmalar yalnızca budama için kullanılır. Son karşılaştırma tam sayı aritmetiğiyle yapılır. Bir aday \((a,b,c)\) ile mevcut en iyi üçlü \((a^\ast,b^\ast,c^\ast)\) karşılaştırılırken
$$c a^\ast \quad \text{ve} \quad c^\ast a$$
karşılaştırması yeterlidir. Oranlar eşitse daha küçük \(a+b+c\) toplamı seçilir.
Basit bir kontrol örneği \(n=165=3\cdot 5 \cdot 11\)'dir. Tek sıralı çarpan üçlüsü \((3,5,11)\) olduğundan en iyi toplam \(19\)'dur. Uygulamalar \(43!\)'ten önce buna benzer küçük testlerle doğrulanır.
C++, Python ve Java uygulamalarının akışı aynıdır. Önce \(43!\)'ün asal üsleri hesaplanır ve gerekli asal kuvvetler önceden hazırlanır. Sonra her üs değeri için tüm üçlü bölüşümler üretilir ve dengeli seçimler önce gelecek biçimde sıralanır. Açgözlü kurulum ilk geçerli üçlüyü verir.
Bundan sonra Faz A, log-uzayında derinlik öncelikli branch-and-bound araması yapar ve üç kısmi çarpanı her adımda sıralı tutar. Faz B ise yalnızca izin verilen en küçük çarpan bölenlerini dolaşır, kalan çarpanlaşmayı yeniden kurar ve karekök eşiğinin altındaki en büyük yardımcı böleni bulur. Son karar tam sayı aritmetiğiyle verildiği için kayan nokta sayıları doğruluğu değil, sadece budamayı etkiler.
\(n = \prod p^{e_p}\) için Faz A naif olarak
$$\prod_p \binom{e_p+2}{2}$$
adet dal incelemek zorunda kalır; bu, asal üs yapısına göre üstel bir büyüklüktür. Faz B de kombinatoriktir: en kötü durumda \(a\) için izin verilen aralıktaki çok sayıda bölen incelenebilir ve her biri için kalan en iyi \(b\) böleni rekürsif olarak aranır.
Bu nedenle \(\log n\) cinsinden basit bir polinomik üst sınır yoktur. Yöntemin pratikte çalışmasının nedeni dört güçlü daraltmadır: iyi bir açgözlü başlangıç, dengeli bölüşümleri öne alan sıralama, erişilebilir log-açıklığı için sürekli alt sınır ve kalan bölen aramasındaki ek budamalar. Bellek kullanımı düşüktür; asıl yük önceden hesaplanan asal kuvvetler, bölüşüm tabloları ve rekürsiyon durumudur.
Para \(n = 43!\), buscamos ternas ordenadas \((a,b,c)\) que cumplan
$$a \le b \le c,\qquad abc = n.$$
El objetivo principal es que la terna quede lo más equilibrada posible, es decir, minimizar la razón \(c/a\). Si varias ternas alcanzan la misma razón óptima, se elige la que tenga el menor valor de \(a+b+c\).
Las implementaciones no prueban todas las ternas de factores una por una. En su lugar usan la factorización prima de \(43!\), exploran primero las distribuciones de exponentes más equilibradas y luego refinan el mejor resultado con una búsqueda exacta de divisores.
Para cada primo \(p \le 43\), el exponente de \(p\) en \(43!\) viene dado por la fórmula de Legendre:
$$e_p = \sum_{k \ge 1} \left\lfloor \frac{43}{p^k} \right\rfloor.$$
Por tanto,
$$43! = 2^{39} 3^{19} 5^9 7^6 11^3 13^3 17^2 19^2 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43.$$
Cada terna admisible equivale a elegir, para cada primo \(p\), exponentes no negativos \(\alpha_p,\beta_p,\gamma_p\) tales que
$$\alpha_p + \beta_p + \gamma_p = e_p,$$
y entonces definir
$$a = \prod_{p \le 43} p^{\alpha_p},\qquad b = \prod_{p \le 43} p^{\beta_p},\qquad c = \prod_{p \le 43} p^{\gamma_p}.$$
Como el logaritmo es estrictamente creciente, minimizar \(c/a\) equivale a minimizar
$$\Delta = \log c - \log a.$$
Así, un problema multiplicativo de equilibrio se convierte en uno aditivo. Si los logaritmos actuales de los tres factores, ya ordenados, son
$$L_1 \le L_2 \le L_3,$$
la calidad actual de la terna viene dada exactamente por el rango logarítmico \(L_3-L_1\).
Antes de la búsqueda profunda, la implementación construye una terna válida de manera voraz. Las copias de los primos grandes se procesan de mayor a menor, y cada copia se envía al cubo cuyo logaritmo acumulado es el menor en ese instante. Esto no garantiza optimalidad, pero produce muy rápido una terna razonablemente equilibrada.
Esa primera terna aporta una cota superior inicial para \(\Delta\). A partir de ahí, cualquier rama que no pueda mejorarla se descarta inmediatamente.
Para una sola potencia prima \(p^e\), el número de repartos del exponente entre tres factores es
$$\binom{e+2}{2},$$
porque contamos las soluciones enteras no negativas de \(x+y+z=e\). Hacer el producto cartesiano sobre todos los primos sería gigantesco, así que la búsqueda se organiza con branch-and-bound.
Los repartos para un exponente fijo \(e\) se prueban en un orden que favorece primero las distribuciones equilibradas. Se prioriza un pequeño valor de
$$\max(x,y,z) - \min(x,y,z),$$
y después la cercanía a \(e/3\), medida por
$$|3x-e| + |3y-e| + |3z-e|.$$
Tras asignar cada primo, los tres factores parciales se vuelven a ordenar por tamaño. Esto elimina duplicados simétricos y hace que las cotas de poda sean mucho más limpias.
Supongamos que los logaritmos actuales, ya ordenados, son \(L_1 \le L_2 \le L_3\), y que la masa logarítmica total de los primos aún no asignados es \(R\). Incluso si esa masa pudiera repartirse de manera continua, el menor rango final posible se obtiene llenando primero los cubos pequeños. La cota inferior optimista es
$$\operatorname{LB}(L_1,L_2,L_3,R) = \begin{cases} L_3 - (L_1 + R), & R \le L_2 - L_1, \\ L_3 - \left(L_2 + \frac{R-(L_2-L_1)}{2}\right), & L_2 - L_1 \lt R \le L_2 - L_1 + 2(L_3-L_2), \\ 0, & R > L_2 - L_1 + 2(L_3-L_2). \end{cases}$$
La idea es simple. Primero se eleva el factor más pequeño hasta alcanzar al intermedio. Si todavía sobra masa, se elevan juntos los dos más pequeños hacia el mayor. Si ni siquiera esa relajación continua puede mejorar el mejor rango conocido, toda la rama se poda.
La cota es válida porque el problema real es más rígido que esa relajación continua: los exponentes son discretos y están ligados a primos concretos, así que el rango realmente alcanzable solo puede ser mayor.
La fase A ya produce una razón excelente \(R^\ast = c^\ast / a^\ast\). La segunda fase convierte esa razón en una ventana de búsqueda para el factor mínimo \(a\).
De \(a \le b \le c\) y \(abc=n\) se deduce siempre que
$$a \le n^{1/3}.$$
Ahora, si una terna candidata es al menos tan buena como la mejor actual, entonces \(c/a \le R^\ast\). Como \(b \le c\), se tiene
$$n = abc \le a c^2 \le a(R^\ast a)^2 = (R^\ast)^2 a^3,$$
y por tanto
$$a \ge \left(\frac{n}{(R^\ast)^2}\right)^{1/3}.$$
Así, la fase B solo necesita revisar divisores \(a\) dentro de la ventana estrecha
$$\left(\frac{n}{(R^\ast)^2}\right)^{1/3} \le a \le n^{1/3}.$$
La implementación genera exactamente esos divisores a partir de los exponentes primos y vuelve a podar usando cotas logarítmicas.
Una vez fijado \(a\), definimos
$$q = \frac{n}{a} = bc.$$
Con \(a\) fijo, minimizar \(c/a\) equivale a minimizar \(c\), y como \(bc=q\), eso equivale a maximizar \(b\). La condición de orden \(b \le c\) se convierte en
$$b \le \sqrt{q}.$$
Por ello, el mejor factor acompañante es simplemente el mayor divisor de \(q\) que no supera \(\sqrt{q}\). Después queda forzado
$$c = \frac{q}{b}.$$
La factorización residual de \(q\) ya es conocida a partir de los exponentes elegidos para \(a\), de modo que la implementación recorre directamente ese espacio de divisores. Además, usa una cota superior obtenida de las potencias primas restantes para podar ramas que ya no pueden mejorar el mejor valor actual de \(b\).
Los logaritmos solo se usan para podar. La comparación final entre ternas candidatas es exacta. Para comparar \((a,b,c)\) con la mejor terna conocida \((a^\ast,b^\ast,c^\ast)\), basta con comparar
$$c a^\ast \quad \text{y} \quad c^\ast a.$$
Si ambas razones son iguales, se desempata con el menor valor de \(a+b+c\).
Un control sencillo es \(n=165=3\cdot 5 \cdot 11\). La única terna ordenada es \((3,5,11)\), así que la suma óptima es \(19\). Las implementaciones se verifican con controles pequeños de este tipo antes de evaluar \(43!\).
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Primero calculan los exponentes primos de \(43!\) y precalculan las potencias primas necesarias. Luego generan, para cada valor de exponente, todos los repartos en tres partes y los ordenan para que las opciones equilibradas se exploren primero. Una construcción voraz proporciona la primera terna admisible.
Después, la fase A ejecuta una búsqueda en profundidad con branch-and-bound en el espacio logarítmico, manteniendo siempre ordenados los tres factores parciales. La fase B enumera solo los divisores admisibles del factor más pequeño, reconstruye la factorización residual y busca el mayor divisor acompañante permitido por la cota de la raíz cuadrada. La selección final se hace con aritmética entera exacta, de modo que los logaritmos influyen en la poda, pero no en la corrección.
Si \(n = \prod p^{e_p}\), la fase A examinaría de forma ingenua
$$\prod_p \binom{e_p+2}{2}$$
ramas, lo cual es exponencial respecto a la estructura de exponentes primos. La fase B también es combinatoria: en el peor caso puede revisar muchos divisores dentro de la ventana válida para \(a\), y para cada uno realiza una búsqueda recursiva del mejor divisor residual \(b\).
Por tanto, no existe una cota polinómica simple en función de \(\log n\). El método resulta práctico aquí porque cuatro ideas recortan gran parte del espacio: una buena semilla voraz, el orden equilibrado de los repartos, la cota inferior continua para el rango logarítmico alcanzable y la poda adicional dentro de la búsqueda de divisores residuales. El uso de memoria sigue siendo moderado y está dominado por las potencias primas almacenadas, las tablas de repartos y el estado de la recursión.
对 \(n = 43!\)，我们要找满足
$$a \le b \le c,\qquad abc = n$$
的有序三元组 \((a,b,c)\)。首要目标是让三个因子尽量平衡，也就是最小化比值 \(c/a\)。如果有多个三元组达到同样的最优比值，就再比较 \(a+b+c\)，取和最小的那个。
实现并不是直接枚举全部因子三元组，而是先利用 \(43!\) 的素因子指数结构，优先搜索更平衡的指数分配，再用一次精确的约数搜索把答案收紧。
对每个素数 \(p \le 43\)，\(43!\) 中 \(p\) 的指数由 Legendre 公式给出：
$$e_p = \sum_{k \ge 1} \left\lfloor \frac{43}{p^k} \right\rfloor.$$
因此
$$43! = 2^{39} 3^{19} 5^9 7^6 11^3 13^3 17^2 19^2 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43.$$
任意一个合法三元组都等价于：对每个素数 \(p\) 选择非负整数 \(\alpha_p,\beta_p,\gamma_p\)，满足
$$\alpha_p + \beta_p + \gamma_p = e_p,$$
然后构造
$$a = \prod_{p \le 43} p^{\alpha_p},\qquad b = \prod_{p \le 43} p^{\beta_p},\qquad c = \prod_{p \le 43} p^{\gamma_p}.$$
由于对数函数严格单调，最小化 \(c/a\) 等价于最小化
$$\Delta = \log c - \log a.$$
这样一来，原本乘法意义下的“平衡”就变成了加法意义下的“跨度”。如果当前三个因子的对数排序后为
$$L_1 \le L_2 \le L_3,$$
那么当前状态的优劣恰好由对数范围 \(L_3-L_1\) 决定。
在正式深搜之前，实现会先构造一个合法三元组作为起点。做法是把较大的素数幂拷贝从大到小处理，每次都放进当前对数和最小的那个桶中。这种贪心法不保证最优，但通常能很快给出一个相当平衡的候选解。
这个初始三元组提供了 \(\Delta\) 的第一个上界。有了上界以后，后续分支只要确定不可能更优，就可以立刻剪掉。
对单个素数幂 \(p^e\) 而言，把指数分给三个因子的方案数是
$$\binom{e+2}{2},$$
因为这正是方程 \(x+y+z=e\) 的非负整数解个数。若对所有素数直接做笛卡尔积，规模会极其庞大，所以实现采用 branch-and-bound。
对固定的 \(e\)，所有分配 \((x,y,z)\) 会先按“越平衡越优先”的规则排序。第一关键字是
$$\max(x,y,z) - \min(x,y,z),$$
第二关键字是与 \(e/3\) 的接近程度：
$$|3x-e| + |3y-e| + |3z-e|.$$
每处理完一个素数后，三个部分因子都会按大小重新排序。因为最终只关心排序后的 \((a,b,c)\)，这种重排可以去掉对称重复，并让后面的剪枝公式保持简单。
设当前排序后的对数为 \(L_1 \le L_2 \le L_3\)，尚未分配的素数幂总共还贡献对数质量 \(R\)。哪怕把这部分质量当作可以连续分配，最小可能终态范围也只能通过“先补最小桶”得到。于是有乐观下界
$$\operatorname{LB}(L_1,L_2,L_3,R) = \begin{cases} L_3 - (L_1 + R), & R \le L_2 - L_1, \\ L_3 - \left(L_2 + \frac{R-(L_2-L_1)}{2}\right), & L_2 - L_1 \lt R \le L_2 - L_1 + 2(L_3-L_2), \\ 0, & R > L_2 - L_1 + 2(L_3-L_2). \end{cases}$$
含义很直观。先把最小的那个补到中间那个；如果还有剩余，就让两个较小的桶一起向最大的桶靠近。若连这种连续放松后的下界都无法优于当前最优范围，那么整棵分支树都可以剪掉。
这个下界是安全的，因为真实问题比连续放松更严格：指数必须是离散的，而且绑定在特定素数上，所以真正能达到的范围只会更大，不会更小。
阶段 A 已经得到一个很好的比值 \(R^\ast = c^\ast / a^\ast\)。第二阶段把这个比值转化为最小因子 \(a\) 的搜索窗口。
由 \(a \le b \le c\) 和 \(abc=n\) 总能推出
$$a \le n^{1/3}.$$
如果某个候选三元组至少和当前最优一样好，即 \(c/a \le R^\ast\)，又因为 \(b \le c\)，所以
$$n = abc \le a c^2 \le a(R^\ast a)^2 = (R^\ast)^2 a^3,$$
从而得到
$$a \ge \left(\frac{n}{(R^\ast)^2}\right)^{1/3}.$$
因此阶段 B 只需要考察位于狭窄区间
$$\left(\frac{n}{(R^\ast)^2}\right)^{1/3} \le a \le n^{1/3}$$
中的约数。实现会直接从素因子指数生成这些 \(a\)，并继续使用对数上下界进行剪枝。
一旦 \(a\) 固定，设
$$q = \frac{n}{a} = bc.$$
对于固定的 \(a\)，最小化 \(c/a\) 就等价于最小化 \(c\)，而在 \(bc=q\) 的条件下，这又等价于最大化 \(b\)。排序条件 \(b \le c\) 等价于
$$b \le \sqrt{q}.$$
因此最优伴随因子就是 \(q\) 的所有约数中不超过 \(\sqrt{q}\) 的最大者。找到它以后，第三个因子就唯一确定：
$$c = \frac{q}{b}.$$
由于 \(q\) 的剩余素因子指数已经由 \(a\) 的选择决定，实现可以直接在这个剩余约数空间里搜索。同时，它还用“剩余素数幂最多能把当前值放大多少”的上界继续剪枝，排除不可能改进当前最优 \(b\) 的分支。
对数只用于剪枝，不用于最终判定。要把候选三元组 \((a,b,c)\) 和当前最优 \((a^\ast,b^\ast,c^\ast)\) 作比较，只需比较
$$c a^\ast \quad \text{和} \quad c^\ast a.$$
如果比值完全相同，再比较较小的 \(a+b+c\)。
一个简单的检查例子是 \(n=165=3\cdot 5 \cdot 11\)。这时唯一的有序三元组是 \((3,5,11)\)，因此最优和为 \(19\)。实现会先通过这类小检查，再去处理 \(43!\)。
C++、Python 和 Java 三个实现的整体流程一致。首先计算 \(43!\) 的素因子指数，并预先保存所需的素数幂。然后针对每个指数值生成全部三路拆分，并按“更平衡优先”的顺序排序。接着用贪心法构造第一个可行三元组。
之后，阶段 A 在对数空间中执行深度优先的 branch-and-bound 搜索，并始终保持三个部分因子有序。阶段 B 只枚举最小因子的可行约数，恢复剩余因子分解，再寻找平方根阈值以下最大的合法伴随约数。最终答案的选择完全依赖精确整数运算，因此浮点对数只影响剪枝效率，不影响正确性。
若 \(n = \prod p^{e_p}\)，阶段 A 朴素情况下需要考察
$$\prod_p \binom{e_p+2}{2}$$
个分支，这对素因子指数结构来说是指数级的。阶段 B 同样是组合型搜索：最坏情况下，它可能要检查窗口内相当多的约数 \(a\)，并对每个 \(a\) 再做一次剩余约数 \(b\) 的递归搜索。
因此这里不存在关于 \(\log n\) 的简单多项式最坏界。之所以对 \(43!\) 仍然可行，是因为四种削减手段非常有效：好的贪心初值、平衡优先的拆分顺序、连续放松得到的对数范围下界，以及剩余约数搜索中的额外剪枝。内存占用不大，主要来自预计算的素数幂、拆分表和递归状态。
Для \(n = 43!\) нужно найти упорядоченные тройки множителей \((a,b,c)\), удовлетворяющие
$$a \le b \le c,\qquad abc = n.$$
Главная цель состоит в том, чтобы сделать тройку как можно более сбалансированной, то есть минимизировать отношение \(c/a\). Если несколько троек дают один и тот же оптимальный результат, выбирается та, у которой минимальна сумма \(a+b+c\).
Реализации не перебирают все тройки делителей напрямую. Вместо этого они используют разложение \(43!\) на простые множители, сначала ищут наиболее ровные распределения показателей, а затем уточняют лучший результат точным поиском по делителям.
Для каждого простого \(p \le 43\) показатель в \(43!\) задается формулой Лежандра:
$$e_p = \sum_{k \ge 1} \left\lfloor \frac{43}{p^k} \right\rfloor.$$
Следовательно,
$$43! = 2^{39} 3^{19} 5^9 7^6 11^3 13^3 17^2 19^2 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43.$$
Любая допустимая тройка эквивалентна выбору неотрицательных показателей \(\alpha_p,\beta_p,\gamma_p\) для каждого простого \(p\) так, что
$$\alpha_p + \beta_p + \gamma_p = e_p,$$
после чего определяются числа
$$a = \prod_{p \le 43} p^{\alpha_p},\qquad b = \prod_{p \le 43} p^{\beta_p},\qquad c = \prod_{p \le 43} p^{\gamma_p}.$$
Так как логарифм строго возрастает, минимизация \(c/a\) равносильна минимизации величины
$$\Delta = \log c - \log a.$$
Тем самым мультипликативная задача балансировки превращается в аддитивную. Если текущие логарифмы трех частичных множителей после сортировки равны
$$L_1 \le L_2 \le L_3,$$
то качество текущего состояния точно измеряется диапазоном \(L_3-L_1\).
Перед глубоким поиском строится первая допустимая тройка жадным способом. Копии больших простых множителей рассматриваются от больших к меньшим и каждый раз добавляются в ту корзину, у которой накопленный логарифм минимален. Это не гарантирует оптимальности, но обычно быстро дает хорошо сбалансированную тройку.
Полученная тройка задает первую верхнюю границу для \(\Delta\). После этого любая ветвь, которая заведомо не сможет улучшить текущий результат, немедленно отсекается.
Для одной простой степени \(p^e\) число способов разбить показатель между тремя множителями равно
$$\binom{e+2}{2},$$
поскольку это число неотрицательных решений уравнения \(x+y+z=e\). Если брать декартово произведение по всем простым, пространство состояний становится слишком большим, поэтому используется branch-and-bound.
Для фиксированного \(e\) варианты \((x,y,z)\) упорядочиваются так, чтобы более сбалансированные распределения рассматривались раньше. Сначала минимизируется
$$\max(x,y,z) - \min(x,y,z),$$
а затем близость к \(e/3\), измеряемая выражением
$$|3x-e| + |3y-e| + |3z-e|.$$
После обработки каждого простого множителя три частичных числа снова сортируются. Это важно, потому что в конце имеет значение только упорядоченная тройка; такая сортировка убирает симметрические дубликаты и упрощает формулы отсечения.
Пусть текущие отсортированные логарифмы равны \(L_1 \le L_2 \le L_3\), а еще не распределенные простые степени дают суммарную логарифмическую массу \(R\). Даже если разрешить делить эту массу непрерывно, наименьший возможный конечный диапазон получается, если сначала заполнять меньшие корзины. Отсюда следует оптимистичная нижняя граница
$$\operatorname{LB}(L_1,L_2,L_3,R) = \begin{cases} L_3 - (L_1 + R), & R \le L_2 - L_1, \\ L_3 - \left(L_2 + \frac{R-(L_2-L_1)}{2}\right), & L_2 - L_1 \lt R \le L_2 - L_1 + 2(L_3-L_2), \\ 0, & R > L_2 - L_1 + 2(L_3-L_2). \end{cases}$$
Смысл таков. Сначала оставшаяся масса поднимает самый маленький логарифм до среднего. Если после этого масса еще остается, два меньших логарифма поднимаются вместе к наибольшему. Если даже такая непрерывная релаксация не способна улучшить лучший известный диапазон, вся ветвь отсекается.
Эта граница корректна, потому что реальная задача строже непрерывной релаксации: показатели дискретны и привязаны к конкретным простым, значит истинный достижимый диапазон может быть только больше.
Фаза A уже дает очень хорошее отношение \(R^\ast = c^\ast / a^\ast\). Во второй фазе это отношение превращается в окно поиска для наименьшего множителя \(a\).
Из условий \(a \le b \le c\) и \(abc=n\) всегда следует
$$a \le n^{1/3}.$$
Пусть теперь кандидат не хуже текущего лучшего, то есть \(c/a \le R^\ast\). Так как \(b \le c\), имеем
$$n = abc \le a c^2 \le a(R^\ast a)^2 = (R^\ast)^2 a^3,$$
откуда
$$a \ge \left(\frac{n}{(R^\ast)^2}\right)^{1/3}.$$
Значит, во второй фазе достаточно рассматривать только делители \(a\) из узкого интервала
$$\left(\frac{n}{(R^\ast)^2}\right)^{1/3} \le a \le n^{1/3}.$$
Реализация перечисляет именно такие делители, проходя по вариантам показателей для \(a\) и снова используя логарифмические отсечения.
После фиксации \(a\) положим
$$q = \frac{n}{a} = bc.$$
При данном \(a\) минимизация \(c/a\) равносильна минимизации \(c\), а из условия \(bc=q\) это равносильно максимизации \(b\). Ограничение порядка \(b \le c\) дает
$$b \le \sqrt{q}.$$
Следовательно, оптимальный спутник \(b\) - это просто наибольший делитель числа \(q\), не превосходящий \(\sqrt{q}\). После его нахождения
$$c = \frac{q}{b}$$
определяется однозначно. Остаточная факторизация \(q\) уже известна из выбранных показателей для \(a\), поэтому реализация работает прямо в этом пространстве делителей и дополнительно отсекает ветви по верхней оценке на то, насколько оставшиеся простые степени еще могут увеличить текущее значение \(b\).
Логарифмы используются только для отсечения. Финальное сравнение кандидатов выполняется точно. Чтобы сравнить \((a,b,c)\) с лучшей известной тройкой \((a^\ast,b^\ast,c^\ast)\), достаточно сравнить
$$c a^\ast \quad \text{и} \quad c^\ast a.$$
Если отношения совпадают, выбирается меньшая сумма \(a+b+c\).
Простейшая проверка - \(n=165=3\cdot 5 \cdot 11\). Единственная упорядоченная тройка равна \((3,5,11)\), поэтому оптимальная сумма равна \(19\). Реализации проверяются на таких контрольных примерах перед вычислением для \(43!\).
Реализации на C++, Python и Java устроены одинаково. Сначала вычисляются показатели простых в \(43!\) и заранее строятся нужные простые степени. Затем для каждого значения показателя генерируются все трехчастные разбиения, причем более ровные варианты ставятся первыми. Жадная конструкция дает первую допустимую тройку.
Далее фаза A запускает поиск в глубину с branch-and-bound в логарифмическом пространстве, постоянно поддерживая три частичных множителя в отсортированном виде. Фаза B перечисляет только допустимые делители для наименьшего множителя, восстанавливает остаточную факторизацию и ищет наибольший разрешенный делитель-спутник ниже порога \(\sqrt{q}\). Окончательный выбор делается точной целочисленной арифметикой, поэтому вещественные логарифмы влияют только на скорость отсечения, но не на корректность.
Если \(n = \prod p^{e_p}\), то наивная фаза A должна была бы просмотреть
$$\prod_p \binom{e_p+2}{2}$$
ветвей, что экспоненциально по структуре простых показателей. Фаза B тоже носит комбинаторный характер: в худшем случае приходится просматривать много делителей в допустимом окне для \(a\), а для каждого из них выполнять рекурсивный поиск лучшего остаточного делителя \(b\).
Поэтому простой полиномиальной оценки через \(\log n\) здесь нет. На практике метод работает благодаря четырем сильным сокращениям пространства поиска: хорошей жадной начальной оценке, приоритету сбалансированных разбиений, непрерывной нижней границе для достижимого логарифмического диапазона и дополнительному отсечению внутри поиска остаточного делителя. Память требуется умеренная; основную часть составляют заранее сохраненные простые степени, таблицы разбиений и состояние рекурсии.
عندما يكون \(n = 43!\)، نريد إيجاد الثلاثيات المرتبة \((a,b,c)\) التي تحقق
$$a \le b \le c,\qquad abc = n.$$
الهدف الأساسي هو جعل العوامل الثلاثة متوازنة قدر الإمكان، أي تصغير النسبة \(c/a\). وإذا وُجد أكثر من ثلاثي يحقق النسبة المثلى نفسها، نختار الأصغر في القيمة \(a+b+c\).
التنفيذات لا تقوم بتجربة كل ثلاثية عوامل مباشرة. بدلاً من ذلك تبدأ من التحليل الأولي لـ \(43!\)، وتفحص أولاً توزيعات الأسس الأكثر توازناً، ثم تنتقل إلى بحث دقيق في القواسم لتحسين أفضل نتيجة وصلت إليها.
لكل عدد أولي \(p \le 43\)، فإن أس \(p\) داخل \(43!\) يعطى بصيغة ليجاندر:
$$e_p = \sum_{k \ge 1} \left\lfloor \frac{43}{p^k} \right\rfloor.$$
ومن ثم نحصل على
$$43! = 2^{39} 3^{19} 5^9 7^6 11^3 13^3 17^2 19^2 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43.$$
كل ثلاثي مقبول يكافئ اختيار أسس غير سالبة \(\alpha_p,\beta_p,\gamma_p\) لكل أولي \(p\) بحيث
$$\alpha_p + \beta_p + \gamma_p = e_p,$$
ثم نبني
$$a = \prod_{p \le 43} p^{\alpha_p},\qquad b = \prod_{p \le 43} p^{\beta_p},\qquad c = \prod_{p \le 43} p^{\gamma_p}.$$
بما أن اللوغاريتم دالة متزايدة تماماً، فإن تصغير \(c/a\) يكافئ تصغير
$$\Delta = \log c - \log a.$$
وهكذا تتحول مسألة التوازن الضربي إلى مسألة جمعيّة. إذا كانت اللوغاريتمات الحالية للعوامل الثلاثة بعد الترتيب هي
$$L_1 \le L_2 \le L_3,$$
فإن جودة الحالة الحالية تقاس مباشرة بالمدى اللوغاريتمي \(L_3-L_1\).
قبل البحث العميق، يبني التنفيذ ثلاثياً صحيحاً بطريقة جشعة. تُعالَج نسخ العوامل الأولية الكبيرة من الأكبر إلى الأصغر، وفي كل مرة تُضاف النسخة إلى السلة التي تملك أصغر مجموع لوغاريتمي في تلك اللحظة. هذه الطريقة لا تضمن الحل الأمثل، لكنها غالباً تعطي بسرعة ثلاثياً متوازناً بشكل جيد.
هذا الثلاثي الأول يوفر حداً علوياً ابتدائياً لـ \(\Delta\). وبعد وجود هذا الحد، يمكن حذف أي فرع يتبين أنه غير قادر على تحسينه.
بالنسبة لقوة أولية واحدة \(p^e\)، فإن عدد طرق تقسيم الأس إلى ثلاثة عوامل يساوي
$$\binom{e+2}{2},$$
لأننا نعد الحلول الصحيحة غير السالبة للمعادلة \(x+y+z=e\). الضرب المباشر لكل هذه الاحتمالات عبر جميع الأعداد الأولية سيكون ضخماً جداً، لذلك يُنظَّم البحث بطريقة branch-and-bound.
تُرتَّب التقسيمات الممكنة لأس ثابت \(e\) بحيث تُجرَّب التوزيعات المتوازنة أولاً. المعيار الأول هو صغر القيمة
$$\max(x,y,z) - \min(x,y,z),$$
ثم تأتي درجة القرب من \(e/3\)، المقاسة بالكمية
$$|3x-e| + |3y-e| + |3z-e|.$$
بعد توزيع كل أولي، يعاد ترتيب العوامل الجزئية الثلاثة حسب الحجم. هذا مهم لأن ما يهم في النهاية هو الثلاثي المرتب فقط. إعادة الترتيب تزيل التماثلات المتكررة وتجعل صيغ التقليم أبسط.
لنفرض أن اللوغاريتمات المرتبة الحالية هي \(L_1 \le L_2 \le L_3\)، وأن الكتلة اللوغاريتمية الكلية للعوامل الأولية غير الموزعة بعد تساوي \(R\). حتى لو سمحنا بتوزيع هذه الكتلة بشكل مستمر، فإن أصغر مدى نهائي ممكن ينتج من ملء السلال الصغيرة أولاً. والحد السفلي المتفائل الناتج هو
$$\operatorname{LB}(L_1,L_2,L_3,R) = \begin{cases} L_3 - (L_1 + R), & R \le L_2 - L_1, \\ L_3 - \left(L_2 + \frac{R-(L_2-L_1)}{2}\right), & L_2 - L_1 \lt R \le L_2 - L_1 + 2(L_3-L_2), \\ 0, & R > L_2 - L_1 + 2(L_3-L_2). \end{cases}$$
المعنى مباشر. أولاً نرفع الأصغر حتى يصل إلى الوسط. وإذا بقيت كتلة بعد ذلك، نرفع العاملين الأصغر معاً باتجاه الأكبر. فإذا كانت هذه الاسترخاءة المستمرة نفسها لا تستطيع تحسين أفضل مدى معروف، فإن الفرع كله يُقطع.
هذا الحد السفلي صحيح لأن المسألة الحقيقية أكثر تقييداً من النسخة المستمرة: الأسس هنا قيم منفصلة ومرتبطة بأوليات محددة، لذلك فالمدى الحقيقي الممكن لا يمكن أن يكون أصغر من هذا الحد.
المرحلة A تعطي بالفعل نسبة ممتازة \(R^\ast = c^\ast / a^\ast\). في المرحلة الثانية تتحول هذه النسبة إلى نافذة بحث للعامل الأصغر \(a\).
من الشرطين \(a \le b \le c\) و\(abc=n\) نحصل دائماً على
$$a \le n^{1/3}.$$
والآن إذا كان ثلاثي مرشح جيداً على الأقل مثل الحل الحالي، أي \(c/a \le R^\ast\)، وبما أن \(b \le c\)، فإن
$$n = abc \le a c^2 \le a(R^\ast a)^2 = (R^\ast)^2 a^3,$$
ومن ثم
$$a \ge \left(\frac{n}{(R^\ast)^2}\right)^{1/3}.$$
إذن لا حاجة في المرحلة B إلا إلى فحص القواسم \(a\) الواقعة في المجال الضيق
$$\left(\frac{n}{(R^\ast)^2}\right)^{1/3} \le a \le n^{1/3}.$$
التنفيذ يولد هذه القواسم مباشرة من أسس العوامل الأولية، ويستخدم أيضاً حدوداً لوغاريتمية سفلية وعلوية للتقليم.
بعد تثبيت \(a\)، نعرّف
$$q = \frac{n}{a} = bc.$$
بالنسبة لهذا \(a\) الثابت، فإن تصغير \(c/a\) يعادل تصغير \(c\)، ومع \(bc=q\) يصبح هذا مكافئاً لتعظيم \(b\). أما شرط الترتيب \(b \le c\) فيتحول إلى
$$b \le \sqrt{q}.$$
إذن أفضل عامل مرافق هو ببساطة أكبر قاسم لـ \(q\) لا يتجاوز \(\sqrt{q}\). وبعد إيجاده يتحدد العامل الثالث قسرياً:
$$c = \frac{q}{b}.$$
وبما أن التحليل المتبقي لـ \(q\) معروف من اختيار أسس \(a\)، فإن التنفيذ يبحث مباشرة في فضاء هذه القواسم. كما أنه يستخدم حداً علوياً من القوى الأولية المتبقية لقطع الفروع التي يستحيل أن تنتج قيمة أفضل لـ \(b\).
اللوغاريتمات تستخدم فقط للتقليم. أما المقارنة النهائية بين المرشحين فتتم بدقة صحيحة. لمقارنة \((a,b,c)\) مع أفضل ثلاثي معروف \((a^\ast,b^\ast,c^\ast)\)، يكفي مقارنة
$$c a^\ast \quad \text{و} \quad c^\ast a.$$
وإذا تساوت النسبة، يُحسم التعادل باختيار الأصغر في \(a+b+c\).
ومن نقاط الفحص البسيطة الحالة \(n=165=3\cdot 5 \cdot 11\). لا يوجد هنا إلا ثلاثي مرتب واحد هو \((3,5,11)\)، ولذلك تكون أفضل قيمة للمجموع هي \(19\). تُستعمل مثل هذه الحالات الصغيرة للتأكد من صحة المنهج قبل التعامل مع \(43!\).
تنفيذات C++ وPython وJava تتبع البنية نفسها. أولاً تُحسب أسس العوامل الأولية في \(43!\)، ثم تُجهز القوى الأولية المطلوبة مسبقاً. بعد ذلك تُولَّد كل التقسيمات الثلاثية لكل قيمة أس، وتُرتَّب بحيث تُفحص الخيارات الأكثر توازناً أولاً. ثم يوفر البناء الجشع أول ثلاثي مقبول.
بعد ذلك تنفذ المرحلة A بحثاً عمقياً من نوع branch-and-bound في الفضاء اللوغاريتمي مع إبقاء العوامل الجزئية الثلاثة مرتبة دائماً. ثم تأتي المرحلة B فتعدّد فقط القواسم المسموح بها للعامل الأصغر، وتعيد بناء التحليل المتبقي، ثم تبحث عن أكبر قاسم مرافق لا يتجاوز حد الجذر التربيعي. القرار النهائي يعتمد على حساب صحيح دقيق، لذلك لا تؤثر القيم العائمة إلا في التقليم وليس في صحة النتيجة.
إذا كان \(n = \prod p^{e_p}\)، فإن المرحلة A لو نُفذت بصورة ساذجة لاضطرت إلى فحص
$$\prod_p \binom{e_p+2}{2}$$
فرعاً، وهو نمو أسي بالنسبة إلى بنية الأسس الأولية. والمرحلة B أيضاً ذات طبيعة توافقية: ففي أسوأ الأحوال قد تفحص عدداً كبيراً من القواسم داخل المجال المسموح به لـ \(a\)، ولكل واحد منها تنفذ بحثاً عودياً عن أفضل قاسم متبقٍ \(b\).
لذلك لا يوجد هنا حد كثير حدود بسيط بدلالة \(\log n\). ما يجعل الطريقة عملية في هذه المسألة هو أربع وسائل قوية لتقليص البحث: بذرة جشعة جيدة، وترتيب يفضل التقسيمات المتوازنة، وحد سفلي مستمر للمدى اللوغاريتمي الممكن، وتقليـم إضافي داخل بحث القواسم المتبقية. استهلاك الذاكرة يبقى معتدلاً، ويتركز أساساً في القوى الأولية المخزنة مسبقاً وجداول التقسيمات وحالة العودية.