Write
$$n=\prod_{i=1}^k p_i^{e_i}.$$
Every divisor of \(n\) is obtained by choosing exponents \(0\le a_i\le e_i\). The problem asks for the smallest positive integer \(n\) whose divisor structure has width at least \(10000\), where width means the size of the largest antichain in the divisibility order. The implementations never enumerate all divisors of large candidates directly; they work only with the exponent pattern of the prime factorization.
Let \(W(n)\) denote the width of the divisor poset of \(n\). The central observation is that \(W(n)\) depends only on the multiset of exponents \(\{e_1,\dots,e_k\}\), so the search can be carried out on exponent sequences instead of on raw integers.
Each divisor has the form
$$d=\prod_{i=1}^k p_i^{a_i},\qquad 0\le a_i\le e_i.$$
For two divisors \(d=\prod p_i^{a_i}\) and \(m=\prod p_i^{b_i}\), divisibility is equivalent to coordinatewise comparison:
$$d\mid m \iff a_i\le b_i\ \text{for all }i.$$
Therefore the divisor poset is isomorphic to
$$[0,e_1]\times[0,e_2]\times\cdots\times[0,e_k],$$
a direct product of chains. This already shows that the actual prime values are irrelevant for the width; only the exponents matter.
Give the exponent vector \((a_1,\dots,a_k)\) the rank
$$r(a_1,\dots,a_k)=a_1+\cdots+a_k.$$
If two distinct vectors have the same rank, then neither can dominate the other coordinatewise, so every rank level is an antichain. A standard Sperner-type fact for products of chains says that a largest antichain is achieved by one of these levels. Hence \(W(n)\) is exactly the largest rank size.
Introduce the rank-generating polynomial
$$P_n(x)=\prod_{i=1}^k (1+x+\cdots+x^{e_i})=\sum_{t=0}^{e_1+\cdots+e_k} c_t x^t.$$
The coefficient \(c_t\) counts divisors whose exponent sum is \(t\). Therefore
$$W(n)=\max_t c_t.$$
After processing exponents \(e_1,\dots,e_j\), let \(c^{(j)}_s\) be the number of ways to reach rank \(s\). Adding the next exponent \(e_{j+1}\) means multiplying by \(1+x+\cdots+x^{e_{j+1}}\), which gives the recurrence
$$c^{(j+1)}_s=\sum_{t=0}^{e_{j+1}} c^{(j)}_{s-t}.$$
So the width can be obtained by repeated coefficient convolution, starting from the one-term polynomial \(1\). When all factors have been processed, the largest entry of the resulting coefficient array is the width.
For a fixed exponent multiset, the width is already determined, so the remaining task is to attach those exponents to primes as cheaply as possible. If \(p<q\) and \(a>b\), then
$$p^a q^b < p^b q^a,$$
because dividing the two sides gives \((p/q)^{a-b}<1\). Thus the smallest integer with exponents \(\{e_1,\dots,e_k\}\) is obtained by sorting them in nonincreasing order and assigning them to consecutive primes:
$$n_{\min}(e_1,\dots,e_k)=2^{e_1}3^{e_2}5^{e_3}\cdots,\qquad e_1\ge e_2\ge\cdots\ge e_k\ge1.$$
This turns the search into a search over nonincreasing exponent sequences.
The implementation explores exponent sequences \(e_1\ge e_2\ge\cdots\) by depth-first search. At each node it knows the current product and the current width obtained from the convolution above.
If the width has already reached \(10000\), the current product is a valid candidate and the branch can stop immediately, because appending more positive exponents would only multiply by extra prime powers and make the number larger.
If the current product is already at least as large as the best candidate found so far, that branch is pruned as well.
A useful initial upper bound comes from choosing sixteen distinct primes, which corresponds to exponent pattern
$$\underbrace{(1,1,\dots,1)}_{16\text{ times}}.$$
Then
$$P_n(x)=(1+x)^{16},$$
so the width is the central binomial coefficient
$$\binom{16}{8}=12870>10000.$$
Therefore the product of the first sixteen primes is a valid starting answer, giving the search a finite ceiling from the beginning.
We have
$$5040=2^4\cdot 3^2\cdot 5\cdot 7,$$
so the exponent multiset is \((4,2,1,1)\). The rank-generating polynomial is
$$P_{5040}(x)=(1+x+x^2+x^3+x^4)(1+x+x^2)(1+x)^2.$$
First multiply the last two factors:
$$ (1+x+x^2)(1+x)^2 = 1+3x+4x^2+3x^3+x^4. $$
Multiplying once more gives coefficient sequence
$$1,\,4,\,8,\,11,\,12,\,11,\,8,\,4,\,1.$$
The largest coefficient is \(12\), so
$$W(5040)=12.$$
Likewise, \(45=3^2\cdot5\) yields \((1+x+x^2)(1+x)=1+2x+2x^2+x^3\), hence \(W(45)=2\). These are the small verification values used by the implementations.
The C++, Python, and Java implementations keep the current exponent sequence together with the current integer it represents. For each recursive state, they rebuild the coefficient array of \(P_n(x)\) by repeated convolution with short all-ones blocks and take the maximum coefficient as the current width.
The search always moves to the next prime and only tries exponents from \(1\) up to the previous exponent, which enforces the nonincreasing pattern proved above. Inside the loop, the next prime power is accumulated multiplicatively, so larger exponents reuse the work already done for smaller ones.
Whenever the target width is reached, the current product is compared with the best answer seen so far. Whenever the product itself has already grown past the best known candidate, the branch is abandoned. The C++ implementation uses 128-bit arithmetic for the running product, while the Python and Java implementations rely on arbitrary-precision integers.
Consider a search state with exponent sequence \(e_1,\dots,e_k\) and total degree
$$E=e_1+\cdots+e_k.$$
Building the coefficient table for that state costs
$$\Theta\!\left(\sum_{j=1}^k (E_{j-1}+1)(e_j+1)\right),\qquad E_{j-1}=e_1+\cdots+e_{j-1},$$
which is \(O(E^2)\) in the worst case, and it uses \(O(E)\) memory for the current coefficient array.
If \(S\) is the set of visited search states, the total running time is
$$O\!\left(\sum_{s\in S} E_s^2\right),$$
where the practical size of \(S\) is controlled almost entirely by pruning. There is no simple closed form for the number of visited states, but the monotone exponent restriction and the explicit initial upper bound make the search small enough in practice.
Schreibe
$$n=\prod_{i=1}^k p_i^{e_i}.$$
Jeder Teiler von \(n\) entsteht durch eine Exponentenwahl \(0\le a_i\le e_i\). Gesucht ist die kleinste positive Zahl \(n\), deren Teilerstruktur Breite mindestens \(10000\) besitzt, wobei die Breite die Größe der größten Antikette in der Teilbarkeitsordnung ist. Die Implementierungen zählen dafür keine Teiler großer Kandidaten direkt aus, sondern arbeiten ausschließlich mit dem Exponentenmuster der Primfaktorzerlegung.
Sei \(W(n)\) die Breite des Teilerposets von \(n\). Die entscheidende Beobachtung lautet: \(W(n)\) hängt nur vom Exponentenmultiset \(\{e_1,\dots,e_k\}\) ab. Deshalb kann man direkt über Exponentenfolgen suchen statt über rohe Ganzzahlen.
Jeder Teiler hat die Form
$$d=\prod_{i=1}^k p_i^{a_i},\qquad 0\le a_i\le e_i.$$
Für zwei Teiler \(d=\prod p_i^{a_i}\) und \(m=\prod p_i^{b_i}\) ist Teilbarkeit äquivalent zu koordinatenweisem Vergleich:
$$d\mid m \iff a_i\le b_i\ \text{für alle }i.$$
Damit ist das Teilerposet isomorph zu
$$[0,e_1]\times[0,e_2]\times\cdots\times[0,e_k],$$
also zu einem direkten Produkt von Ketten. Schon daraus folgt, dass für die Breite die konkreten Primzahlen keine Rolle spielen; entscheidend sind nur die Exponenten.
Gib dem Exponentenvektor \((a_1,\dots,a_k)\) den Rang
$$r(a_1,\dots,a_k)=a_1+\cdots+a_k.$$
Zwei verschiedene Vektoren mit demselben Rang können nicht vergleichbar sein, also ist jede Rangschicht eine Antikette. Ein klassisches Sperner-artiges Resultat für Produkte von Ketten sagt, dass eine größte Antikette tatsächlich in einer solchen Schicht liegt. Daher ist \(W(n)\) genau die Größe der größten Rangschicht.
Führe dazu das rankenerzeugende Polynom ein:
$$P_n(x)=\prod_{i=1}^k (1+x+\cdots+x^{e_i})=\sum_{t=0}^{e_1+\cdots+e_k} c_t x^t.$$
Der Koeffizient \(c_t\) zählt die Teiler, deren Exponentensumme \(t\) ist. Also gilt
$$W(n)=\max_t c_t.$$
Nach Verarbeitung der Exponenten \(e_1,\dots,e_j\) sei \(c^{(j)}_s\) die Anzahl der Möglichkeiten, Rang \(s\) zu erreichen. Fügt man den nächsten Exponenten \(e_{j+1}\) hinzu, multipliziert man mit \(1+x+\cdots+x^{e_{j+1}}\) und erhält die Rekursion
$$c^{(j+1)}_s=\sum_{t=0}^{e_{j+1}} c^{(j)}_{s-t}.$$
Damit entsteht die Breite durch wiederholte Koeffizientenfaltung, beginnend mit dem Eintrag \(1\). Nachdem alle Faktoren verarbeitet sind, ist der größte Wert im Koeffizientenarray die gesuchte Breite.
Ist das Exponentenmultiset fest, dann steht die Breite bereits fest. Es bleibt also nur, diese Exponenten möglichst günstig auf Primzahlen zu verteilen. Sind \(p<q\) und \(a>b\), dann gilt
$$p^a q^b < p^b q^a,$$
denn der Quotient der beiden Seiten ist \((p/q)^{a-b}<1\). Also erhält man die kleinste Zahl mit Exponenten \(\{e_1,\dots,e_k\}\), wenn man sie nichtzunehmend sortiert und den aufsteigenden Primzahlen zuordnet:
$$n_{\min}(e_1,\dots,e_k)=2^{e_1}3^{e_2}5^{e_3}\cdots,\qquad e_1\ge e_2\ge\cdots\ge e_k\ge1.$$
Damit reduziert sich die Suche auf nichtzunehmende Exponentenfolgen.
Die Implementierung durchsucht Exponentenfolgen \(e_1\ge e_2\ge\cdots\) per Tiefensuche. In jedem Knoten kennt sie sowohl das aktuelle Produkt als auch die aktuelle Breite aus der obigen Faltung.
Sobald die Breite mindestens \(10000\) erreicht, ist das aktuelle Produkt ein gültiger Kandidat und der Ast kann sofort enden, denn zusätzliche positive Exponenten würden nur weitere Primzahlpotenzen multiplizieren und die Zahl vergrößern.
Falls das aktuelle Produkt bereits mindestens so groß ist wie der bislang beste Kandidat, wird der Ast ebenfalls abgeschnitten.
Eine nützliche Startschranke erhält man mit sechzehn verschiedenen Primzahlen, also dem Exponentenmuster
$$\underbrace{(1,1,\dots,1)}_{16\text{ mal}}.$$
Dann gilt
$$P_n(x)=(1+x)^{16},$$
und die Breite ist der zentrale Binomialkoeffizient
$$\binom{16}{8}=12870>10000.$$
Das Produkt der ersten sechzehn Primzahlen ist also eine gültige Anfangsantwort und liefert der Suche von Anfang an eine endliche Obergrenze.
Es gilt
$$5040=2^4\cdot 3^2\cdot 5\cdot 7,$$
also ist das Exponentenmultiset \((4,2,1,1)\). Das rankenerzeugende Polynom lautet
$$P_{5040}(x)=(1+x+x^2+x^3+x^4)(1+x+x^2)(1+x)^2.$$
Zuerst multiplizieren wir die letzten beiden Faktoren:
$$ (1+x+x^2)(1+x)^2 = 1+3x+4x^2+3x^3+x^4. $$
Nach der letzten Multiplikation erhält man die Koeffizientenfolge
$$1,\,4,\,8,\,11,\,12,\,11,\,8,\,4,\,1.$$
Der größte Koeffizient ist \(12\), also
$$W(5040)=12.$$
Ebenso liefert \(45=3^2\cdot5\) das Polynom \((1+x+x^2)(1+x)=1+2x+2x^2+x^3\) und damit \(W(45)=2\). Genau diese kleinen Kontrollwerte tauchen in den Implementierungen auf.
Die C++-, Python- und Java-Implementierungen halten die aktuelle Exponentenfolge zusammen mit der aktuell dargestellten Zahl. Für jeden Rekursionszustand bauen sie das Koeffizientenarray von \(P_n(x)\) durch wiederholte Faltung kurzer Einsblöcke neu auf und lesen den größten Koeffizienten als aktuelle Breite ab.
Die Suche geht immer zur nächsten Primzahl weiter und probiert nur Exponenten von \(1\) bis zum vorherigen Exponenten. Damit wird die oben bewiesene monotone Reihenfolge erzwungen. Innerhalb der Schleife wird die nächste Primzahlpotenz schrittweise aufgebaut, sodass größere Exponenten die Arbeit kleinerer Exponenten wiederverwenden.
Sobald die Zielbreite erreicht ist, wird das aktuelle Produkt mit der bisher besten Antwort verglichen. Sobald das Produkt selbst bereits über dem besten bekannten Kandidaten liegt, wird der Ast verworfen. Die C++-Implementierung benutzt für das laufende Produkt 128-Bit-Arithmetik, während Python und Java auf Ganzzahlen mit beliebiger Präzision setzen.
Betrachte einen Suchzustand mit Exponentenfolge \(e_1,\dots,e_k\) und Gesamtgrad
$$E=e_1+\cdots+e_k.$$
Der Aufbau der Koeffiziententabelle für diesen Zustand kostet
$$\Theta\!\left(\sum_{j=1}^k (E_{j-1}+1)(e_j+1)\right),\qquad E_{j-1}=e_1+\cdots+e_{j-1},$$
also im schlechtesten Fall \(O(E^2)\) Zeit und \(O(E)\) Speicher für das aktuelle Koeffizientenarray.
Ist \(S\) die Menge der besuchten Suchzustände, dann beträgt die gesamte Laufzeit
$$O\!\left(\sum_{s\in S} E_s^2\right),$$
wobei die praktische Größe von \(S\) fast vollständig durch das Pruning bestimmt wird. Für die Zahl der besuchten Zustände gibt es keine einfache geschlossene Formel, aber die monotone Exponentenregel und die explizite Anfangsschranke machen den Suchbaum in der Praxis klein genug.
Şunu yazalım:
$$n=\prod_{i=1}^k p_i^{e_i}.$$
\(n\)'nin her böleni, \(0\le a_i\le e_i\) olacak şekilde üslerin seçilmesiyle elde edilir. Problem, bölen yapısının genişliği en az \(10000\) olan en küçük pozitif \(n\)'yi arar; burada genişlik, bölünebilme düzenindeki en büyük antizincirin boyutudur. Gerçek çözümde adayların tüm bölenleri tek tek üretilmez; yalnızca asal çarpanların üs örüntüsü üzerinden çalışılır.
\(n\)'nin bölen posetinin genişliğini \(W(n)\) ile gösterelim. Temel gözlem şudur: \(W(n)\) yalnızca \(\{e_1,\dots,e_k\}\) üs çoklu kümesine bağlıdır. Bu yüzden arama doğrudan tam sayılar üzerinde değil, üs dizileri üzerinde yapılabilir.
Her bölen şu biçimdedir:
$$d=\prod_{i=1}^k p_i^{a_i},\qquad 0\le a_i\le e_i.$$
\(d=\prod p_i^{a_i}\) ve \(m=\prod p_i^{b_i}\) için bölünebilme, koordinat bazında karşılaştırmaya denktir:
$$d\mid m \iff a_i\le b_i\ \text{tüm }i\text{ için}.$$
Dolayısıyla bölen poseti
$$[0,e_1]\times[0,e_2]\times\cdots\times[0,e_k]$$
ile izomorftur; yani doğrudan zincirlerin çarpımıdır. Buradan hemen, genişlik için asal sayıların kendilerinin değil yalnızca üslerin önemli olduğu görülür.
\((a_1,\dots,a_k)\) üs vektörünün rütbesi
$$r(a_1,\dots,a_k)=a_1+\cdots+a_k$$
olsun. Aynı rütbeye sahip iki farklı vektör karşılaştırılabilir olamaz; bu yüzden her rütbe seviyesi bir antizincirdir. Zincir çarpımları için standart bir Sperner tipi sonuç, en büyük antizincirin bu seviyelerden birinde bulunduğunu söyler. O halde \(W(n)\) tam olarak en büyük rütbe seviyesinin boyutudur.
Bunun için rütbe üreten polinomu tanımlayalım:
$$P_n(x)=\prod_{i=1}^k (1+x+\cdots+x^{e_i})=\sum_{t=0}^{e_1+\cdots+e_k} c_t x^t.$$
\(c_t\) katsayısı, üs toplamı \(t\) olan bölen sayısını verir. Dolayısıyla
$$W(n)=\max_t c_t.$$
\(e_1,\dots,e_j\) üsleri işlendikten sonra \(c^{(j)}_s\), rütbe \(s\)'ye ulaşma sayısı olsun. Sıradaki \(e_{j+1}\) üssünü eklemek, \(1+x+\cdots+x^{e_{j+1}}\) ile çarpmak demektir ve şu yinelemeyi verir:
$$c^{(j+1)}_s=\sum_{t=0}^{e_{j+1}} c^{(j)}_{s-t}.$$
Yani genişlik, \(1\) polinomundan başlayıp kısa tüm-birler bloklarıyla art arda katsayı konvolüsyonu yapılarak elde edilir. Tüm çarpanlar işlendikten sonra katsayı dizisinin maksimumu genişliktir.
Üs çoklu kümesi sabitse genişlik de sabittir; geriye yalnızca bu üsleri asallara en ucuz biçimde yerleştirmek kalır. Eğer \(p<q\) ve \(a>b\) ise
$$p^a q^b < p^b q^a,$$
çünkü iki tarafın oranı \((p/q)^{a-b}<1\) olur. Bu nedenle \(\{e_1,\dots,e_k\}\) üslerine sahip en küçük sayı, üsleri azalan sırayla dizip artan asallara yerleştirince elde edilir:
$$n_{\min}(e_1,\dots,e_k)=2^{e_1}3^{e_2}5^{e_3}\cdots,\qquad e_1\ge e_2\ge\cdots\ge e_k\ge1.$$
Böylece arama uzayı, tüm sayılar değil, azalan üs dizileridir.
Uygulama \(e_1\ge e_2\ge\cdots\) biçimindeki üs dizilerini derinlik öncelikli aramayla gezer. Her düğümde hem mevcut çarpım hem de yukarıdaki konvolüsyondan gelen genişlik bilinir.
Genişlik zaten \(10000\)'e ulaştıysa mevcut çarpım geçerli bir adaydır ve dal hemen durabilir; çünkü sonradan pozitif üsler eklemek yalnızca yeni asal kuvvetleri çarpar ve sayıyı büyütür.
Mevcut çarpım, şu ana kadarki en iyi adaydan büyük ya da eşitse dal yine kesilir.
Kullanışlı başlangıç üst sınırı, on altı farklı asal seçerek elde edilir; buna karşılık gelen üs örüntüsü
$$\underbrace{(1,1,\dots,1)}_{16\text{ kez}}$$
şeklindedir. Bu durumda
$$P_n(x)=(1+x)^{16},$$
ve genişlik merkezi binom katsayısı olur:
$$\binom{16}{8}=12870>10000.$$
Dolayısıyla ilk on altı asalın çarpımı geçerli bir başlangıç cevabıdır; böylece arama daha en baştan sonlu bir tavan değerine sahip olur.
Şunu yazabiliriz:
$$5040=2^4\cdot 3^2\cdot 5\cdot 7,$$
yani üs çoklu kümesi \((4,2,1,1)\)'dir. Rütbe üreten polinom
$$P_{5040}(x)=(1+x+x^2+x^3+x^4)(1+x+x^2)(1+x)^2$$
olur. Önce son iki çarpanı çarpalım:
$$ (1+x+x^2)(1+x)^2 = 1+3x+4x^2+3x^3+x^4. $$
Son çarpımın katsayı dizisi
$$1,\,4,\,8,\,11,\,12,\,11,\,8,\,4,\,1$$
olur. En büyük katsayı \(12\) olduğundan
$$W(5040)=12.$$
Aynı biçimde \(45=3^2\cdot5\) için \((1+x+x^2)(1+x)=1+2x+2x^2+x^3\) elde edilir ve \(W(45)=2\) çıkar. Uygulamalardaki küçük doğrulama değerleri bunlardır.
C++, Python ve Java uygulamaları mevcut üs dizisini ve bunun temsil ettiği çarpımı birlikte taşır. Her özyinelemeli durumda \(P_n(x)\)'in katsayı dizisi, kısa tüm-birler bloklarıyla art arda konvolüsyon yapılarak yeniden kurulur ve en büyük katsayı mevcut genişlik olarak alınır.
Arama her zaman bir sonraki asala geçer ve yalnızca \(1\) ile önceki üs arasındaki değerleri dener; böylece yukarıda ispatlanan azalan düzen korunur. Döngü içinde sıradaki asal kuvveti kademeli olarak büyütüldüğü için daha büyük üsler, daha küçük üsler için yapılmış hesabı yeniden kullanır.
Hedef genişliğe ulaşıldığında mevcut çarpım o ana kadarki en iyi cevapla karşılaştırılır. Çarpım zaten bilinen en iyi adayın üzerine çıktıysa dal terk edilir. C++ sürümü ara çarpım için 128 bit aritmetik kullanırken Python ve Java sürümleri doğal olarak keyfi hassasiyetli tam sayılara dayanır.
\(e_1,\dots,e_k\) üs dizisine sahip bir arama durumunda toplam derece
$$E=e_1+\cdots+e_k$$
olsun. Bu durum için katsayı tablosunu kurmanın maliyeti
$$\Theta\!\left(\sum_{j=1}^k (E_{j-1}+1)(e_j+1)\right),\qquad E_{j-1}=e_1+\cdots+e_{j-1},$$
olur; bu da en kötü durumda \(O(E^2)\) zaman ve mevcut katsayı dizisi için \(O(E)\) bellek demektir.
Eğer \(S\) ziyaret edilen arama durumları kümesiyse toplam süre
$$O\!\left(\sum_{s\in S} E_s^2\right)$$
şeklindedir. Pratikte \(S\)'nin büyüklüğünü neredeyse tamamen budama belirler. Ziyaret edilen durum sayısı için basit kapalı form yoktur, fakat azalan üs kuralı ve açık başlangıç üst sınırı arama ağacını yönetilebilir boyutta tutar.
Escribimos
$$n=\prod_{i=1}^k p_i^{e_i}.$$
Cada divisor de \(n\) aparece al elegir exponentes \(0\le a_i\le e_i\). El problema pide el menor entero positivo \(n\) cuya estructura de divisores tenga anchura al menos \(10000\), donde la anchura es el tamaño de la mayor anticadena en el orden de divisibilidad. Las implementaciones no enumeran todos los divisores de candidatos grandes; trabajan solo con el patrón de exponentes de la factorización prima.
Denotemos por \(W(n)\) la anchura del poset de divisores de \(n\). La observación clave es que \(W(n)\) depende únicamente del multiconjunto de exponentes \(\{e_1,\dots,e_k\}\). Por eso la búsqueda puede hacerse sobre secuencias de exponentes en lugar de hacerlo sobre enteros crudos.
Cada divisor tiene la forma
$$d=\prod_{i=1}^k p_i^{a_i},\qquad 0\le a_i\le e_i.$$
Para dos divisores \(d=\prod p_i^{a_i}\) y \(m=\prod p_i^{b_i}\), la divisibilidad equivale a una comparación coordenada a coordenada:
$$d\mid m \iff a_i\le b_i\ \text{para todo }i.$$
Por tanto, el poset de divisores es isomorfo a
$$[0,e_1]\times[0,e_2]\times\cdots\times[0,e_k],$$
un producto directo de cadenas. Esto muestra de inmediato que, para la anchura, los valores concretos de los primos no importan; lo que importa son los exponentes.
Asignemos al vector de exponentes \((a_1,\dots,a_k)\) el rango
$$r(a_1,\dots,a_k)=a_1+\cdots+a_k.$$
Dos vectores distintos con el mismo rango no pueden ser comparables, así que cada nivel de rango es una anticadena. Un hecho clásico de tipo Sperner para productos de cadenas afirma que una anticadena máxima aparece en uno de esos niveles. En consecuencia, \(W(n)\) es exactamente el tamaño del mayor nivel de rango.
Introducimos entonces el polinomio generador por rangos
$$P_n(x)=\prod_{i=1}^k (1+x+\cdots+x^{e_i})=\sum_{t=0}^{e_1+\cdots+e_k} c_t x^t.$$
El coeficiente \(c_t\) cuenta los divisores cuya suma de exponentes es \(t\). Por tanto,
$$W(n)=\max_t c_t.$$
Tras procesar los exponentes \(e_1,\dots,e_j\), sea \(c^{(j)}_s\) el número de maneras de alcanzar el rango \(s\). Añadir el siguiente exponente \(e_{j+1}\) equivale a multiplicar por \(1+x+\cdots+x^{e_{j+1}}\), lo que produce la recurrencia
$$c^{(j+1)}_s=\sum_{t=0}^{e_{j+1}} c^{(j)}_{s-t}.$$
Así, la anchura se obtiene mediante convoluciones sucesivas de coeficientes, empezando desde el polinomio \(1\). Cuando todos los factores han sido incorporados, el mayor valor del arreglo de coeficientes es la anchura.
Si el multiconjunto de exponentes ya está fijado, la anchura también lo está. Solo queda colocar esos exponentes sobre primos del modo más barato posible. Si \(p<q\) y \(a>b\), entonces
$$p^a q^b < p^b q^a,$$
porque el cociente entre ambos lados es \((p/q)^{a-b}<1\). Por ello, el menor entero con exponentes \(\{e_1,\dots,e_k\}\) se obtiene ordenándolos de forma no creciente y asignándolos a los primos consecutivos:
$$n_{\min}(e_1,\dots,e_k)=2^{e_1}3^{e_2}5^{e_3}\cdots,\qquad e_1\ge e_2\ge\cdots\ge e_k\ge1.$$
La búsqueda se reduce así al espacio de las secuencias no crecientes de exponentes.
La implementación explora secuencias \(e_1\ge e_2\ge\cdots\) mediante búsqueda en profundidad. En cada nodo conoce tanto el producto actual como la anchura actual obtenida por la convolución anterior.
Si la anchura ya alcanzó \(10000\), el producto actual es un candidato válido y la rama puede detenerse en ese punto, porque añadir más exponentes positivos solo multiplicaría por potencias primas adicionales y aumentaría el número.
Si el producto actual ya es al menos tan grande como el mejor candidato conocido, la rama se poda inmediatamente.
Una cota superior inicial útil proviene de tomar dieciséis primos distintos, es decir, el patrón de exponentes
$$\underbrace{(1,1,\dots,1)}_{16\text{ veces}}.$$
Entonces
$$P_n(x)=(1+x)^{16},$$
y la anchura es el coeficiente binomial central
$$\binom{16}{8}=12870>10000.$$
Así, el producto de los primeros dieciséis primos ya da una respuesta válida de partida, lo que proporciona un techo finito desde el comienzo.
Tenemos
$$5040=2^4\cdot 3^2\cdot 5\cdot 7,$$
de modo que el multiconjunto de exponentes es \((4,2,1,1)\). El polinomio generador por rangos es
$$P_{5040}(x)=(1+x+x^2+x^3+x^4)(1+x+x^2)(1+x)^2.$$
Primero multiplicamos los dos últimos factores:
$$ (1+x+x^2)(1+x)^2 = 1+3x+4x^2+3x^3+x^4. $$
Al multiplicar una vez más se obtiene la sucesión de coeficientes
$$1,\,4,\,8,\,11,\,12,\,11,\,8,\,4,\,1.$$
El coeficiente máximo es \(12\), por lo tanto
$$W(5040)=12.$$
Del mismo modo, \(45=3^2\cdot5\) produce \((1+x+x^2)(1+x)=1+2x+2x^2+x^3\), y por eso \(W(45)=2\). Esos son los pequeños valores de comprobación usados por las implementaciones.
Las implementaciones en C++, Python y Java mantienen la secuencia actual de exponentes junto con el entero actual que esa secuencia representa. En cada estado recursivo reconstruyen el arreglo de coeficientes de \(P_n(x)\) mediante convoluciones repetidas con bloques cortos llenos de unos, y toman el coeficiente máximo como anchura actual.
La búsqueda siempre avanza al siguiente primo y solo prueba exponentes entre \(1\) y el exponente anterior, con lo que se impone la pauta no creciente demostrada antes. Dentro del bucle, la potencia del primo siguiente se acumula multiplicativamente, de modo que los exponentes mayores reutilizan el trabajo ya hecho para los menores.
Cuando se alcanza la anchura objetivo, el producto actual se compara con la mejor respuesta conocida. Cuando el producto ya supera ese mejor candidato, la rama se abandona. La implementación en C++ usa aritmética de 128 bits para el producto acumulado, mientras que las de Python y Java usan enteros de precisión arbitraria.
Consideremos un estado de búsqueda con secuencia de exponentes \(e_1,\dots,e_k\) y grado total
$$E=e_1+\cdots+e_k.$$
Construir la tabla de coeficientes para ese estado cuesta
$$\Theta\!\left(\sum_{j=1}^k (E_{j-1}+1)(e_j+1)\right),\qquad E_{j-1}=e_1+\cdots+e_{j-1},$$
lo cual es \(O(E^2)\) en el peor caso, y utiliza \(O(E)\) memoria para el arreglo actual de coeficientes.
Si \(S\) es el conjunto de estados visitados, el tiempo total es
$$O\!\left(\sum_{s\in S} E_s^2\right),$$
donde el tamaño práctico de \(S\) está gobernado casi por completo por la poda. No hay una fórmula cerrada sencilla para el número de estados visitados, pero la restricción de exponentes no crecientes y la cota superior inicial hacen que el árbol sea manejable en la práctica.
设
$$n=\prod_{i=1}^k p_i^{e_i}.$$
\(n\) 的每个约数都对应于一组指数选择 \(0\le a_i\le e_i\)。本题要求找到最小的正整数 \(n\)，使它的约数结构的宽度至少为 \(10000\)。这里的“宽度”指的是在整除关系下最大反链的大小。实现并不会对大候选值的所有约数做显式枚举，而是直接围绕质因数分解中的指数模式展开。
记 \(W(n)\) 为 \(n\) 的约数偏序集宽度。最关键的观察是：\(W(n)\) 只由指数多重集 \(\{e_1,\dots,e_k\}\) 决定，与具体是哪几个质数无关。因此，真正要搜索的对象不是整数本身，而是按大小约束的指数序列。
任意约数都可以写成
$$d=\prod_{i=1}^k p_i^{a_i},\qquad 0\le a_i\le e_i.$$
若另一个约数为 \(m=\prod p_i^{b_i}\)，那么整除关系等价于逐坐标比较：
$$d\mid m \iff a_i\le b_i\ \text{对所有 }i\text{ 都成立}.$$
所以，\(n\) 的约数偏序集与
$$[0,e_1]\times[0,e_2]\times\cdots\times[0,e_k]$$
同构，也就是若干有限链的直积。这个表示立刻说明：宽度只取决于指数，而不取决于这些指数挂在哪些质数上。
给指数向量 \((a_1,\dots,a_k)\) 赋予秩
$$r(a_1,\dots,a_k)=a_1+\cdots+a_k.$$
如果两个不同的指数向量具有相同的秩，那么它们不可能在逐坐标意义下互相比较，因此每个秩层本身就是一个反链。对链的直积，经典的 Sperner 型结论告诉我们：最大反链恰好可以在某一个秩层中取得。于是 \(W(n)\) 就等于最大秩层的大小。
把这一点写成多项式，就是秩生成函数
$$P_n(x)=\prod_{i=1}^k (1+x+\cdots+x^{e_i})=\sum_{t=0}^{e_1+\cdots+e_k} c_t x^t.$$
其中系数 \(c_t\) 表示指数和等于 \(t\) 的约数个数。因此
$$W(n)=\max_t c_t.$$
这一步就是整个解法的核心：题目的“宽度”被转成了一个系数最大值问题。
设在处理完 \(e_1,\dots,e_j\) 之后，\(c^{(j)}_s\) 表示达到秩 \(s\) 的方案数。再加入下一个指数 \(e_{j+1}\) 时，相当于把当前多项式乘上 \(1+x+\cdots+x^{e_{j+1}}\)，于是得到递推
$$c^{(j+1)}_s=\sum_{t=0}^{e_{j+1}} c^{(j)}_{s-t}.$$
从初始多项式 \(1\) 开始，依次把每个因子乘进去，就能得到完整的系数表。所有因子处理结束后，系数表中的最大值就是 \(W(n)\)。
换句话说，程序在做的事情并不是直接列出所有约数，而是用一个“系数动态规划”来统计每个秩层的大小。
一旦指数多重集固定，宽度就已经固定了。剩下的问题只是：这些指数应该如何分配给质数，才能使整数本身尽量小？
如果 \(p<q\) 且 \(a>b\)，那么
$$p^a q^b < p^b q^a,$$
因为两边之比是 \((p/q)^{a-b}<1\)。所以，大指数必须放在小质数上才最优。
因此，对于同一个指数多重集，最小的整数一定具有形式
$$n_{\min}(e_1,\dots,e_k)=2^{e_1}3^{e_2}5^{e_3}\cdots,\qquad e_1\ge e_2\ge\cdots\ge e_k\ge1.$$
这就把原问题转成了对非增指数序列的搜索，而不再需要在所有整数里盲目试探。
实现会按 \(e_1\ge e_2\ge\cdots\) 的约束做深度优先搜索。每到一个节点，它都知道当前指数序列对应的乘积，以及通过上面的卷积计算得到的当前宽度。
如果当前宽度已经达到 \(10000\)，那么当前乘积就是一个合法候选值，这个分支可以立刻停止。原因很简单：再附加新的正指数，只会再乘上一些新的质数幂，从而让数值更大，不可能得到更优答案。
如果当前乘积已经不小于目前最好的候选值，这个分支也可以直接剪掉，因为继续向下不会变得更小。
实现还使用了一个非常重要的初始上界。若取十六个互不相同的质数，也就是指数模式
$$\underbrace{(1,1,\dots,1)}_{16\text{ 个}},$$
那么对应的多项式就是
$$P_n(x)=(1+x)^{16}.$$
它的最大系数是中心二项式系数
$$\binom{16}{8}=12870>10000.$$
因此，前十六个质数的乘积已经给出了一个确定可行的答案上界，后续搜索只需要在这个上界之下寻找更小的候选值。
有
$$5040=2^4\cdot 3^2\cdot 5\cdot 7,$$
所以指数多重集是 \((4,2,1,1)\)。对应的秩生成函数为
$$P_{5040}(x)=(1+x+x^2+x^3+x^4)(1+x+x^2)(1+x)^2.$$
先把后两个因子相乘：
$$ (1+x+x^2)(1+x)^2 = 1+3x+4x^2+3x^3+x^4. $$
再乘上 \(1+x+x^2+x^3+x^4\) 后，系数序列为
$$1,\,4,\,8,\,11,\,12,\,11,\,8,\,4,\,1.$$
最大系数是 \(12\)，因此
$$W(5040)=12.$$
同理，\(45=3^2\cdot5\) 时有 \((1+x+x^2)(1+x)=1+2x+2x^2+x^3\)，于是 \(W(45)=2\)。这些正是实现里用来做小范围核对的数值。
C++、Python 和 Java 实现都维护两样东西：当前的指数序列，以及这组指数所代表的当前整数。对每一个递归状态，它们都会通过若干个短的全 \(1\) 系数块做卷积，重建 \(P_n(x)\) 的系数数组，然后把其中最大项作为当前宽度。
搜索总是转向下一个质数，并且只尝试从 \(1\) 到前一个指数之间的取值，这样就强制满足上面证明过的非增顺序。在同一个质数上，幂次是通过连续乘法逐步累积的，因此更大的指数会复用更小指数已经完成的工作。
一旦宽度达到目标值，当前乘积就会拿去和已知最优候选比较；如果乘积本身已经不优于当前最优值，该分支就被丢弃。C++ 版本对运行中的乘积使用 128 位整数，Python 和 Java 版本则依赖任意精度整数。
考虑一个搜索状态，它的指数序列为 \(e_1,\dots,e_k\)，总次数为
$$E=e_1+\cdots+e_k.$$
对这个状态重建系数表的代价是
$$\Theta\!\left(\sum_{j=1}^k (E_{j-1}+1)(e_j+1)\right),\qquad E_{j-1}=e_1+\cdots+e_{j-1},$$
最坏情况下可写成 \(O(E^2)\)，空间则是当前系数数组所需的 \(O(E)\)。
如果把所有访问过的搜索状态记为 \(S\)，总时间可以写成
$$O\!\left(\sum_{s\in S} E_s^2\right).$$
这里真正决定运行时间的是剪枝后还剩多少状态。访问状态数没有一个简单的闭式公式，但“指数非增”这一结构约束加上明确的初始上界，使得实际搜索规模足够小。
Пусть
$$n=\prod_{i=1}^k p_i^{e_i}.$$
Каждый делитель числа \(n\) задается выбором показателей \(0\le a_i\le e_i\). Требуется найти наименьшее положительное \(n\), для которого ширина структуры делителей не меньше \(10000\), где ширина понимается как размер наибольшей антицепи в порядке делимости. Реализации не перебирают все делители больших кандидатов напрямую, а работают только с шаблоном показателей в простом разложении.
Обозначим через \(W(n)\) ширину частично упорядоченного множества делителей числа \(n\). Ключевое наблюдение состоит в том, что \(W(n)\) зависит только от мультимножества показателей \(\{e_1,\dots,e_k\}\). Поэтому искать нужно не по самим числам, а по невозрастающим последовательностям показателей.
Каждый делитель имеет вид
$$d=\prod_{i=1}^k p_i^{a_i},\qquad 0\le a_i\le e_i.$$
Если \(d=\prod p_i^{a_i}\) и \(m=\prod p_i^{b_i}\), то делимость эквивалентна покоординатному сравнению:
$$d\mid m \iff a_i\le b_i\ \text{для всех }i.$$
Следовательно, множество делителей с этим порядком изоморфно
$$[0,e_1]\times[0,e_2]\times\cdots\times[0,e_k],$$
то есть прямому произведению конечных цепей. Отсюда сразу видно, что для ширины важны только показатели, а не сами простые числа.
Зададим вектору показателей \((a_1,\dots,a_k)\) ранг
$$r(a_1,\dots,a_k)=a_1+\cdots+a_k.$$
Два разных вектора с одинаковым рангом не могут быть сравнимы, значит каждый слой фиксированного ранга является антицепью. Стандартный результат типа теоремы Спернера для произведений цепей утверждает, что максимальная антицепь достигается на одном из таких слоев. Поэтому \(W(n)\) совпадает с размером самого большого рангового слоя.
Введем ранговый производящий многочлен
$$P_n(x)=\prod_{i=1}^k (1+x+\cdots+x^{e_i})=\sum_{t=0}^{e_1+\cdots+e_k} c_t x^t.$$
Коэффициент \(c_t\) считает делители, у которых сумма показателей равна \(t\). Следовательно,
$$W(n)=\max_t c_t.$$
После обработки показателей \(e_1,\dots,e_j\) пусть \(c^{(j)}_s\) обозначает число способов получить ранг \(s\). Добавление следующего показателя \(e_{j+1}\) соответствует умножению на \(1+x+\cdots+x^{e_{j+1}}\), поэтому возникает рекурсия
$$c^{(j+1)}_s=\sum_{t=0}^{e_{j+1}} c^{(j)}_{s-t}.$$
Итак, ширина получается последовательной сверткой коэффициентов, начиная с многочлена \(1\). После обработки всех множителей максимум в текущем массиве коэффициентов и есть \(W(n)\).
Если мультимножество показателей уже фиксировано, то ширина уже определена. Остается назначить эти показатели простым числам так, чтобы само число было как можно меньше. Если \(p<q\) и \(a>b\), то
$$p^a q^b < p^b q^a,$$
поскольку отношение двух сторон равно \((p/q)^{a-b}<1\). Значит, большие показатели надо ставить на меньшие простые.
Тем самым минимальное число с показателями \(\{e_1,\dots,e_k\}\) имеет вид
$$n_{\min}(e_1,\dots,e_k)=2^{e_1}3^{e_2}5^{e_3}\cdots,\qquad e_1\ge e_2\ge\cdots\ge e_k\ge1.$$
Поиск можно вести по невозрастающим последовательностям показателей.
Реализация перебирает последовательности \(e_1\ge e_2\ge\cdots\) поиском в глубину. В каждой вершине известны текущее произведение и текущая ширина, вычисленная сверткой выше.
Если ширина уже достигла \(10000\), текущее произведение является допустимым кандидатом, и ветку можно завершить, потому что добавление новых положительных показателей лишь домножит число на дополнительные простые степени и сделает его больше.
Если текущее произведение уже не меньше лучшего найденного кандидата, ветка тоже немедленно отсекается.
Очень полезная стартовая верхняя граница получается из шестнадцати различных простых, то есть из шаблона показателей
$$\underbrace{(1,1,\dots,1)}_{16\text{ раз}}.$$
Тогда
$$P_n(x)=(1+x)^{16},$$
и ширина равна центральному биномиальному коэффициенту
$$\binom{16}{8}=12870>10000.$$
Значит, произведение первых шестнадцати простых уже дает корректный начальный ответ и ограничивает поиск сверху с самого начала.
Имеем
$$5040=2^4\cdot 3^2\cdot 5\cdot 7,$$
поэтому мультимножество показателей равно \((4,2,1,1)\). Ранговый многочлен имеет вид
$$P_{5040}(x)=(1+x+x^2+x^3+x^4)(1+x+x^2)(1+x)^2.$$
Сначала перемножим два последних множителя:
$$ (1+x+x^2)(1+x)^2 = 1+3x+4x^2+3x^3+x^4. $$
После умножения на первый множитель получаем последовательность коэффициентов
$$1,\,4,\,8,\,11,\,12,\,11,\,8,\,4,\,1.$$
Максимальный коэффициент равен \(12\), значит
$$W(5040)=12.$$
Аналогично, для \(45=3^2\cdot5\) получается \((1+x+x^2)(1+x)=1+2x+2x^2+x^3\), и потому \(W(45)=2\). Именно эти небольшие контрольные значения используются в реализациях.
Реализации на C++, Python и Java хранят текущую последовательность показателей вместе с текущим числом, которое она задает. Для каждого рекурсивного состояния они заново строят массив коэффициентов \(P_n(x)\) с помощью последовательных сверток коротких блоков из единиц и берут максимальный коэффициент как текущую ширину.
Поиск всегда переходит к следующему простому числу и пробует только показатели от \(1\) до предыдущего показателя, тем самым принудительно сохраняя доказанный выше невозрастающий порядок. Внутри цикла очередная простая степень накапливается умножением, поэтому большие показатели переиспользуют уже выполненную работу для меньших.
Когда достигнута целевая ширина, текущее произведение сравнивается с лучшим найденным ответом. Когда само произведение уже не лучше текущего лучшего кандидата, ветка отбрасывается. В версии на C++ для промежуточного произведения используется 128-битная арифметика, а версии на Python и Java опираются на целые числа произвольной точности.
Рассмотрим состояние поиска с последовательностью показателей \(e_1,\dots,e_k\) и суммарной степенью
$$E=e_1+\cdots+e_k.$$
Построение таблицы коэффициентов для такого состояния стоит
$$\Theta\!\left(\sum_{j=1}^k (E_{j-1}+1)(e_j+1)\right),\qquad E_{j-1}=e_1+\cdots+e_{j-1},$$
что в худшем случае дает \(O(E^2)\) по времени и \(O(E)\) по памяти для текущего массива коэффициентов.
Если \(S\) — множество посещенных состояний, суммарное время равно
$$O\!\left(\sum_{s\in S} E_s^2\right),$$
где практический размер \(S\) почти полностью определяется отсечениями. Простого замкнутого выражения для числа посещенных состояний нет, но ограничение на невозрастающие показатели и явная начальная верхняя граница делают дерево поиска достаточно маленьким на практике.
لنكتب
$$n=\prod_{i=1}^k p_i^{e_i}.$$
كل قاسم لـ \(n\) ينتج من اختيار أسس \(0\le a_i\le e_i\). المطلوب هو إيجاد أصغر عدد صحيح موجب \(n\) تكون بنية قواسمه ذات عرض لا يقل عن \(10000\)، والمقصود بالعرض هنا هو حجم أكبر مجموعة من القواسم تكون عناصرها غير قابلة للمقارنة تحت علاقة القسمة. لا تقوم التطبيقات بتعداد جميع القواسم للأعداد الكبيرة مباشرة، بل تعمل فقط على نمط الأسس في التحليل إلى عوامل أولية.
لنرمز إلى عرض ترتيب القواسم للعدد \(n\) بالرمز \(W(n)\). الفكرة الأساسية هي أن \(W(n)\) يعتمد فقط على متعدد الأسس \(\{e_1,\dots,e_k\}\)، لا على القيم الفعلية للأعداد الأولية. لذلك يمكن تنفيذ البحث على متتاليات الأسس نفسها بدلًا من البحث على الأعداد مباشرة.
كل قاسم يكتب على الصورة
$$d=\prod_{i=1}^k p_i^{a_i},\qquad 0\le a_i\le e_i.$$
إذا كان \(d=\prod p_i^{a_i}\) و\(m=\prod p_i^{b_i}\)، فإن علاقة القسمة تكافئ المقارنة عنصرًا بعنصر:
$$d\mid m \iff a_i\le b_i\ \text{for all }i.$$
إذن فإن ترتيب القواسم مماثل لـ
$$[0,e_1]\times[0,e_2]\times\cdots\times[0,e_k],$$
أي حاصل ضرب مباشر لسلاسل منتهية. وهذا يوضح مباشرة أن العرض لا يعتمد على الأعداد الأولية نفسها، بل على الأسس فقط.
نعطي متجه الأسس \((a_1,\dots,a_k)\) الرتبة
$$r(a_1,\dots,a_k)=a_1+\cdots+a_k.$$
إذا كان متجهان مختلفان يملكان الرتبة نفسها، فلا يمكن أن يكون أحدهما أصغر من الآخر عنصرًا بعنصر، ولذلك فكل طبقة رتبية تمثل مجموعة لا تقارن عناصرها. وتخبرنا نتيجة من نوع مبرهنة سبيرنر لجداءات السلاسل بأن أكبر مجموعة من هذا النوع تتحقق في إحدى هذه الطبقات. ومن ثم فإن \(W(n)\) يساوي حجم أكبر طبقة رتبية.
نعرّف كثير الحدود المولد للرتب كما يلي:
$$P_n(x)=\prod_{i=1}^k (1+x+\cdots+x^{e_i})=\sum_{t=0}^{e_1+\cdots+e_k} c_t x^t.$$
المعامل \(c_t\) يعد القواسم التي يكون مجموع أسسها مساويًا لـ \(t\). لذا نحصل على
$$W(n)=\max_t c_t.$$
بعد معالجة الأسس \(e_1,\dots,e_j\)، ليكن \(c^{(j)}_s\) عدد الطرق التي تعطي الرتبة \(s\). وعند إضافة الأس \(e_{j+1}\) التالي، فهذا يكافئ الضرب في \(1+x+\cdots+x^{e_{j+1}}\)، فنحصل على العلاقة
$$c^{(j+1)}_s=\sum_{t=0}^{e_{j+1}} c^{(j)}_{s-t}.$$
أي أن العرض يحسب عبر التفاف متكرر للمعاملات ابتداءً من كثير الحدود \(1\). وبعد إدخال جميع العوامل، تكون أكبر قيمة في مصفوفة المعاملات هي العرض المطلوب.
عندما تثبت مجموعة الأسس، يصبح العرض ثابتًا أيضًا. ويتبقى فقط توزيع هذه الأسس على الأعداد الأولية بأقل كلفة ممكنة. إذا كان \(p<q\) و\(a>b\)، فإن
$$p^a q^b < p^b q^a,$$
لأن نسبة الطرفين تساوي \((p/q)^{a-b}<1\). لذا يجب وضع الأسس الأكبر على الأعداد الأولية الأصغر.
وعليه فإن أصغر عدد يحمل مجموعة الأسس \(\{e_1,\dots,e_k\}\) هو
$$n_{\min}(e_1,\dots,e_k)=2^{e_1}3^{e_2}5^{e_3}\cdots,\qquad e_1\ge e_2\ge\cdots\ge e_k\ge1.$$
وبذلك تتحول المسألة إلى بحث في متتاليات أسس غير متزايدة.
تستكشف الخوارزمية متتاليات الأسس \(e_1\ge e_2\ge\cdots\) باستخدام بحث عمقي. وفي كل عقدة تكون قيمة الحاصل الحالي معروفة، كما تكون قيمة العرض الحالية معروفة من خلال الالتفاف السابق.
إذا بلغ العرض بالفعل \(10000\)، فإن الحاصل الحالي يمثل مرشحًا صالحًا ويمكن إنهاء هذا الفرع فورًا، لأن إضافة أسس موجبة جديدة لن تفعل إلا ضرب العدد في قوى أولية إضافية، وبالتالي تكبيره.
وإذا كان الحاصل الحالي أكبر من أو مساويًا لأفضل مرشح معروف، فإن هذا الفرع يقطع أيضًا مباشرة.
هناك حد أعلى ابتدائي مهم جدًا يأتي من اختيار ستة عشر عددًا أوليًا مختلفًا، أي من نمط الأسس التالي الذي يحتوي على ستة عشر قيمة كلها تساوي \(1\):
$$\underbrace{(1,1,\dots,1)}_{16}.$$
عندئذ يصبح
$$P_n(x)=(1+x)^{16},$$
ويكون العرض هو المعامل الثنائي المركزي
$$\binom{16}{8}=12870>10000.$$
إذن فإن حاصل ضرب أول ستة عشر عددًا أوليًا يعطي جوابًا ابتدائيًا صالحًا، ويوفر سقفًا عدديًا واضحًا يبدأ منه القطع.
لدينا
$$5040=2^4\cdot 3^2\cdot 5\cdot 7,$$
ولذلك يكون متعدد الأسس هو \((4,2,1,1)\). كثير الحدود المولد للرتب هو
$$P_{5040}(x)=(1+x+x^2+x^3+x^4)(1+x+x^2)(1+x)^2.$$
نضرب أولًا العاملين الأخيرين:
$$ (1+x+x^2)(1+x)^2 = 1+3x+4x^2+3x^3+x^4. $$
وبعد الضرب في العامل الأول نحصل على متتالية المعاملات
$$1,\,4,\,8,\,11,\,12,\,11,\,8,\,4,\,1.$$
أكبر معامل هو \(12\)، وبالتالي
$$W(5040)=12.$$
وبالمثل، فإن \(45=3^2\cdot5\) يعطي \((1+x+x^2)(1+x)=1+2x+2x^2+x^3\)، ومن ثم \(W(45)=2\). وهذه هي قيم التحقق الصغيرة المستخدمة في التطبيقات.
تحتفظ تطبيقات C++ وPython وJava بمتتالية الأسس الحالية مع العدد الحالي الذي تمثله هذه المتتالية. وفي كل حالة تكرارية تعيد بناء مصفوفة معاملات \(P_n(x)\) عبر التفاف متكرر لكتل قصيرة مكونة من آحاد، ثم تأخذ أكبر معامل بوصفه العرض الحالي.
يتحرك البحث دائمًا إلى العدد الأولي التالي، ولا يجرب إلا الأسس من \(1\) حتى الأس السابق، وبذلك يفرض الترتيب غير المتزايد الذي أثبتناه سابقًا. كما أن قوة العدد الأولي التالي تتراكم بالضرب داخل الحلقة، فتستفيد الأسس الأكبر من العمل الذي أُنجز للأسس الأصغر.
عندما يتحقق العرض المستهدف، يقارن الحاصل الحالي بأفضل جواب معروف. وعندما يصبح الحاصل نفسه غير أفضل من أفضل مرشح حالي، يهمل الفرع. تستخدم نسخة C++ حسابًا بعدد صحيح ذي 128 بت للحاصل الجاري، بينما تعتمد نسختا Python وJava على أعداد صحيحة ذات دقة غير محدودة.
لننظر إلى حالة بحث تملك متتالية الأسس \(e_1,\dots,e_k\) والدرجة الكلية
$$E=e_1+\cdots+e_k.$$
إن بناء جدول المعاملات لهذه الحالة يكلف
$$\Theta\!\left(\sum_{j=1}^k (E_{j-1}+1)(e_j+1)\right),\qquad E_{j-1}=e_1+\cdots+e_{j-1},$$
وهو ما يعطي في أسوأ الأحوال \(O(E^2)\) زمنًا و\(O(E)\) ذاكرةً لمصفوفة المعاملات الحالية.
إذا رمزنا إلى مجموعة حالات البحث المزارة بـ \(S\)، فإن الزمن الكلي يساوي
$$O\!\left(\sum_{s\in S} E_s^2\right).$$
ويعتمد الحجم العملي لـ \(S\) تقريبًا بالكامل على فعالية القطع. لا توجد صيغة مغلقة بسيطة لعدد الحالات المزارة، لكن شرط عدم ازدياد الأسس مع الحد الأعلى الابتدائي الصريح يجعل شجرة البحث صغيرة بما يكفي عمليًا.