Let \(\Omega(n)\) denote the number of prime factors of \(n\), counted with multiplicity. For a fixed rank \(R\), define
$$a_t(R)=\min\left\{x:\#\{n\le x:\Omega(n)\ge t\}\ge R\right\}.$$
This means that \(a_t(R)\) is the \(R\)-th smallest positive integer whose prime-factor count is at least \(t\). The problem asks for
$$a_{10^6}(10^6)\pmod{123454321}.$$
A direct scan through the integers is hopeless, because the target threshold and the target rank are both one million. The implementations therefore search at a much smaller auxiliary level and then lift the answer to the final threshold by a rigorous doubling argument.
The central idea is to work with an intermediate threshold \(c\), find the millionth number with at least \(c\) prime factors, and then prove that once this number lies below \(3^c\), every later threshold is obtained by repeated multiplication by \(2\).
Every integer \(n\ge 2\) has a unique factorization
$$n=p_1p_2\cdots p_r,\qquad p_1\le p_2\le \cdots \le p_r,$$
where \(r=\Omega(n)\). Writing the prime factors in nondecreasing order removes duplicates automatically. For example,
$$72=2\cdot 2\cdot 2\cdot 3\cdot 3$$
appears only once when the search is constrained to stay nondecreasing. A depth-first search over such ordered prime sequences therefore enumerates every integer exactly once, while the recursion depth records \(\Omega(n)\).
For a temporary threshold \(c\), consider the set
$$S_c(X)=\{n\le X:\Omega(n)\ge c\}.$$
The implementations raise \(c\) step by step and, at the same time, set the search limit to
$$X=3^c.$$
They stop as soon as
$$\#S_c(3^c)\ge 10^6.$$
At that moment, the millionth element for threshold \(c\) satisfies
$$a_c(10^6)\le 3^c.$$
This inequality is the exact condition needed for the doubling lemma in the next step.
Assume that for some \(c\) and fixed rank \(R\) we already know
$$a_c(R)\le 3^c.$$
We claim that
$$a_{c+1}(R)=2\,a_c(R).$$
First, there are at least \(R\) numbers with \(\Omega(n)\ge c\) and \(n\le a_c(R)\). Doubling each of them gives at least \(R\) numbers with \(\Omega(n)\ge c+1\) and value at most \(2a_c(R)\). Hence
$$a_{c+1}(R)\le 2a_c(R).$$
For the reverse direction, suppose \(m<2a_c(R)\) and \(\Omega(m)\ge c+1\). If \(m\) were odd, then all of its prime factors would be at least \(3\), so
$$m\ge 3^{c+1}>2\cdot 3^c\ge 2a_c(R),$$
a contradiction. Therefore every such \(m\) must be even, and then
$$\Omega\!\left(\frac{m}{2}\right)\ge c,\qquad \frac{m}{2}<a_c(R).$$
So the map \(m\mapsto m/2\) sends all numbers counted below \(2a_c(R)\) at level \(c+1\) into the numbers counted below \(a_c(R)\) at level \(c\). There are at most \(R-1\) of those. Hence fewer than \(R\) numbers with \(\Omega(n)\ge c+1\) lie below \(2a_c(R)\), and together with the previous inequality this proves
$$a_{c+1}(R)=2a_c(R).$$
The problem uses
$$R=T=10^6.$$
Once the search finds a level \(c\) with \(a_c(R)\le 3^c\), Step 3 can be applied repeatedly:
$$a_{c+1}(R)=2a_c(R),\quad a_{c+2}(R)=2a_{c+1}(R),\quad \dots,\quad a_T(R)=2^{T-c}a_c(R).$$
Therefore the final answer is
$$a_{10^6}(10^6)\equiv a_c(10^6)\cdot 2^{10^6-c}\pmod{123454321}.$$
This is why the search only needs to determine the millionth value at the smaller threshold \(c\).
Suppose the recursion is currently at a product \(n\), has already used \(u\) prime factors, and the next allowed prime is at least \(p_i\). To reach threshold \(c\), we still need \(c-u\) more prime factors. The smallest possible completion therefore has size at least
$$n\,p_i^{\,c-u}.$$
If this lower bound already exceeds \(3^c\), then no descendant of the current state can contribute a valid value. The pruning condition is
$$n\,p_i^{\,c-u}>3^c.$$
The implementations evaluate the same test in logarithmic form to avoid overflow:
$$\log n+(c-u)\log p_i>c\log 3.$$
Because the next prime only grows as the loop advances, once the bound fails for one choice of prime it fails for all later choices too, so the loop can stop immediately.
This small example shows the same mechanism on manageable numbers. Start with \(c=3\), so the barrier is
$$3^3=27.$$
The integers \(n\le 27\) with \(\Omega(n)\ge 3\) are
$$8,\ 12,\ 16,\ 18,\ 20,\ 24,\ 27.$$
Therefore
$$a_3(5)=20\le 27.$$
Now the doubling lemma applies. Hence
$$a_4(5)=40,\qquad a_5(5)=80.$$
So the fifth number with at least five prime factors is \(80\). This is exactly the kind of checkpoint used to confirm that the enumeration and the lifting rule agree.
The C++, Python, and Java implementations follow the same pipeline. First they build a prime table up to a fixed ceiling and also store the logarithm of each prime, because the pruning rule is checked thousands of times during the depth-first search.
For a current threshold \(c\), the search limit is set to \(3^c\). The recursion then enumerates products of primes in nondecreasing order. Every time the current product already has at least \(c\) prime factors, that product is recorded as a candidate. The recursion still continues deeper, because numbers with more than \(c\) prime factors also qualify as long as they stay under the same limit.
The logarithmic lower bound from Step 5 cuts off most branches very early. Moreover, once a branch fails for a certain next prime, the implementation stops trying larger next primes from the same state, because the lower bound can only get worse.
After each run, the candidate list is checked. If it still contains fewer than one million values, the working threshold is increased by \(1\) and the search limit is multiplied by \(3\). When the list is finally large enough, it is sorted, the millionth value is extracted as \(a_c(10^6)\), and then the implementation multiplies by \(2\) exactly \(10^6-c\) times modulo \(123454321\). That last phase is equivalent to multiplying by \(2^{10^6-c}\) modulo the same number.
Let \(B\) be the prime-sieve ceiling, let \(V\) be the number of recursive states visited at the final successful threshold, and let \(M\) be the number of collected candidates at that threshold. Building the prime table costs \(O(B\log\log B)\) time and \(O(B)\) memory. The depth-first enumeration costs \(O(V)\) time, because each surviving search state is processed once. Sorting the candidate list costs \(O(M\log M)\) time and \(O(M)\) additional storage for the list itself.
The final lifting phase performs \(10^6-c\) modular doublings, so it adds \(O(10^6-c)\) time and \(O(1)\) extra memory. Overall, the running time is
$$O(B\log\log B+V+M\log M+10^6-c),$$
and the memory usage is
$$O(B+M).$$
The dominant practical cost is the search tree size \(V\), but the lower bound from Step 5 keeps it manageable.
Sei \(\Omega(n)\) die Anzahl der Primfaktoren von \(n\), wobei Vielfachheiten mitgezählt werden. Für einen festen Rang \(R\) definieren wir
$$a_t(R)=\min\left\{x:\#\{n\le x:\Omega(n)\ge t\}\ge R\right\}.$$
Dann ist \(a_t(R)\) also die \(R\)-kleinste positive Zahl mit mindestens \(t\) Primfaktoren. Gesucht ist
$$a_{10^6}(10^6)\pmod{123454321}.$$
Ein direkter Durchlauf über die natürlichen Zahlen ist hier aussichtslos, weil sowohl der Zielrang als auch der Zielschwellenwert eine Million betragen. Deshalb arbeiten die Implementierungen zunächst mit einem kleineren Hilfsschwellenwert und heben das Ergebnis anschließend mit einem exakten Verdopplungsargument auf die Endstufe an.
Die zentrale Idee ist, einen Zwischenwert \(c\) zu wählen, die millionste Zahl mit mindestens \(c\) Primfaktoren zu bestimmen und dann zu zeigen: Sobald diese Zahl unterhalb von \(3^c\) liegt, erhält man jede spätere Schwelle einfach durch Multiplikation mit \(2\).
Jede ganze Zahl \(n\ge 2\) besitzt eine eindeutige Darstellung
$$n=p_1p_2\cdots p_r,\qquad p_1\le p_2\le \cdots \le p_r,$$
wobei \(r=\Omega(n)\) ist. Wenn man die Primfaktoren stets in nichtfallender Reihenfolge schreibt, entstehen keine Mehrfachdarstellungen. Zum Beispiel erscheint
$$72=2\cdot 2\cdot 2\cdot 3\cdot 3$$
genau einmal. Eine Tiefensuche über solche geordneten Primfolgen erzeugt also jede Zahl genau einmal, und die Rekursionstiefe ist zugleich die Anzahl der verwendeten Primfaktoren.
Für eine vorläufige Schwelle \(c\) betrachten wir die Menge
$$S_c(X)=\{n\le X:\Omega(n)\ge c\}.$$
Die Implementierungen erhöhen \(c\) schrittweise und setzen gleichzeitig die Suchgrenze auf
$$X=3^c.$$
Sie stoppen genau dann, wenn
$$\#S_c(3^c)\ge 10^6$$
gilt. In diesem Moment folgt unmittelbar
$$a_c(10^6)\le 3^c.$$
Genau diese Ungleichung ist die Voraussetzung für das Verdopplungslemma im nächsten Schritt.
Nehmen wir an, für ein \(c\) und einen festen Rang \(R\) gelte bereits
$$a_c(R)\le 3^c.$$
Dann behaupten wir:
$$a_{c+1}(R)=2\,a_c(R).$$
Zunächst gibt es mindestens \(R\) Zahlen mit \(\Omega(n)\ge c\) und \(n\le a_c(R)\). Verdoppelt man jede davon, so erhält man mindestens \(R\) Zahlen mit \(\Omega(n)\ge c+1\) und Wert höchstens \(2a_c(R)\). Also
$$a_{c+1}(R)\le 2a_c(R).$$
Für die umgekehrte Richtung sei \(m<2a_c(R)\) und \(\Omega(m)\ge c+1\). Wäre \(m\) ungerade, dann wären alle Primfaktoren mindestens \(3\), also
$$m\ge 3^{c+1}>2\cdot 3^c\ge 2a_c(R),$$
ein Widerspruch. Folglich ist jedes solche \(m\) gerade, und dann gilt
$$\Omega\!\left(\frac{m}{2}\right)\ge c,\qquad \frac{m}{2}<a_c(R).$$
Die Abbildung \(m\mapsto m/2\) schickt also alle Zahlen unter \(2a_c(R)\) auf Stufe \(c+1\) in Zahlen unter \(a_c(R)\) auf Stufe \(c\). Davon gibt es höchstens \(R-1\). Zusammen mit der ersten Ungleichung folgt damit
$$a_{c+1}(R)=2a_c(R).$$
Im Problem gilt
$$R=T=10^6.$$
Sobald die Suche ein Niveau \(c\) mit \(a_c(R)\le 3^c\) gefunden hat, kann Schritt 3 beliebig oft wiederholt werden:
$$a_{c+1}(R)=2a_c(R),\quad a_{c+2}(R)=2a_{c+1}(R),\quad \dots,\quad a_T(R)=2^{T-c}a_c(R).$$
Damit reduziert sich die gesuchte Zahl auf
$$a_{10^6}(10^6)\equiv a_c(10^6)\cdot 2^{10^6-c}\pmod{123454321}.$$
Genau deshalb muss die Suche nur die millionste Zahl bei der kleineren Schwelle \(c\) direkt bestimmen.
Angenommen, die Rekursion steht bei einem aktuellen Produkt \(n\), hat bereits \(u\) Primfaktoren verwendet und darf als nächsten Faktor nur noch Primzahlen ab \(p_i\) einsetzen. Um die Schwelle \(c\) zu erreichen, fehlen noch \(c-u\) Faktoren. Die kleinstmögliche Fortsetzung hat also mindestens Größe
$$n\,p_i^{\,c-u}.$$
Wenn diese Untergrenze schon größer als \(3^c\) ist, kann kein Nachfolgerzustand mehr zulässig sein. Die Beschneidungsbedingung lautet daher
$$n\,p_i^{\,c-u}>3^c.$$
Die Implementierungen testen dieselbe Aussage in logarithmischer Form, um Überläufe zu vermeiden:
$$\log n+(c-u)\log p_i>c\log 3.$$
Da die nächste Primzahl im Schleifenverlauf nur größer wird, ist die Schranke nach dem ersten Fehlschlag für alle späteren Primzahlen erst recht verletzt. Deshalb kann die Schleife dann sofort abbrechen.
Dieses kleine Beispiel zeigt denselben Mechanismus mit handhabbaren Zahlen. Beginnen wir mit \(c=3\). Dann ist die Schranke
$$3^3=27.$$
Die Zahlen \(n\le 27\) mit \(\Omega(n)\ge 3\) sind
$$8,\ 12,\ 16,\ 18,\ 20,\ 24,\ 27.$$
Daher gilt
$$a_3(5)=20\le 27.$$
Nun greift das Verdopplungslemma, also
$$a_4(5)=40,\qquad a_5(5)=80.$$
Die fünfte Zahl mit mindestens fünf Primfaktoren ist also \(80\). Genau an solchen kleinen Kontrollpunkten lässt sich überprüfen, dass Enumeration und Hebungsvorschrift zusammenpassen.
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Zuerst erzeugen sie eine Primzahlliste bis zu einer festen Obergrenze und speichern zusätzlich die Logarithmen dieser Primzahlen, weil die Beschneidungsregel während der Tiefensuche sehr häufig ausgewertet wird.
Für eine aktuelle Arbeitsschwelle \(c\) wird die Suchgrenze auf \(3^c\) gesetzt. Danach erzeugt die Rekursion Produkte aus Primzahlen in nichtfallender Reihenfolge. Immer wenn das aktuelle Produkt bereits mindestens \(c\) Primfaktoren besitzt, wird es als Kandidat gespeichert. Die Rekursion läuft trotzdem weiter, weil auch Zahlen mit mehr als \(c\) Primfaktoren gültig bleiben, solange sie unter derselben Schranke liegen.
Die logarithmische Untergrenze aus Schritt 5 schneidet den Suchbaum frühzeitig ab. Außerdem beendet die Implementierung von einem Zustand aus den Versuch mit größeren nächsten Primzahlen sofort, sobald eine Primzahl schon scheitert, denn mit größeren Primzahlen kann die Untergrenze nur noch ungünstiger werden.
Nach jedem Durchlauf wird die Kandidatenliste geprüft. Enthält sie noch keine Million Werte, werden die Arbeitsschwelle um \(1\) erhöht und die Suchgrenze mit \(3\) multipliziert. Sobald genügend Kandidaten vorliegen, wird die Liste sortiert, der millionste Wert als \(a_c(10^6)\) entnommen und anschließend genau \(10^6-c\) Mal modulo \(123454321\) mit \(2\) multipliziert. Das ist gleichbedeutend mit einer Multiplikation mit \(2^{10^6-c}\) modulo derselben Zahl.
Sei \(B\) die Obergrenze des Primzahlensiebs, \(V\) die Zahl der tatsächlich besuchten Rekursionszustände bei der letzten erfolgreichen Schwelle und \(M\) die Zahl der dort eingesammelten Kandidaten. Der Aufbau der Primzahlliste kostet \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher. Die Tiefensuche kostet \(O(V)\) Zeit, da jeder überlebende Suchzustand genau einmal bearbeitet wird. Das Sortieren der Kandidaten benötigt \(O(M\log M)\) Zeit und \(O(M)\) Speicher für die Liste.
Die abschließende Hebung führt \(10^6-c\) modulare Verdopplungen aus und kostet daher \(O(10^6-c)\) Zeit bei \(O(1)\) Zusatzspeicher. Insgesamt ergibt sich damit
$$O(B\log\log B+V+M\log M+10^6-c)$$
Zeit und
$$O(B+M)$$
Speicher. Praktisch dominiert die Größe des Suchbaums \(V\), aber die Untergrenze aus Schritt 5 hält diesen Wert klein genug.
\(\Omega(n)\), \(n\)'nin asal çarpan sayısını tekrarlarla birlikte göstersin. Sabit bir sıra \(R\) için
$$a_t(R)=\min\left\{x:\#\{n\le x:\Omega(n)\ge t\}\ge R\right\}$$
tanımını yapalım. Yani \(a_t(R)\), en az \(t\) asal çarpanı olan sayıların artan sıralamasındaki \(R\). elemandır. Sorulan değer
$$a_{10^6}(10^6)\pmod{123454321}$$
olup doğrudan aramayla bulunamaz. Çünkü hem hedef sıra hem de hedef eşik bir milyondur. Bu yüzden implementasyonlar önce daha küçük bir yardımcı eşikte arama yapar, sonra sonucu katı bir ikiyle çarpma lemmasıyla asıl eşiğe taşır.
Ana fikir şudur: Önce ara bir \(c\) seviyesi için en az \(c\) asal çarpanı olan milyonuncu sayıyı bul, sonra bu sayı \(3^c\)'nin altına düştüğünde sonraki tüm seviyelerin sadece ikiyle çarpılarak elde edildiğini ispatla.
Her \(n\ge 2\) sayısı
$$n=p_1p_2\cdots p_r,\qquad p_1\le p_2\le \cdots \le p_r,$$
şeklinde tek biçimde yazılır; burada \(r=\Omega(n)\)'dir. Asal çarpanları küçükten büyüğe sıralamak tekrarları ortadan kaldırır. Örneğin
$$72=2\cdot 2\cdot 2\cdot 3\cdot 3$$
yalnızca bir kez üretilir. Dolayısıyla azalmayan asal dizileri üzerinde yapılan derinlik öncelikli arama, her tam sayıyı tam bir kez üretir ve özyineleme derinliği de doğrudan \(\Omega(n)\) değerini verir.
Geçici bir \(c\) eşiği için
$$S_c(X)=\{n\le X:\Omega(n)\ge c\}$$
kümesini ele alalım. Implementasyonlar \(c\)'yi adım adım artırırken arama sınırını da
$$X=3^c$$
olarak alır. Şu koşul ilk kez sağlandığında dururlar:
$$\#S_c(3^c)\ge 10^6.$$
Bu anda milyonuncu eleman için otomatik olarak
$$a_c(10^6)\le 3^c$$
elde edilir. Bir sonraki adımdaki ikiyle çarpma lemmması tam olarak bu eşitsizliğe ihtiyaç duyar.
Bir \(c\) ve sabit sıra \(R\) için
$$a_c(R)\le 3^c$$
bildiğimizi varsayalım. İddiamız şudur:
$$a_{c+1}(R)=2\,a_c(R).$$
Önce, \(\Omega(n)\ge c\) ve \(n\le a_c(R)\) olan en az \(R\) sayı vardır. Bunların her birini ikiyle çarparsak, \(\Omega(n)\ge c+1\) koşulunu sağlayan ve değeri en fazla \(2a_c(R)\) olan en az \(R\) sayı elde ederiz. Demek ki
$$a_{c+1}(R)\le 2a_c(R).$$
Ters yön için \(m<2a_c(R)\) ve \(\Omega(m)\ge c+1\) olsun. Eğer \(m\) tek olsaydı, tüm asal çarpanları en az \(3\) olurdu; bu durumda
$$m\ge 3^{c+1}>2\cdot 3^c\ge 2a_c(R)$$
çelişkisi çıkardı. O halde böyle bir \(m\) mutlaka çifttir ve
$$\Omega\!\left(\frac{m}{2}\right)\ge c,\qquad \frac{m}{2}<a_c(R)$$
olur. Yani \(m\mapsto m/2\) dönüşümü, seviye \(c+1\)'de \(2a_c(R)\)'nin altındaki tüm sayıları seviye \(c\)'de \(a_c(R)\)'nin altındaki sayılara taşır. Bunlardan en fazla \(R-1\) tane olabilir. İlk eşitsizlikle birlikte sonuç
$$a_{c+1}(R)=2a_c(R)$$
olur.
Problemde
$$R=T=10^6$$
kullanılır. Arama \(a_c(R)\le 3^c\) sağlayan bir \(c\) bulduktan sonra Adım 3 art arda uygulanır:
$$a_{c+1}(R)=2a_c(R),\quad a_{c+2}(R)=2a_{c+1}(R),\quad \dots,\quad a_T(R)=2^{T-c}a_c(R).$$
Böylece nihai cevap
$$a_{10^6}(10^6)\equiv a_c(10^6)\cdot 2^{10^6-c}\pmod{123454321}$$
şeklinde yazılır. Yani büyük iş, yalnızca daha küçük eşik \(c\) için milyonuncu sayıyı bulmaktır.
Özyineleme şu durumda olsun: mevcut çarpım \(n\), kullanılan asal çarpan sayısı \(u\), izin verilen bir sonraki asalın en küçüğü \(p_i\). Eşik \(c\)'ye ulaşmak için hâlâ \(c-u\) tane asal çarpan gerekir. Bu durumda mümkün olan en küçük tamamlama en az
$$n\,p_i^{\,c-u}$$
büyüklüğündedir. Eğer bu değer zaten \(3^c\)'yi aşıyorsa, o dalın hiçbir devamı geçerli olamaz. Budama koşulu
$$n\,p_i^{\,c-u}>3^c$$
şeklindedir. Implementasyonlar taşma riskini azaltmak için aynı testi logaritmik biçimde uygular:
$$\log n+(c-u)\log p_i>c\log 3.$$
Döngü ilerledikçe bir sonraki asal yalnızca büyüdüğünden, bir asal için başarısız olan bu alt sınır daha büyük asallar için de başarısız olacaktır. Bu yüzden aynı durumdan daha sonraki seçimler hemen kesilebilir.
Bu küçük örnek aynı mekanizmayı somut olarak gösterir. \(c=3\) ile başlayalım. Bariyer
$$3^3=27$$
olur. \(\Omega(n)\ge 3\) ve \(n\le 27\) koşulunu sağlayan sayılar
$$8,\ 12,\ 16,\ 18,\ 20,\ 24,\ 27$$
şeklindedir. Dolayısıyla
$$a_3(5)=20\le 27.$$
Artık ikiyle çarpma lemmması geçerlidir. O halde
$$a_4(5)=40,\qquad a_5(5)=80.$$
Yani en az beş asal çarpanı olan 5. sayı \(80\)'dir. Bu, arama ve yükseltme mantığının uyuştuğunu gösteren ideal bir küçük kontrol örneğidir.
C++, Python ve Java implementasyonları aynı akışı izler. Önce sabit bir üst sınıra kadar asal sayılar üretilir ve her asalın logaritması saklanır; çünkü budama kuralı derinlik öncelikli arama sırasında çok sık test edilir.
Mevcut çalışma eşiği \(c\) için arama sınırı \(3^c\) olarak alınır. Sonra özyineleme, asalları azalmayan sırayla çarparak olası ürünleri üretir. Bir ürün en az \(c\) asal çarpana ulaştığı anda aday listesine eklenir. Arama yine de daha derine devam eder; çünkü \(c\)'den fazla asal çarpanı olan sayılar da aynı sınır altında kaldıkları sürece geçerlidir.
Adım 5'teki logaritmik alt sınır, dalların büyük kısmını çok erken keser. Ayrıca bir durumdan çıkarken belirli bir sonraki asal başarısız olduğunda, daha büyük asallar denenmez; çünkü alt sınır sadece daha kötüleşir.
Her turdan sonra aday sayısı kontrol edilir. Liste hâlâ bir milyondan küçükse, çalışma eşiği \(1\) artırılır ve arama sınırı \(3\) ile çarpılır. Liste yeterli büyüklüğe ulaştığında sıralanır, milyonuncu eleman \(a_c(10^6)\) olarak alınır ve ardından \(123454321\) modunda tam \(10^6-c\) kez ikiyle çarpılır. Bu son aşama, aynı mod altında \(2^{10^6-c}\) ile çarpmaya denktir.
\(B\) asal süzgeci üst sınırı, \(V\) son başarılı eşikte ziyaret edilen özyineleme durumu sayısı, \(M\) ise o eşikte toplanan aday sayısı olsun. Asal tablosunu kurmak \(O(B\log\log B)\) zaman ve \(O(B)\) bellek ister. Derinlik öncelikli üretim \(O(V)\) zaman alır; çünkü her yaşayan durum yalnızca bir kez işlenir. Aday listesinin sıralanması \(O(M\log M)\) zaman ve listenin kendisi için \(O(M)\) bellek gerektirir.
Son yükseltme aşaması \(10^6-c\) adet modüler ikiyle çarpma içerir; dolayısıyla \(O(10^6-c)\) zaman ve \(O(1)\) ek bellek kullanır. Toplam çalışma süresi
$$O(B\log\log B+V+M\log M+10^6-c)$$
ve toplam bellek kullanımı
$$O(B+M)$$
olur. Pratikte belirleyici unsur arama ağacının büyüklüğü olan \(V\)'dir; fakat Adım 5'teki alt sınır bu değeri yönetilebilir seviyede tutar.
Sea \(\Omega(n)\) el número de factores primos de \(n\), contando multiplicidades. Para un rango fijo \(R\), definimos
$$a_t(R)=\min\left\{x:\#\{n\le x:\Omega(n)\ge t\}\ge R\right\}.$$
Así, \(a_t(R)\) es el \(R\)-ésimo entero positivo más pequeño con al menos \(t\) factores primos. El problema pide
$$a_{10^6}(10^6)\pmod{123454321}.$$
Un barrido directo sobre los enteros es imposible, porque tanto el umbral final como el rango buscado valen un millón. Por eso las implementaciones trabajan primero con un nivel auxiliar mucho menor y luego elevan el resultado hasta el umbral final mediante un argumento exacto de duplicación.
La idea central es elegir un nivel intermedio \(c\), hallar el millonésimo número con al menos \(c\) factores primos y demostrar que, una vez que ese número cae por debajo de \(3^c\), todos los niveles posteriores se obtienen simplemente multiplicando por \(2\).
Cada entero \(n\ge 2\) tiene una descomposición única
$$n=p_1p_2\cdots p_r,\qquad p_1\le p_2\le \cdots \le p_r,$$
donde \(r=\Omega(n)\). Escribir los primos en orden no decreciente elimina duplicados automáticamente. Por ejemplo,
$$72=2\cdot 2\cdot 2\cdot 3\cdot 3$$
aparece una sola vez si la búsqueda obliga a mantener ese orden. Una búsqueda en profundidad sobre estas secuencias ordenadas enumera así cada entero exactamente una vez, y la profundidad de la recursión coincide con \(\Omega(n)\).
Para un umbral temporal \(c\), consideremos el conjunto
$$S_c(X)=\{n\le X:\Omega(n)\ge c\}.$$
Las implementaciones aumentan \(c\) paso a paso y, al mismo tiempo, fijan el límite de búsqueda en
$$X=3^c.$$
Se detienen cuando
$$\#S_c(3^c)\ge 10^6.$$
En ese instante, el millonésimo elemento para el umbral \(c\) satisface
$$a_c(10^6)\le 3^c.$$
Esa desigualdad es exactamente la hipótesis necesaria para el lema de duplicación del paso siguiente.
Supongamos que para cierto \(c\) y un rango fijo \(R\) ya sabemos que
$$a_c(R)\le 3^c.$$
Afirmamos entonces que
$$a_{c+1}(R)=2\,a_c(R).$$
Primero, existen al menos \(R\) números con \(\Omega(n)\ge c\) y \(n\le a_c(R)\). Si duplicamos cada uno, obtenemos al menos \(R\) números con \(\Omega(n)\ge c+1\) y valor como máximo \(2a_c(R)\). Por tanto,
$$a_{c+1}(R)\le 2a_c(R).$$
Para la otra dirección, sea \(m<2a_c(R)\) con \(\Omega(m)\ge c+1\). Si \(m\) fuera impar, todos sus factores primos serían al menos \(3\), y entonces
$$m\ge 3^{c+1}>2\cdot 3^c\ge 2a_c(R),$$
lo cual es imposible. Así que todo tal \(m\) debe ser par, y en consecuencia
$$\Omega\!\left(\frac{m}{2}\right)\ge c,\qquad \frac{m}{2}<a_c(R).$$
La aplicación \(m\mapsto m/2\) envía todos los números contados por debajo de \(2a_c(R)\) en el nivel \(c+1\) a números contados por debajo de \(a_c(R)\) en el nivel \(c\). De estos hay como máximo \(R-1\). Junto con la desigualdad anterior, eso demuestra
$$a_{c+1}(R)=2a_c(R).$$
En el problema se usa
$$R=T=10^6.$$
Una vez encontrado un nivel \(c\) con \(a_c(R)\le 3^c\), el Paso 3 se puede aplicar repetidamente:
$$a_{c+1}(R)=2a_c(R),\quad a_{c+2}(R)=2a_{c+1}(R),\quad \dots,\quad a_T(R)=2^{T-c}a_c(R).$$
Por lo tanto, el valor final se reduce a
$$a_{10^6}(10^6)\equiv a_c(10^6)\cdot 2^{10^6-c}\pmod{123454321}.$$
Eso explica por qué la búsqueda directa solo necesita encontrar el millonésimo valor en el umbral menor \(c\).
Supongamos que la recursión está en un producto actual \(n\), ya ha usado \(u\) factores primos y el siguiente primo permitido es al menos \(p_i\). Para llegar al umbral \(c\), todavía faltan \(c-u\) factores. La finalización más pequeña posible tiene tamaño al menos
$$n\,p_i^{\,c-u}.$$
Si esa cota ya supera \(3^c\), entonces ningún descendiente del estado actual puede producir un candidato válido. La condición de poda es
$$n\,p_i^{\,c-u}>3^c.$$
Las implementaciones evalúan la misma condición en forma logarítmica para evitar desbordamientos:
$$\log n+(c-u)\log p_i>c\log 3.$$
Como el siguiente primo solo aumenta a medida que avanza el bucle, si la cota falla para una opción concreta también fallará para todas las opciones posteriores, de modo que se puede romper el bucle de inmediato.
Este ejemplo pequeño muestra el mismo mecanismo con números manejables. Empezamos con \(c=3\), así que la barrera es
$$3^3=27.$$
Los enteros \(n\le 27\) con \(\Omega(n)\ge 3\) son
$$8,\ 12,\ 16,\ 18,\ 20,\ 24,\ 27.$$
Por tanto,
$$a_3(5)=20\le 27.$$
Ahora ya se puede aplicar el lema de duplicación. En consecuencia,
$$a_4(5)=40,\qquad a_5(5)=80.$$
Así, el quinto número con al menos cinco factores primos es \(80\). Es una verificación corta pero muy útil de que la enumeración y la fase de elevación son coherentes entre sí.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero construyen una tabla de primos hasta un tope fijo y almacenan también el logaritmo de cada primo, porque la regla de poda se evalúa continuamente durante la búsqueda en profundidad.
Para un umbral de trabajo \(c\), el límite de búsqueda se fija en \(3^c\). La recursión genera entonces productos de primos en orden no decreciente. En cuanto el producto actual ya tiene al menos \(c\) factores primos, se guarda como candidato. La búsqueda sigue descendiendo, porque los números con más de \(c\) factores también son válidos siempre que permanezcan por debajo del mismo límite.
La cota inferior logarítmica del Paso 5 elimina la mayor parte del árbol muy pronto. Además, en un estado dado, si una elección del siguiente primo ya falla, la implementación deja de probar primos más grandes desde ese mismo punto, porque la cota solo puede empeorar.
Después de cada ejecución se revisa la lista de candidatos. Si todavía contiene menos de un millón de valores, el umbral de trabajo aumenta en \(1\) y el límite de búsqueda se multiplica por \(3\). Cuando la lista finalmente es suficientemente grande, se ordena, se toma el valor millonésimo como \(a_c(10^6)\) y luego se multiplica por \(2\) exactamente \(10^6-c\) veces módulo \(123454321\). Esa fase final equivale a multiplicar por \(2^{10^6-c}\) en el mismo módulo.
Sea \(B\) el límite de la criba de primos, \(V\) el número de estados recursivos visitados en el umbral final exitoso y \(M\) la cantidad de candidatos reunidos en ese umbral. Construir la tabla de primos cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) memoria. La enumeración en profundidad cuesta \(O(V)\) tiempo, porque cada estado que sobrevive a la poda se procesa una sola vez. Ordenar la lista de candidatos cuesta \(O(M\log M)\) tiempo y \(O(M)\) memoria para la propia lista.
La fase final de elevación realiza \(10^6-c\) duplicaciones modulares, así que añade \(O(10^6-c)\) tiempo y \(O(1)\) memoria extra. En conjunto, el tiempo total es
$$O(B\log\log B+V+M\log M+10^6-c),$$
y la memoria total es
$$O(B+M).$$
En la práctica, el coste dominante es el tamaño del árbol de búsqueda \(V\), pero la cota del Paso 5 lo mantiene bajo control.
设 \(\Omega(n)\) 表示 \(n\) 的质因子总数，重数也计入其中。对固定排名 \(R\)，定义
$$a_t(R)=\min\left\{x:\#\{n\le x:\Omega(n)\ge t\}\ge R\right\}.$$
也就是说，\(a_t(R)\) 是所有满足 \(\Omega(n)\ge t\) 的正整数按从小到大排列后的第 \(R\) 个。题目要求的是
$$a_{10^6}(10^6)\pmod{123454321}.$$
这里不能做朴素枚举，因为目标阈值和目标排名都等于一百万。实现采用的办法是：先在一个远小于最终阈值的辅助层级上求出同一排名的答案，再用一个严格的倍增引理把结果提升到真正需要的层级。
整个方法的核心是先选择一个中间阈值 \(c\)，找出“至少有 \(c\) 个质因子”的第 \(10^6\) 个数；一旦证明这个数已经落在 \(3^c\) 以下，就能推出更高阈值下对应的第 \(10^6\) 个数只是不断乘以 \(2\)。
任意整数 \(n\ge 2\) 都可以唯一写成
$$n=p_1p_2\cdots p_r,\qquad p_1\le p_2\le \cdots \le p_r,$$
其中 \(r=\Omega(n)\)。把质因子按非降顺序排列后，每个整数只会出现一次，不会因为不同的乘法顺序而重复。例如
$$72=2\cdot 2\cdot 2\cdot 3\cdot 3$$
在这种表示法下只对应一个序列。因此，对“非降质因子序列”做深度优先搜索，就等价于把所有整数按唯一方式生成出来，而递归深度本身就记录了 \(\Omega(n)\) 的大小。
对临时阈值 \(c\)，考虑集合
$$S_c(X)=\{n\le X:\Omega(n)\ge c\}.$$
实现并不是直接对最终阈值 \(10^6\) 搜索，而是逐步增加 \(c\)，同时把搜索上界设为
$$X=3^c.$$
一旦满足
$$\#S_c(3^c)\ge 10^6,$$
就停止增长。此时“至少有 \(c\) 个质因子”的第 \(10^6\) 个数一定满足
$$a_c(10^6)\le 3^c.$$
这个不等式看起来只是一个界，但它实际上正是后续倍增论证成立的关键。
设对某个 \(c\) 和固定排名 \(R\)，已经知道
$$a_c(R)\le 3^c.$$
我们要证明
$$a_{c+1}(R)=2\,a_c(R).$$
先看上界。所有满足 \(\Omega(n)\ge c\) 且 \(n\le a_c(R)\) 的数至少有 \(R\) 个。把每一个都乘以 \(2\)，就得到至少 \(R\) 个满足 \(\Omega(n)\ge c+1\) 且不超过 \(2a_c(R)\) 的数。因此
$$a_{c+1}(R)\le 2a_c(R).$$
再看下界。若 \(m<2a_c(R)\) 且 \(\Omega(m)\ge c+1\)，那么 \(m\) 不可能是奇数。因为奇数的所有质因子都至少为 \(3\)，于是
$$m\ge 3^{c+1}>2\cdot 3^c\ge 2a_c(R),$$
这与 \(m<2a_c(R)\) 矛盾。于是这样的 \(m\) 必然是偶数，并且
$$\Omega\!\left(\frac{m}{2}\right)\ge c,\qquad \frac{m}{2}<a_c(R).$$
这说明所有落在 \(2a_c(R)\) 以下、且满足 \(\Omega(n)\ge c+1\) 的数，都可以通过“除以 \(2\)”映射到落在 \(a_c(R)\) 以下、且满足 \(\Omega(n)\ge c\) 的数。后者最多只有 \(R-1\) 个严格小于 \(a_c(R)\) 的元素。因此 \(2a_c(R)\) 以下还不到 \(R\) 个候选，结合前面的上界，得到
$$a_{c+1}(R)=2a_c(R).$$
题目中取
$$R=T=10^6.$$
一旦搜索找到了某个 \(c\)，使得 \(a_c(R)\le 3^c\)，那么步骤 3 可以不断重复：
$$a_{c+1}(R)=2a_c(R),\quad a_{c+2}(R)=2a_{c+1}(R),\quad \dots,\quad a_T(R)=2^{T-c}a_c(R).$$
因此最终答案可以写成
$$a_{10^6}(10^6)\equiv a_c(10^6)\cdot 2^{10^6-c}\pmod{123454321}.$$
这说明真正困难的部分，不是直接逼近阈值 \(10^6\)，而是先在较小的 \(c\) 上找到同一排名的数，然后用严格的结构性质把它提升上去。
设递归当前位于乘积 \(n\)，已经使用了 \(u\) 个质因子，而下一个允许选择的最小质数是 \(p_i\)。如果目标是达到阈值 \(c\)，那么还需要 \(c-u\) 个质因子。此时任何后继状态的最小可能值至少是
$$n\,p_i^{\,c-u}.$$
若这个最小可能值已经超过 \(3^c\)，那么当前分支无论如何扩展都不可能产生有效候选，必须立即剪掉。剪枝条件就是
$$n\,p_i^{\,c-u}>3^c.$$
实现里为了避免整数溢出，使用的是完全等价的对数形式：
$$\log n+(c-u)\log p_i>c\log 3.$$
而且由于循环中的下一个质数只会越来越大，一旦某个质数已经让这个下界失败，那么后面更大的质数只会更差，所以可以直接结束这一层循环。
这个小例子足以说明整个机制。先取 \(c=3\)，这时屏障是
$$3^3=27.$$
满足 \(\Omega(n)\ge 3\) 且 \(n\le 27\) 的整数是
$$8,\ 12,\ 16,\ 18,\ 20,\ 24,\ 27.$$
因此
$$a_3(5)=20\le 27.$$
于是倍增引理开始生效，从而有
$$a_4(5)=40,\qquad a_5(5)=80.$$
也就是说，按从小到大排序后，“至少有 5 个质因子”的第 5 个数就是 \(80\)。这个例子规模很小，却准确展示了“先搜索，再倍增”的完整逻辑。
C++、Python 和 Java 三份实现遵循完全相同的流程。首先，它们在一个固定上限内生成质数表，并且预先保存每个质数的对数值，因为剪枝判定会在深度优先搜索中被反复调用。
对当前工作阈值 \(c\)，搜索上界设为 \(3^c\)。递归按非降顺序不断往当前乘积后面附加质数，从而生成所有可能的候选。只要当前乘积的质因子总数已经达到 \(c\)，它就会被加入候选列表。不过递归不会立即停止，因为拥有超过 \(c\) 个质因子的数同样满足条件，只要它们还没有超出上界。
步骤 5 的对数下界会在很浅的层数就剪掉大量无望分支。另外，在同一个递归状态里，如果某个“下一个质数”的选择已经失败，那么实现会直接停止尝试更大的质数，因为那样只会使下界更大，不可能重新变得可行。
每完成一轮搜索，就检查候选数量是否已经达到一百万。如果还不够，就把工作阈值加 \(1\)，并把搜索上界乘以 \(3\)。一旦候选足够，先排序，再取出第 \(10^6\) 个值作为 \(a_c(10^6)\)，然后在模 \(123454321\) 下重复乘以 \(2\) 共 \(10^6-c\) 次。这个阶段与直接乘上 \(2^{10^6-c}\) 在同一模数下是等价的。
设质数筛上界为 \(B\)，最终成功阈值下被访问的递归状态数为 \(V\)，该阈值下收集到的候选个数为 \(M\)。构造质数表需要 \(O(B\log\log B)\) 时间和 \(O(B)\) 空间。深度优先枚举需要 \(O(V)\) 时间，因为每个未被剪枝的状态只处理一次。候选排序需要 \(O(M\log M)\) 时间，而候选列表本身占用 \(O(M)\) 空间。
最后的提升阶段还需要执行 \(10^6-c\) 次模乘 \(2\)，因此再增加 \(O(10^6-c)\) 时间和 \(O(1)\) 额外空间。总时间复杂度为
$$O(B\log\log B+V+M\log M+10^6-c),$$
总空间复杂度为
$$O(B+M).$$
实际运行中，最关键的量是搜索树规模 \(V\)，但步骤 5 的下界对其有很强的压缩作用。
Пусть \(\Omega(n)\) обозначает число простых множителей числа \(n\) с учетом кратностей. Для фиксированного ранга \(R\) определим
$$a_t(R)=\min\left\{x:\#\{n\le x:\Omega(n)\ge t\}\ge R\right\}.$$
То есть \(a_t(R)\) есть \(R\)-е по возрастанию положительное целое число, у которого как минимум \(t\) простых множителей. В задаче требуется найти
$$a_{10^6}(10^6)\pmod{123454321}.$$
Полный перебор невозможен: и целевой ранг, и целевой порог равны одному миллиону. Поэтому реализации сначала работают на гораздо меньшем вспомогательном уровне, а затем поднимают найденный ответ к конечному порогу с помощью строгого лемматического правила удвоения.
Основная идея состоит в следующем: выбрать промежуточный порог \(c\), найти миллионное число с условием \(\Omega(n)\ge c\), а затем доказать, что как только это число оказывается не больше \(3^c\), переход к каждому следующему порогу равносилен умножению на \(2\).
Каждое число \(n\ge 2\) единственным образом представляется как
$$n=p_1p_2\cdots p_r,\qquad p_1\le p_2\le \cdots \le p_r,$$
где \(r=\Omega(n)\). Если всегда записывать простые множители в неубывающем порядке, то дубликаты исчезают автоматически. Например,
$$72=2\cdot 2\cdot 2\cdot 3\cdot 3$$
возникает ровно один раз. Поэтому поиск в глубину по таким упорядоченным цепочкам простых перечисляет каждое число единожды, а глубина рекурсии одновременно хранит значение \(\Omega(n)\).
Для временного порога \(c\) рассмотрим множество
$$S_c(X)=\{n\le X:\Omega(n)\ge c\}.$$
Реализации постепенно увеличивают \(c\) и одновременно берут поисковое ограничение
$$X=3^c.$$
Поиск останавливается, когда выполняется условие
$$\#S_c(3^c)\ge 10^6.$$
В этот момент автоматически верно
$$a_c(10^6)\le 3^c.$$
Именно это неравенство и нужно для следующего шага.
Пусть для некоторого \(c\) и фиксированного ранга \(R\) уже известно, что
$$a_c(R)\le 3^c.$$
Тогда утверждается, что
$$a_{c+1}(R)=2\,a_c(R).$$
Сначала получим верхнюю оценку. Есть по крайней мере \(R\) чисел с \(\Omega(n)\ge c\) и \(n\le a_c(R)\). Если каждое из них умножить на \(2\), то получится по крайней мере \(R\) чисел с \(\Omega(n)\ge c+1\) и значением не больше \(2a_c(R)\). Следовательно,
$$a_{c+1}(R)\le 2a_c(R).$$
Теперь нижняя оценка. Пусть \(m<2a_c(R)\) и \(\Omega(m)\ge c+1\). Если бы \(m\) было нечетным, то все его простые множители были бы не меньше \(3\), а значит
$$m\ge 3^{c+1}>2\cdot 3^c\ge 2a_c(R),$$
что невозможно. Значит, такое \(m\) обязательно четно, и тогда
$$\Omega\!\left(\frac{m}{2}\right)\ge c,\qquad \frac{m}{2}<a_c(R).$$
Тем самым отображение \(m\mapsto m/2\) переводит все числа уровня \(c+1\), лежащие ниже \(2a_c(R)\), в числа уровня \(c\), лежащие ниже \(a_c(R)\). Последних строго меньше \(R\). Совмещая это с верхней оценкой, получаем
$$a_{c+1}(R)=2a_c(R).$$
В задаче используется
$$R=T=10^6.$$
Как только найден уровень \(c\), для которого \(a_c(R)\le 3^c\), шаг 3 можно применять снова и снова:
$$a_{c+1}(R)=2a_c(R),\quad a_{c+2}(R)=2a_{c+1}(R),\quad \dots,\quad a_T(R)=2^{T-c}a_c(R).$$
Следовательно, окончательный ответ равен
$$a_{10^6}(10^6)\equiv a_c(10^6)\cdot 2^{10^6-c}\pmod{123454321}.$$
Именно поэтому основной поиск нужно провести лишь для меньшего порога \(c\), а затем поднять результат наверх строго доказанным способом.
Пусть рекурсия находится в состоянии с текущим произведением \(n\), уже использовано \(u\) простых множителей, а следующий разрешенный простой не меньше \(p_i\). Чтобы дойти до порога \(c\), еще нужно добавить \(c-u\) множителей. Самое маленькое возможное продолжение тогда имеет размер не меньше
$$n\,p_i^{\,c-u}.$$
Если эта величина уже больше \(3^c\), никакой потомок текущего состояния не сможет дать корректный кандидат. Условие отсечения имеет вид
$$n\,p_i^{\,c-u}>3^c.$$
Чтобы избежать переполнения, реализации проверяют эквивалентную логарифмическую форму:
$$\log n+(c-u)\log p_i>c\log 3.$$
Поскольку в цикле следующий простой только возрастает, то после первого неудачного выбора все более крупные простые тем более не подойдут, и цикл можно завершить сразу.
Этот маленький пример показывает тот же самый механизм на коротком списке. Возьмем \(c=3\), тогда барьер равен
$$3^3=27.$$
Числа \(n\le 27\) с условием \(\Omega(n)\ge 3\) таковы:
$$8,\ 12,\ 16,\ 18,\ 20,\ 24,\ 27.$$
Значит,
$$a_3(5)=20\le 27.$$
После этого сразу работает лемма об удвоении, и потому
$$a_4(5)=40,\qquad a_5(5)=80.$$
Следовательно, пятое число с не менее чем пятью простыми множителями равно \(80\). Это удобная проверка того, что процедура перечисления и правило подъема действительно согласованы.
Реализации на C++, Python и Java устроены одинаково. Сначала строится таблица простых чисел до фиксированного предела, а также сохраняются логарифмы этих простых, поскольку условие отсечения проверяется очень часто во время поиска в глубину.
Для текущего рабочего порога \(c\) поисковая граница равна \(3^c\). Затем рекурсия порождает произведения простых в неубывающем порядке. Как только текущее произведение уже имеет не меньше \(c\) простых множителей, оно заносится в список кандидатов. Поиск при этом продолжается глубже, потому что числа с числом множителей больше \(c\) тоже подходят, если не выходят за ту же границу.
Логарифмическая граница из шага 5 очень рано обрезает большую часть дерева. Кроме того, если из некоторого состояния уже не проходит один выбор следующего простого, то реализация сразу прекращает пробовать более крупные простые из того же состояния: нижняя граница после этого только ухудшается.
После каждого запуска проверяется размер списка кандидатов. Если там еще меньше миллиона значений, рабочий порог увеличивается на \(1\), а поисковая граница умножается на \(3\). Когда кандидатов становится достаточно, список сортируется, миллионный элемент берется как \(a_c(10^6)\), и затем это число \(10^6-c\) раз умножается на \(2\) по модулю \(123454321\). Это полностью эквивалентно умножению на \(2^{10^6-c}\) по тому же модулю.
Пусть \(B\) обозначает предел решета простых, \(V\) — число рекурсивных состояний, посещенных на последнем успешном уровне, а \(M\) — число собранных кандидатов на этом уровне. Построение таблицы простых требует \(O(B\log\log B)\) времени и \(O(B)\) памяти. Поиск в глубину занимает \(O(V)\) времени, потому что каждое состояние, не отсеченное заранее, обрабатывается ровно один раз. Сортировка списка кандидатов стоит \(O(M\log M)\) времени и использует \(O(M)\) памяти для самого списка.
Финальная фаза подъема выполняет \(10^6-c\) модульных удвоений, то есть добавляет \(O(10^6-c)\) времени и \(O(1)\) дополнительной памяти. В сумме получаем время
$$O(B\log\log B+V+M\log M+10^6-c),$$
а память
$$O(B+M).$$
На практике решающим фактором является размер дерева поиска \(V\), но нижняя граница из шага 5 делает его достаточно малым.
لتكن \(\Omega(n)\) هي عدد العوامل الأولية للعدد \(n\) مع احتساب التكرار. ولرتبة ثابتة \(R\) نعرّف
$$a_t(R)=\min\left\{x:\#\{n\le x:\Omega(n)\ge t\}\ge R\right\}.$$
وبذلك يكون \(a_t(R)\) هو العدد الموجب رقم \(R\) في الترتيب التصاعدي بين الأعداد التي تمتلك على الأقل \(t\) عوامل أولية. المطلوب في هذه المسألة هو
$$a_{10^6}(10^6)\pmod{123454321}.$$
الفحص المباشر للأعداد واحدًا واحدًا مستحيل عمليًا، لأن حدَّ العوامل المطلوب والرتبة المطلوبة كلاهما يساوي مليونًا. لذلك تبدأ الحلول من مستوى مساعد أصغر بكثير، ثم ترفع النتيجة إلى المستوى النهائي باستخدام مبرهنة دقيقة تعتمد على الضرب المتكرر في \(2\).
الفكرة المحورية هي اختيار عتبة وسيطة \(c\)، ثم إيجاد العدد رقم مليون الذي يحقق \(\Omega(n)\ge c\)، وبعد ذلك إثبات أن هذا العدد متى صار واقعًا تحت \(3^c\)، فإن الانتقال إلى كل عتبة أعلى لا يحتاج إلا إلى ضرب النتيجة في \(2\).
كل عدد \(n\ge 2\) يملك تمثيلًا وحيدًا من الصورة
$$n=p_1p_2\cdots p_r,\qquad p_1\le p_2\le \cdots \le p_r,$$
حيث \(r=\Omega(n)\). وعندما نكتب العوامل الأولية بترتيب غير متناقص، فإننا نمنع التكرار الناتج من تبديل ترتيب الضرب. على سبيل المثال،
$$72=2\cdot 2\cdot 2\cdot 3\cdot 3$$
يظهر مرة واحدة فقط في هذا النظام. ومن ثم فإن البحث العميق في سلاسل العوامل الأولية المرتبة يولّد كل عدد صحيح مرة واحدة بالضبط، بينما يعطي عمق الاستدعاء التراجعي قيمة \(\Omega(n)\) مباشرة.
لعتبة مؤقتة \(c\)، لننظر إلى المجموعة
$$S_c(X)=\{n\le X:\Omega(n)\ge c\}.$$
التنفيذ لا يبدأ من العتبة النهائية \(10^6\)، بل يزيد \(c\) تدريجيًا ويأخذ حد البحث
$$X=3^c.$$
ويتوقف فور تحقق الشرط
$$\#S_c(3^c)\ge 10^6.$$
وعند هذه اللحظة يصبح من المؤكد أن
$$a_c(10^6)\le 3^c.$$
وهذه العلاقة ليست تفصيلًا ثانويًا، بل هي الشرط الذي تعتمد عليه خطوة الرفع بالكامل.
افترض أنه لعتبة ما \(c\) ورتبة ثابتة \(R\) نعرف أن
$$a_c(R)\le 3^c.$$
عندئذٍ ندّعي أن
$$a_{c+1}(R)=2\,a_c(R).$$
أولًا، يوجد على الأقل \(R\) عددًا تحقق \(\Omega(n)\ge c\) وتقع عند أو تحت \(a_c(R)\). وإذا ضربنا كل واحد منها في \(2\)، نحصل على \(R\) أعداد على الأقل تحقق \(\Omega(n)\ge c+1\) وتقع عند أو تحت \(2a_c(R)\). ولذلك
$$a_{c+1}(R)\le 2a_c(R).$$
وللعكس، خذ عددًا \(m<2a_c(R)\) يحقق \(\Omega(m)\ge c+1\). لو كان \(m\) فرديًا لكانت جميع عوامله الأولية لا تقل عن \(3\)، وبالتالي
$$m\ge 3^{c+1}>2\cdot 3^c\ge 2a_c(R),$$
وهذا تناقض. إذن كل عدد من هذا النوع لا بد أن يكون زوجيًا، وبالتالي
$$\Omega\!\left(\frac{m}{2}\right)\ge c,\qquad \frac{m}{2}<a_c(R).$$
أي أن القسمة على \(2\) ترسل جميع الأعداد الواقعة تحت \(2a_c(R)\) في المستوى \(c+1\) إلى أعداد واقعة تحت \(a_c(R)\) في المستوى \(c\). وهذه الأخيرة أقل من \(R\) عددًا. وبضم هذا إلى المتباينة الأولى نحصل على
$$a_{c+1}(R)=2a_c(R).$$
في هذه المسألة نأخذ
$$R=T=10^6.$$
وبمجرد العثور على قيمة \(c\) تحقق \(a_c(R)\le 3^c\)، يمكن تكرار الخطوة السابقة مرارًا:
$$a_{c+1}(R)=2a_c(R),\quad a_{c+2}(R)=2a_{c+1}(R),\quad \dots,\quad a_T(R)=2^{T-c}a_c(R).$$
ومن ثم تصبح القيمة المطلوبة
$$a_{10^6}(10^6)\equiv a_c(10^6)\cdot 2^{10^6-c}\pmod{123454321}.$$
وهكذا يتبين أن الجزء الصعب هو العثور على العدد رقم مليون عند عتبة أصغر بكثير، ثم استخدام البنية الرياضية لرفعه إلى العتبة النهائية.
لنفترض أن الاستدعاء التراجعي يقف عند حاصل ضرب حالي \(n\)، وقد استُخدم حتى الآن \(u\) عاملًا أوليًا، وأن أصغر أولي مسموح به تاليًا هو \(p_i\). للوصول إلى العتبة \(c\) ما زلنا بحاجة إلى \(c-u\) عوامل أولية أخرى. وعندئذٍ يكون أصغر امتداد ممكن مساويًا على الأقل لـ
$$n\,p_i^{\,c-u}.$$
فإذا تجاوز هذا الحد الأدنى قيمة \(3^c\)، فلن يستطيع أي امتداد من هذا الفرع إنتاج مرشح صالح. إذن شرط التقليم هو
$$n\,p_i^{\,c-u}>3^c.$$
ولتجنب مشاكل الفيض العددي، تستخدم الحلول الصيغة اللوغاريتمية المكافئة:
$$\log n+(c-u)\log p_i>c\log 3.$$
وبما أن الأولي التالي يزداد فقط أثناء التقدم في الحلقة، فإذا فشل هذا الحد مع أولي معيّن فسيفشل تلقائيًا مع كل أولي أكبر منه، ولهذا يمكن إيقاف الحلقة في تلك النقطة مباشرة.
هذا المثال الصغير يوضح الآلية نفسها بأعداد يسهل تتبعها. ابدأ بالعتبة \(c=3\)، فيكون الحاجز
$$3^3=27.$$
والأعداد التي تحقق \(\Omega(n)\ge 3\) مع \(n\le 27\) هي
$$8,\ 12,\ 16,\ 18,\ 20,\ 24,\ 27.$$
إذن
$$a_3(5)=20\le 27.$$
وبالتالي تنطبق لِمّة التضعيف مباشرة، فنحصل على
$$a_4(5)=40,\qquad a_5(5)=80.$$
إذًا العدد الخامس الذي يملك خمسة عوامل أولية على الأقل هو \(80\). وهذا المثال الصغير يبيّن بوضوح كيف تتكامل مرحلة التعداد مع مرحلة الرفع.
التنفيذات المكتوبة بلغة C++ وPython وJava تتبع المسار نفسه. أولًا تبني جدولًا للأعداد الأولية حتى حد ثابت، كما تخزن لوغاريتم كل عدد أولي لأن شرط التقليم يُفحَص مرارًا أثناء البحث العميق.
عند عتبة العمل الحالية \(c\)، يكون حد البحث هو \(3^c\). ثم يولّد البحث في العمق جميع الجداءات الممكنة للعوامل الأولية مع الحفاظ على ترتيب غير متناقص. وكلما وصل الجداء الحالي إلى امتلاك \(c\) عوامل أولية على الأقل، يُضاف إلى قائمة المرشحين. ومع ذلك يستمر النزول أعمق، لأن الأعداد ذات العوامل الأكثر من \(c\) تبقى صالحة ما دامت لا تتجاوز الحد نفسه.
الحد السفلي اللوغاريتمي من الخطوة 5 يقطع معظم الفروع في وقت مبكر جدًا. وفوق ذلك، إذا فشل اختيار أولي معيّن بوصفه العامل التالي من حالة ما، فإن التنفيذ لا يجرّب أوليات أكبر من نفس الحالة، لأن الحد الأدنى لن يتحسن بعد ذلك أبدًا.
بعد كل دورة بحث، يجري فحص عدد المرشحين. فإذا كان العدد أقل من مليون، تُزاد عتبة العمل بمقدار \(1\) ويُضرب حد البحث في \(3\). وعندما تصبح القائمة كبيرة بما يكفي، تُرتّب، ويؤخذ العنصر رقم مليون على أنه \(a_c(10^6)\)، ثم يُضرب في \(2\) عدد \(10^6-c\) مرة تحت الترديد \(123454321\). وهذه الخطوة الأخيرة مكافئة تمامًا للضرب في \(2^{10^6-c}\) تحت الترديد نفسه.
لنرمز بـ \(B\) إلى حد غربال الأعداد الأولية، وبـ \(V\) إلى عدد حالات الاستدعاء التراجعي التي جرى الوصول إليها عند آخر عتبة ناجحة، وبـ \(M\) إلى عدد المرشحين المجموعين عند تلك العتبة. بناء جدول الأعداد الأولية يكلف \(O(B\log\log B)\) زمنًا و\(O(B)\) ذاكرة. أما التعداد بالبحث العميق فيكلف \(O(V)\) زمنًا لأن كل حالة باقية بعد التقليم تُعالَج مرة واحدة فقط. وفرز قائمة المرشحين يكلف \(O(M\log M)\) زمنًا ويحتاج \(O(M)\) من الذاكرة للقائمة نفسها.
مرحلة الرفع النهائية تنفذ \(10^6-c\) عملية تضعيف معيارية، ولذلك تضيف \(O(10^6-c)\) زمنًا و\(O(1)\) ذاكرة إضافية. وعليه يكون الزمن الكلي
$$O(B\log\log B+V+M\log M+10^6-c),$$
أما الذاكرة الكلية فهي
$$O(B+M).$$
الجزء العملي الأثقل هو حجم شجرة البحث \(V\)، لكن الحد السفلي الوارد في الخطوة 5 يجعل هذا الحجم قابلاً للإدارة.