A tau number is a positive integer \(n\) for which the divisor count \(\tau(n)\) divides \(n\). With the fixed limit \(L=10^{16}\), the problem asks us to look at every divisor-count value \(k\) for which there exists at least one tau number \(n\le L\) satisfying \(\tau(n)=k\), and then define
$$m(k)=\min\{n\le L:\tau(n)=k,\ k\mid n\}.$$
The required answer is the sum of all existing values \(m(k)\). This includes the trivial case \(m(1)=1\), but the real difficulty is global: for every reachable divisor count \(k\), we must identify the smallest admissible integer rather than just produce one example.
The implementations do not scan integers. They search over prime-exponent patterns, because both the divisor function and the condition \(\tau(n)\mid n\) become rigid and testable in that language.
Write a candidate number as
$$n=\prod_{i=1}^{r} b_i^{e_i},\qquad b_1<b_2<\cdots<b_r,\qquad e_1\ge e_2\ge \cdots\ge e_r\ge 1.$$
The exponents are arranged in non-increasing order because, once the multiset of exponents is fixed, the smallest possible integer is obtained by placing larger exponents on smaller primes. In this representation, the divisor count is
$$\tau(n)=\prod_{i=1}^{r}(e_i+1)=:T.$$
So every exponent vector determines one divisor-count value \(T\). Different vectors can yield the same \(T\), which is why the search must keep the best number found for each divisor-count key.
For the same exponent vector, the smallest possible realization is obtained by using the first \(r\) primes:
$$n_{\min}(e_1,\dots,e_r)=\prod_{i=1}^{r} p_i^{e_i},$$
where \(p_i\) is the \(i\)-th prime. This number does not necessarily satisfy \(\tau(n)\mid n\); it is only the minimal number having that exponent multiset. But it is still crucial, because if even \(n_{\min}(e_1,\dots,e_r)>L\), then every other realization of the same vector is larger, so the entire branch can be discarded immediately.
This lower bound is exactly what the outer depth-first search maintains incrementally. It is the main invariant that makes the global enumeration finite.
Now factor the divisor count itself:
$$T=\prod_{j=1}^{t} q_j^{\nu_j},$$
with distinct primes \(q_j\). Since \(T\mid n\), every prime divisor \(q_j\) of \(T\) must also occur among the prime bases of \(n\), and its exponent inside \(n\) must be at least \(\nu_j\).
For a fixed exponent vector, this turns into an injective placement problem. Each mandatory prime \(q_j\) has to be assigned to a distinct exponent slot \(i\) satisfying
$$e_i\ge \nu_j.$$
If there are more mandatory primes than slots, so \(t>r\), the vector is impossible at once. Likewise, if the largest exponent is still smaller than one of the required values \(\nu_j\), no assignment can work.
Suppose a feasible assignment \(\sigma\) of the mandatory primes has been chosen. Then the resulting number has the form
$$N_\sigma=\left(\prod_{j=1}^{t} q_j^{e_{\sigma(j)}}\right)\left(\prod_{i\notin \operatorname{Im}(\sigma)} s_i^{e_i}\right),$$
where the remaining bases \(s_i\) are distinct primes not dividing \(T\). Once the mandatory primes are placed, the rest of the completion is forced greedily: fill the unused slots with the smallest available extra primes, matched from largest remaining exponent to smallest remaining exponent.
The justification is the swap inequality
$$a^x b^y\le a^y b^x\qquad(a<b,\ x\ge y),$$
which says that smaller primes belong on larger exponents. Therefore the only real branching for one vector is the placement of the mandatory primes. After that, the optimal completion is deterministic.
The best value attached to one exponent vector is therefore
$$M(e_1,\dots,e_r)=\min_{\sigma} N_\sigma,$$
and the desired minimum for a divisor-count value \(k\) is
$$m(k)=\min_{\prod_{i=1}^{r}(e_i+1)=k} M(e_1,\dots,e_r).$$
The outer DFS builds exponent vectors in non-increasing order. Starting from the smallest prime, each new exponent is constrained not to exceed the previous one, so every exponent multiset is visited exactly once in canonical form.
At each node, two quantities are already known:
$$\prod_{i=1}^{r} p_i^{e_i},\qquad T=\prod_{i=1}^{r}(e_i+1).$$
The first is the pruning bound just discussed; the second is the divisor-count value whose current minimum may be improved. Because many different exponent vectors can lead to the same \(T\), the algorithm stores the best candidate found so far for each \(T\). It also caches the prime factorization of \(T\), since the same divisor count appears repeatedly during the search.
Take \(k=12\). Since
$$12=2^2\cdot 3,$$
any tau number \(n\) with \(\tau(n)=12\) must contain the prime \(2\) with exponent at least \(2\), and it must also contain the prime \(3\).
The exponent vectors satisfying
$$\prod(e_i+1)=12$$
are
$$[11],\qquad [5,1],\qquad [3,2],\qquad [2,1,1].$$
The vector \([11]\) is impossible because one slot cannot host both mandatory primes. For \([5,1]\), the smallest feasible number is
$$2^5\cdot 3=96.$$
For \([3,2]\), the best placement gives
$$2^3\cdot 3^2=72.$$
For \([2,1,1]\), the mandatory primes use the exponents \(2\) and \(1\), and the remaining slot receives the smallest extra prime not dividing \(12\), namely \(5\), producing
$$2^2\cdot 3\cdot 5=60.$$
Hence
$$m(12)=60.$$
This is exactly the comparison performed by the algorithm for every reachable divisor-count value.
The C++, Python, and Java implementations first generate a sufficiently long prime table. Then they run an outer DFS over exponent vectors, maintaining the canonical product \(\prod p_i^{e_i}\) and the current divisor count \(T\) incrementally. Every visited node already represents a complete exponent pattern, so it is evaluated immediately as a candidate for its current \(T\).
Whenever a node is visited, the implementation looks up or computes the prime factorization of \(T\) and reuses that data through a cache. Capped multiplication is used throughout this stage so that any branch whose product would exceed \(L\) stops immediately without overflow.
For the current exponent vector, a second DFS assigns the mandatory primes from the factorization of \(T\) to eligible slots. Those mandatory primes are tried in descending prime order so that expensive branches fail earlier, which strengthens pruning. If two unused slots have the same exponent, exploring both would only repeat a symmetric case, so the implementation keeps just one representative.
Once all mandatory primes have been placed, the unused slots are filled greedily with the smallest primes that do not divide \(T\). The resulting number is compared against the best value already stored for that divisor-count key, and the map is updated only if an improvement has been found.
There is no simple closed form for the total running time, because the outer search size depends on the number of non-increasing exponent vectors whose canonical realization satisfies
$$\prod_{i=1}^{r} p_i^{e_i}\le L.$$
If we denote that set by \(V(L)\), then the outer DFS visits each vector in \(V(L)\) exactly once.
For one vector with \(r\) exponent slots and \(t\) distinct prime factors in \(T\), the inner search is a bounded backtracking procedure. Its naive worst case is exponential in \(t\), but in practice the tree is cut down sharply by the slot-feasibility test, the limit \(L\), the current best completion for the vector, the greedy tail fill, and the elimination of equal-exponent symmetries. Memory usage stays moderate: a prime table, a cache of divisor-count factorizations, recursion stacks, and the map of best values \(m(k)\).
Eine Tau-Zahl ist eine positive ganze Zahl \(n\), deren Teileranzahl \(\tau(n)\) die Zahl \(n\) selbst teilt. Fur die feste Schranke \(L=10^{16}\) betrachtet die Aufgabe jeden Wert \(k\), fur den es mindestens eine Tau-Zahl \(n\le L\) mit \(\tau(n)=k\) gibt, und definiert
$$m(k)=\min\{n\le L:\tau(n)=k,\ k\mid n\}.$$
Gesucht ist die Summe aller existierenden Minimalwerte \(m(k)\). Dazu gehort auch der triviale Fall \(m(1)=1\), aber die eigentliche Schwierigkeit ist global: Fur jeden erreichbaren Teileranzahlwert muss der kleinste zulassige Reprasentant gefunden werden.
Die Implementierungen durchsuchen nicht die ganzen Zahlen selbst. Sie arbeiten mit Exponentenvektoren der Primfaktorzerlegung, weil sowohl \(\tau(n)\) als auch die Bedingung \(\tau(n)\mid n\) in dieser Darstellung eine klare Struktur bekommen.
Schreibe einen Kandidaten als
$$n=\prod_{i=1}^{r} b_i^{e_i},\qquad b_1<b_2<\cdots<b_r,\qquad e_1\ge e_2\ge \cdots\ge e_r\ge 1.$$
Die Exponenten stehen in nicht steigender Reihenfolge, denn bei festem Exponentenmultiset wird die Zahl minimal, wenn grossere Exponenten auf kleinere Primzahlen gelegt werden. Dann gilt
$$\tau(n)=\prod_{i=1}^{r}(e_i+1)=:T.$$
Jeder Exponentenvektor bestimmt also einen Teileranzahlwert \(T\). Verschiedene Vektoren konnen denselben Wert \(T\) erzeugen; deshalb muss die Suche fur jeden solchen Schlussel den aktuell besten Kandidaten speichern.
Fur denselben Exponentenvektor erhalt man die kleinstmogliche Realisierung, indem man die ersten \(r\) Primzahlen verwendet:
$$n_{\min}(e_1,\dots,e_r)=\prod_{i=1}^{r} p_i^{e_i},$$
wobei \(p_i\) die \(i\)-te Primzahl ist. Diese Zahl muss die Tau-Bedingung nicht schon erfullen; sie ist lediglich die kleinste Zahl mit genau diesem Exponentenmultiset. Gerade deshalb ist sie als Schranke so wertvoll: Wenn schon \(n_{\min}(e_1,\dots,e_r)>L\) gilt, dann ist jede andere Realisierung noch grosser, und der gesamte Suchzweig kann sofort verworfen werden.
Genau diese Untergrenze wird in der ausseren Tiefensuche laufend mitgefuehrt. Sie ist die zentrale Invariante, die die Gesamtsuche endlich macht.
Nun zerlegen wir die Teileranzahl selbst:
$$T=\prod_{j=1}^{t} q_j^{\nu_j},$$
mit paarweise verschiedenen Primzahlen \(q_j\). Aus \(T\mid n\) folgt, dass jeder Primteiler \(q_j\) von \(T\) auch in \(n\) vorkommen muss, und zwar mit Exponent mindestens \(\nu_j\).
Fur einen festen Exponentenvektor wird daraus ein injektives Platzierungsproblem. Jede Pflichtprimzahl \(q_j\) muss in einen eigenen Slot \(i\) gelegt werden mit
$$e_i\ge \nu_j.$$
Falls es mehr Pflichtprimzahlen als Slots gibt, also \(t>r\), ist der Vektor sofort unmoglich. Ebenso scheitert er sofort, wenn selbst der groesste Exponent kleiner als ein benoetigtes \(\nu_j\) ist.
Angenommen, eine zulassige Zuordnung \(\sigma\) der Pflichtprimzahlen wurde gewahlt. Dann hat die entstehende Zahl die Form
$$N_\sigma=\left(\prod_{j=1}^{t} q_j^{e_{\sigma(j)}}\right)\left(\prod_{i\notin \operatorname{Im}(\sigma)} s_i^{e_i}\right),$$
wobei die restlichen Basen \(s_i\) verschiedene Primzahlen sind, die \(T\) nicht teilen. Sobald die Pflichtprimzahlen gesetzt sind, ist der Rest gierig bestimmt: Die freien Slots werden mit den kleinsten verfugbaren Zusatzprimzahlen gefuellt, zugeordnet von den groessten verbleibenden Exponenten zu den kleinsten.
Der Grund ist die Vertauschungsungleichung
$$a^x b^y\le a^y b^x\qquad(a<b,\ x\ge y),$$
also gehoeren kleinere Primzahlen zu groesseren Exponenten. Damit bleibt fur einen festen Vektor nur die Platzierung der Pflichtprimzahlen als echte Verzweigung. Danach ist die optimale Vervollstandigung eindeutig.
Das beste Ergebnis zu einem Exponentenvektor lautet daher
$$M(e_1,\dots,e_r)=\min_{\sigma} N_\sigma,$$
und fur einen festen Teileranzahlwert \(k\) gilt
$$m(k)=\min_{\prod_{i=1}^{r}(e_i+1)=k} M(e_1,\dots,e_r).$$
Die aussere DFS baut Exponentenvektoren in nicht steigender Reihenfolge auf. Beginnend mit der kleinsten Primzahl darf jeder neue Exponent den vorherigen nicht ubersteigen, sodass jedes Exponentenmultiset genau einmal in kanonischer Form besucht wird.
An jedem Knoten sind bereits zwei Grossen bekannt:
$$\prod_{i=1}^{r} p_i^{e_i},\qquad T=\prod_{i=1}^{r}(e_i+1).$$
Der erste Ausdruck ist die Abschneidegrenze, der zweite der Teileranzahlwert, dessen bestes Beispiel verbessert werden kann. Weil derselbe Wert \(T\) aus verschiedenen Vektoren entstehen kann, speichert der Algorithmus fur jeden Wert \(T\) den aktuell besten Kandidaten. Zudem wird die Primfaktorzerlegung von \(T\) gecacht, da dieselben Teileranzahlen im Suchbaum oft wiederkehren.
Betrachten wir \(k=12\). Wegen
$$12=2^2\cdot 3,$$
muss jede Tau-Zahl \(n\) mit \(\tau(n)=12\) die Primzahl \(2\) mindestens in der zweiten Potenz und ausserdem die Primzahl \(3\) enthalten.
Die Exponentenvektoren mit
$$\prod(e_i+1)=12$$
sind
$$[11],\qquad [5,1],\qquad [3,2],\qquad [2,1,1].$$
Der Vektor \([11]\) ist unmoglich, weil ein einzelner Slot nicht gleichzeitig beide Pflichtprimzahlen tragen kann. Fur \([5,1]\) ist die kleinste zulassige Zahl
$$2^5\cdot 3=96.$$
Fur \([3,2]\) liefert die beste Platzierung
$$2^3\cdot 3^2=72.$$
Bei \([2,1,1]\) besetzen die Pflichtprimzahlen die Exponenten \(2\) und \(1\), und der verbleibende Slot erhaelt die kleinste Zusatzprimzahl, die \(12\) nicht teilt, also \(5\). Damit entsteht
$$2^2\cdot 3\cdot 5=60.$$
Also gilt
$$m(12)=60.$$
Genau diesen Vergleich wiederholt der Algorithmus fur jeden erreichbaren Teileranzahlwert.
Die C++-, Python- und Java-Implementierungen erzeugen zuerst eine ausreichend lange Primzahlliste. Danach laeuft eine aussere DFS uber Exponentenvektoren, die sowohl das kanonische Produkt \(\prod p_i^{e_i}\) als auch den aktuellen Teileranzahlwert \(T\) inkrementell fortschreibt. Jeder besuchte Knoten ist bereits ein vollstandiges Exponentenmuster und wird deshalb sofort als Kandidat fur seinen aktuellen Wert \(T\) ausgewertet.
Beim Besuch eines Knotens wird die Primfaktorzerlegung von \(T\) nachgeschlagen oder neu berechnet und dann im Cache wiederverwendet. Ueberall wird mit gekappten Multiplikationen gearbeitet, damit Zweige, deren Produkt \(L\) ueberschreiten wuerde, sofort abbrechen und keine Ueberlaeufe entstehen.
Fur den aktuellen Exponentenvektor verteilt eine zweite DFS die Pflichtprimzahlen aus der Faktorisierung von \(T\) auf passende Slots. Diese Pflichtprimzahlen werden in absteigender Primzahlreihenfolge ausprobiert, damit teure Fehlzweige moeglichst frueh scheitern. Falls zwei freie Slots denselben Exponenten haben, waere ihre getrennte Exploration nur symmetrische Doppelarbeit; deshalb bleibt nur ein Reprasentant.
Sobald alle Pflichtprimzahlen gesetzt sind, werden die restlichen Slots gierig mit den kleinsten Primzahlen gefuellt, die \(T\) nicht teilen. Das resultierende Produkt wird nur dann gespeichert, wenn es den bisher besten Wert fur diesen Teileranzahl-Schluessel verbessert.
Fur die gesamte Laufzeit gibt es keine einfache geschlossene Formel, weil die aussere Suchgroesse davon abhaengt, wie viele nicht steigende Exponentenvektoren die kanonische Schranke
$$\prod_{i=1}^{r} p_i^{e_i}\le L$$
erfuellen. Bezeichne diese Menge mit \(V(L)\). Dann besucht die aussere DFS jeden Vektor aus \(V(L)\) genau einmal.
Fur einen Vektor mit \(r\) Slots und \(t\) verschiedenen Primfaktoren in \(T\) ist die innere Suche ein begrenztes Backtracking-Verfahren. Im naiven Worst Case ist sie exponentiell in \(t\), praktisch wird der Baum aber stark durch Slot-Tests, die Schranke \(L\), den aktuellen Bestwert, die gierige Restfuellung und die Elimination gleicher Exponenten reduziert. Der Speicherbedarf bleibt moderat: Primzahlliste, Faktorisierungs-Cache, Rekursionsstapel und die Abbildung der besten Werte \(m(k)\).
Bir tau sayısı, bölen sayısı \(\tau(n)\) sayının kendisini bölen pozitif bir tam sayı \(n\)'dir. Sabit üst sınır \(L=10^{16}\) için problem, \(\tau(n)=k\) ve \(k\mid n\) koşullarını sağlayan en az bir tau sayısı \(n\le L\) bulunan her bölen-sayısı değeri \(k\) için
$$m(k)=\min\{n\le L:\tau(n)=k,\ k\mid n\}$$
tanımını yapar ve bu mevcut tüm minimumların toplamını ister. Buna tabii ki \(m(1)=1\) de dahildir; fakat asıl güçlük tek bir örnek bulmak değil, ulaşılabilen her bölen-sayısı değeri için en küçük geçerli sayıyı bulmaktır.
Uygulamalar sayıları tek tek taramaz. Bunun yerine asal üs vektörleri üzerinde çalışırlar; çünkü hem \(\tau(n)\) hem de \(\tau(n)\mid n\) koşulu bu temsil altında net bir yapıya kavuşur.
Bir adayı şu biçimde yazalım:
$$n=\prod_{i=1}^{r} b_i^{e_i},\qquad b_1<b_2<\cdots<b_r,\qquad e_1\ge e_2\ge \cdots\ge e_r\ge 1.$$
Üsler azalmayan değil, azalan sırada tutulur; çünkü aynı üs çokluğu sabitken daha büyük üsleri daha küçük asallara vermek sayıyı en küçük yapar. Bu gösterimde bölen fonksiyonu
$$\tau(n)=\prod_{i=1}^{r}(e_i+1)=:T$$
olur. Dolayısıyla her üs vektörü bir bölen-sayısı değeri \(T\) üretir. Farklı vektörler aynı \(T\)'yi verebildiği için arama, her \(T\) için şimdiye kadarki en iyi adayı saklamak zorundadır.
Aynı üs vektörünün mümkün olan en küçük gerçekleşmesi, ilk \(r\) asal kullanılarak elde edilir:
$$n_{\min}(e_1,\dots,e_r)=\prod_{i=1}^{r} p_i^{e_i},$$
burada \(p_i\), \(i\). asaldır. Bu sayı otomatik olarak tau koşulunu sağlamaz; sadece aynı üs çokluğuna sahip sayılar arasındaki en küçük değerdir. Ama tam da bu yüzden güçlü bir budama sınırıdır: Eğer \(n_{\min}(e_1,\dots,e_r)>L\) ise, aynı vektörün başka hiçbir gerçekleşmesi limite sığamaz ve ilgili arama dalı anında kesilir.
Dış DFS tam olarak bu alt sınırı artımlı biçimde taşır. Aramanın sonlu kalmasını sağlayan temel değişmez budur.
Şimdi bölen sayısının kendisini asal çarpanlara ayıralım:
$$T=\prod_{j=1}^{t} q_j^{\nu_j}.$$
Buradaki \(q_j\)'ler farklı asallardır. \(T\mid n\) olduğundan, \(T\)'yi bölen her asal \(q_j\), \(n\)'nin asal tabanları arasında da bulunmalı ve \(n\) içindeki üssü en az \(\nu_j\) olmalıdır.
Sabit bir üs vektörü için bu, birebir bir yerleştirme problemine dönüşür. Her zorunlu asal \(q_j\),
$$e_i\ge \nu_j$$
sağlayan farklı bir üs yuvasına yerleştirilmelidir. Eğer zorunlu asalların sayısı yuva sayısını aşıyorsa, yani \(t>r\), vektör hemen imkansızdır. Benzer şekilde, en büyük üs bile gereken bir \(\nu_j\)'yi karşılamıyorsa hiçbir atama işe yaramaz.
Zorunlu asallar için uygun bir \(\sigma\) yerleşimi seçildiğini varsayalım. O zaman ortaya çıkan sayı
$$N_\sigma=\left(\prod_{j=1}^{t} q_j^{e_{\sigma(j)}}\right)\left(\prod_{i\notin \operatorname{Im}(\sigma)} s_i^{e_i}\right)$$
şeklindedir; burada kalan tabanlar \(s_i\), \(T\)'yi bölmeyen farklı asallardır. Zorunlu asallar yerleştirildikten sonra geri kalan tamamlamanın en iyisi açgözlüdür: boş yuvalar, kullanılabilir en küçük ek asallarla ve büyük kalan üslerden küçük kalan üslere doğru doldurulur.
Bunun nedeni basit takas eşitsizliğidir:
$$a^x b^y\le a^y b^x\qquad(a<b,\ x\ge y).$$
Yani daha küçük asallar daha büyük üslere gitmelidir. Böylece sabit bir vektörde gerçek dallanma yalnızca zorunlu asalların hangi uygun yuvalara yerleşeceğidir; sonrası tek bir en iyi açgözlü tamamlama verir.
Bu vektöre ait en iyi değer
$$M(e_1,\dots,e_r)=\min_{\sigma} N_\sigma,$$
ve sabit bir bölen-sayısı değeri için aradığımız minimum
$$m(k)=\min_{\prod_{i=1}^{r}(e_i+1)=k} M(e_1,\dots,e_r)$$
olur.
Dış DFS üs vektörlerini azalan sırada kurar. En küçük asaldan başlanır ve sonraki üs, öncekini aşamaz; böylece her üs çokluğu kanonik biçimde tam bir kez ziyaret edilir.
Bu DFS'in her düğümünde iki nicelik zaten bellidir:
$$\prod_{i=1}^{r} p_i^{e_i},\qquad T=\prod_{i=1}^{r}(e_i+1).$$
İlk çarpım budama sınırıdır; ikinci ifade ise minimumunu iyileştirmeye çalıştığımız bölen-sayısı değeridir. Farklı üs vektörleri aynı \(T\)'yi üretebildiği için algoritma her \(T\) anahtarı için en iyi sayıyı saklar. Ayrıca aynı bölen-sayısı değerleri sık sık tekrarlandığından, \(T\)'nin asal çarpanlara ayrımı da önbellekte tutulur.
\(k=12\) için
$$12=2^2\cdot 3$$
olduğundan, \(\tau(n)=12\) olan herhangi bir tau sayısı en az ikinci kuvvette bir \(2\) ve ayrıca bir \(3\) içermek zorundadır.
Şu koşulu sağlayan üs vektörleri
$$\prod(e_i+1)=12$$
şunlardır:
$$[11],\qquad [5,1],\qquad [3,2],\qquad [2,1,1].$$
\([11]\) vektörü imkansızdır; çünkü tek bir yuva hem \(2\)'yi hem \(3\)'ü taşıyamaz. \([5,1]\) için en küçük uygun sayı
$$2^5\cdot 3=96$$
olur. \([3,2]\) için en iyi yerleşim
$$2^3\cdot 3^2=72$$
verir. \([2,1,1]\) için zorunlu asallar üsleri \(2\) ve \(1\) olan yuvaları doldurur; kalan yuva da \(12\)'yi bölmeyen en küçük ek asal olan \(5\)'i alır:
$$2^2\cdot 3\cdot 5=60.$$
Dolayısıyla
$$m(12)=60$$
elde edilir. Algoritma her ulaşılabilir bölen-sayısı değeri için tam olarak bu tür karşılaştırmalar yapar.
C++, Python ve Java uygulamaları önce yeterince uzun bir asal tablosu üretir. Sonra dış DFS, üs vektörleri üzerinde gezerken hem kanonik çarpımı \(\prod p_i^{e_i}\) hem de güncel bölen sayısını \(T\) artımlı olarak taşır. Ziyaret edilen her düğüm zaten tam bir üs deseni olduğu için, kendi \(T\) değeri adına hemen aday olarak değerlendirilir.
Her düğümde \(T\)'nin asal çarpanlara ayrımı ya önbellekten alınır ya da ilk kez hesaplanır. Bu aşamanın tamamında taşmalı çarpım yerine sınır aşıldığında durduran güvenli çarpımlar kullanılır; böylece \(L\)'yi aşan tüm dallar anında sonlanır.
Mevcut üs vektörü için ikinci bir DFS, \(T\)'nin asal ayrımından gelen zorunlu asalları uygun yuvalara yerleştirir. Bu zorunlu asallar büyük asaldan küçüğe doğru denenir; böylece pahalı başarısız dallar daha erken görünür ve budama güçlenir. Eğer iki boş yuvanın üssü aynıysa, ikisini ayrı ayrı denemek sadece simetrik tekrar üretir; bu yüzden yalnızca bir temsilci tutulur.
Tüm zorunlu asallar yerleştirildikten sonra, boş yuvalar \(T\)'yi bölmeyen en küçük asallarla açgözlü biçimde doldurulur. Elde edilen sayı, ilgili bölen-sayısı anahtarı için saklanan en iyi değeri gerçekten iyileştiriyorsa kayda geçer.
Toplam çalışma süresi için basit bir kapalı form yoktur; çünkü dış aramanın büyüklüğü, kanonik sınırı
$$\prod_{i=1}^{r} p_i^{e_i}\le L$$
sağlayan azalan üs vektörlerinin sayısına bağlıdır. Bu kümeyi \(V(L)\) ile gösterirsek, dış DFS bu kümedeki her vektörü tam bir kez ziyaret eder.
\(r\) tane üs yuvası ve \(T\) içinde \(t\) farklı asal çarpanı olan bir vektör için iç arama sınırlı bir backtracking sürecidir. Naif en kötü durumda maliyet \(t\)'de üstel olabilir; fakat pratikte yuva uygunluk testi, \(L\) sınırı, mevcut en iyi tamamlama, açgözlü kuyruk doldurma ve eşit üs simetrilerinin atılması arama ağacını ciddi biçimde küçültür. Bellek kullanımı ılımlıdır: bir asal tablosu, bölen-sayısı ayrımı önbelleği, özyineleme yığınları ve en iyi \(m(k)\) değerlerini tutan harita yeterlidir.
Un numero tau es un entero positivo \(n\) tal que su numero de divisores \(\tau(n)\) divide a \(n\). Con la cota fija \(L=10^{16}\), el problema toma cada valor \(k\) para el que existe al menos un numero tau \(n\le L\) con \(\tau(n)=k\), y define
$$m(k)=\min\{n\le L:\tau(n)=k,\ k\mid n\}.$$
La respuesta buscada es la suma de todos los minimos existentes \(m(k)\). Esto incluye el caso trivial \(m(1)=1\), pero la dificultad real es global: para cada cantidad de divisores alcanzable hay que encontrar el representante valido mas pequeno.
Las implementaciones no recorren enteros uno por uno. Trabajan con vectores de exponentes primos, porque en esa representacion tanto \(\tau(n)\) como la condicion \(\tau(n)\mid n\) quedan descritas por reglas muy rigidas.
Escribimos un candidato como
$$n=\prod_{i=1}^{r} b_i^{e_i},\qquad b_1<b_2<\cdots<b_r,\qquad e_1\ge e_2\ge \cdots\ge e_r\ge 1.$$
Los exponentes se ordenan de mayor a menor porque, con el mismo multiconjunto de exponentes, el numero mas pequeno aparece cuando los exponentes grandes se colocan sobre los primos pequenos. Entonces
$$\tau(n)=\prod_{i=1}^{r}(e_i+1)=:T.$$
Asi, cada vector \((e_1,\dots,e_r)\) produce un valor de divisores \(T\). Distintos vectores pueden llevar al mismo \(T\), por lo que la busqueda debe conservar el mejor candidato encontrado para cada clave de numero de divisores.
Para un vector dado, la realizacion minima se obtiene usando los primeros \(r\) primos:
$$n_{\min}(e_1,\dots,e_r)=\prod_{i=1}^{r} p_i^{e_i},$$
donde \(p_i\) es el \(i\)-esimo primo. Este producto no tiene por que satisfacer ya la condicion tau; solo es el menor entero con ese multiconjunto de exponentes. Precisamente por eso es una excelente cota: si ya ocurre que \(n_{\min}(e_1,\dots,e_r)>L\), ninguna otra realizacion del mismo vector puede entrar en el limite, y toda la rama se poda de inmediato.
La DFS exterior mantiene exactamente esta cota de forma incremental. Es la invariante central que hace finita la enumeracion global.
Ahora factorizamos el propio numero de divisores:
$$T=\prod_{j=1}^{t} q_j^{\nu_j}.$$
Los \(q_j\) son primos distintos. Como \(T\) debe dividir a \(n\), cada primo divisor \(q_j\) de \(T\) debe aparecer tambien entre las bases primas de \(n\), con exponente al menos \(\nu_j\).
Para un vector fijo, esto se convierte en un problema de asignacion inyectiva. Cada primo obligatorio \(q_j\) debe colocarse en una ranura distinta \(i\) que satisfaga
$$e_i\ge \nu_j.$$
Si hay mas primos obligatorios que ranuras, es decir, si \(t>r\), el vector es imposible al instante. Del mismo modo, si ni siquiera el mayor exponente alcanza algun \(\nu_j\) requerido, ninguna asignacion puede funcionar.
Supongamos que ya elegimos una asignacion factible \(\sigma\) de los primos obligatorios. Entonces el numero resultante tiene la forma
$$N_\sigma=\left(\prod_{j=1}^{t} q_j^{e_{\sigma(j)}}\right)\left(\prod_{i\notin \operatorname{Im}(\sigma)} s_i^{e_i}\right),$$
donde las bases restantes \(s_i\) son primos distintos que no dividen a \(T\). Una vez fijados los primos obligatorios, el resto de la completacion es voraz: las ranuras libres se llenan con los menores primos disponibles, emparejando los menores primos con los mayores exponentes restantes.
La razon es la desigualdad elemental
$$a^x b^y\le a^y b^x\qquad(a<b,\ x\ge y),$$
que muestra que los primos pequenos deben ir con los exponentes grandes. Por tanto, para un vector fijo la unica parte realmente no trivial es decidir donde colocar los primos obligatorios; despues de eso, la mejor terminacion queda forzada.
El mejor valor asociado a un vector es
$$M(e_1,\dots,e_r)=\min_{\sigma} N_\sigma,$$
y el minimo buscado para un valor de divisores \(k\) satisface
$$m(k)=\min_{\prod_{i=1}^{r}(e_i+1)=k} M(e_1,\dots,e_r).$$
La DFS exterior construye vectores de exponentes en orden no creciente. Empezando por el primo mas pequeno, el siguiente exponente nunca puede exceder al anterior, asi que cada multiconjunto de exponentes se visita exactamente una vez en forma canonica.
En cada nodo ya se conocen dos cantidades:
$$\prod_{i=1}^{r} p_i^{e_i},\qquad T=\prod_{i=1}^{r}(e_i+1).$$
La primera es la cota de poda; la segunda es el numero de divisores cuyo mejor representante intentamos mejorar. Como distintos vectores pueden producir el mismo \(T\), el algoritmo guarda el mejor candidato por clave \(T\). Ademas, la factorizacion prima de cada \(T\) se almacena en cache, porque los mismos valores reaparecen muchas veces a lo largo del recorrido.
Tomemos \(k=12\). Como
$$12=2^2\cdot 3,$$
todo numero tau \(n\) con \(\tau(n)=12\) debe contener al primo \(2\) con exponente al menos \(2\), y tambien debe contener al primo \(3\).
Los vectores de exponentes que satisfacen
$$\prod(e_i+1)=12$$
son
$$[11],\qquad [5,1],\qquad [3,2],\qquad [2,1,1].$$
El vector \([11]\) es imposible porque una sola ranura no puede alojar a ambos primos obligatorios. Para \([5,1]\), el menor valor factible es
$$2^5\cdot 3=96.$$
Para \([3,2]\), la mejor colocacion produce
$$2^3\cdot 3^2=72.$$
Para \([2,1,1]\), los primos obligatorios ocupan los exponentes \(2\) y \(1\), y la ranura restante recibe el menor primo extra que no divide a \(12\), es decir \(5\):
$$2^2\cdot 3\cdot 5=60.$$
Por consiguiente,
$$m(12)=60.$$
Este es exactamente el tipo de comparacion que el algoritmo repite para cada valor de divisores alcanzable.
Las implementaciones en C++, Python y Java empiezan generando una tabla suficiente de primos. Luego ejecutan una DFS exterior sobre vectores de exponentes, manteniendo de forma incremental tanto el producto canonico \(\prod p_i^{e_i}\) como el valor actual de divisores \(T\). Cada nodo visitado ya representa un patron completo de exponentes, de modo que se evalua inmediatamente como candidato para su \(T\).
Siempre que se visita un nodo, la implementacion recupera o calcula la factorizacion prima de \(T\) y la reutiliza desde una cache. Ademas, las multiplicaciones se hacen con corte superior: en cuanto un producto rebasaria \(L\), esa rama se detiene sin riesgo de desbordamiento.
Para el vector actual, una segunda DFS asigna los primos obligatorios de la factorizacion de \(T\) a ranuras compatibles. Esos primos se prueban en orden decreciente para que las ramas costosas fallen antes y la poda sea mas fuerte. Si dos ranuras libres tienen el mismo exponente, explorarlas por separado solo repetiria un caso simetrico, por lo que se conserva un unico representante.
Una vez colocados todos los primos obligatorios, las ranuras restantes se rellenan vorazmente con los menores primos que no dividen a \(T\). El numero resultante solo se guarda si mejora el minimo ya conocido para esa clave de numero de divisores.
No hay una formula cerrada simple para el tiempo total, porque el tamano de la busqueda exterior depende de cuantos vectores de exponentes no crecientes satisfacen la cota canonica
$$\prod_{i=1}^{r} p_i^{e_i}\le L.$$
Si llamamos \(V(L)\) a ese conjunto, la DFS exterior visita cada vector de \(V(L)\) exactamente una vez.
Para un vector con \(r\) ranuras de exponentes y \(t\) factores primos distintos en \(T\), la busqueda interior es un proceso de backtracking acotado. Su peor caso ingenuo es exponencial en \(t\), pero en la practica el arbol se reduce mucho gracias a la prueba de factibilidad de ranuras, al limite \(L\), a la mejor completacion conocida, al relleno voraz del resto y a la eliminacion de simetrias cuando hay exponentes iguales. La memoria necesaria es moderada: una tabla de primos, una cache de factorizaciones, las pilas de recursion y el mapa que guarda los mejores valores \(m(k)\).
Tau 数指满足 \(\tau(n)\mid n\) 的正整数 \(n\)，其中 \(\tau(n)\) 是 \(n\) 的约数个数。题目固定上界 \(L=10^{16}\)，并对每一个满足“存在某个 \(n\le L\)，使得 \(\tau(n)=k\) 且 \(k\mid n\)”的值 \(k\) 定义
$$m(k)=\min\{n\le L:\tau(n)=k,\ k\mid n\}.$$
最终要求把所有存在的最小值 \(m(k)\) 加总。这里当然包括平凡项 \(m(1)=1\)，但真正困难的地方在于：不是找到某一个 Tau 数就够了，而是要对每一个可实现的约数个数 \(k\) 都找出最小的合法代表。
三份实现都没有直接枚举整数 \(n\)。它们枚举的是素因子指数向量，因为在这种表示下，\(\tau(n)\) 的结构、\(\tau(n)\mid n\) 的约束，以及所有有效的剪枝条件都会变得清晰而且可操作。
把候选数写成
$$n=\prod_{i=1}^{r} b_i^{e_i},\qquad b_1<b_2<\cdots<b_r,\qquad e_1\ge e_2\ge \cdots\ge e_r\ge 1.$$
这里把指数按非增序排列，是因为在指数多重集固定时，把较大的指数分配给较小的素数，得到的整数总是最小的。于是约数函数立刻变成
$$\tau(n)=\prod_{i=1}^{r}(e_i+1)=:T.$$
因此每个指数向量 \((e_1,\dots,e_r)\) 都对应一个约数个数值 \(T\)。不同的指数向量完全可能产生同一个 \(T\)，所以算法不能只按向量工作，还必须为每一个约数个数键保存当前最优的数值。
对同一个指数向量，最小的具体实现方式是使用前 \(r\) 个素数：
$$n_{\min}(e_1,\dots,e_r)=\prod_{i=1}^{r} p_i^{e_i},$$
其中 \(p_i\) 表示第 \(i\) 个素数。这个乘积并不一定已经满足 Tau 条件；它只是拥有同样指数多重集的整数里最小的那个。正因为如此，它成为极强的下界：如果连这个标准值都已经超过 \(L\)，那么任何采用相同指数向量的其他实现只会更大，这整条搜索分支就可以直接丢弃。
外层 DFS 始终维护的正是这个标准乘积。它是整个搜索过程最关键的一个不变量，也是全局枚举能够终止的原因。
接着把约数个数 \(T\) 自身做素因子分解：
$$T=\prod_{j=1}^{t} q_j^{\nu_j}.$$
这里的 \(q_j\) 彼此不同。由于 \(T\) 必须整除 \(n\)，所以每个整除 \(T\) 的素数 \(q_j\) 也必须出现在 \(n\) 的素因子分解中，而且它在 \(n\) 里的指数至少要达到 \(\nu_j\)。
对固定的指数向量来说，这就变成了一个单射放置问题：每一个“必选素数” \(q_j\) 都必须占据一个不同的指数槽 \(i\)，并满足
$$e_i\ge \nu_j.$$
如果必选素数的种类数多于槽位数，即 \(t>r\)，那么这个向量立刻不可能。即使槽位数量足够，只要最大的指数仍然小于某个所需的 \(\nu_j\)，同样没有任何可行放置方式。
假设我们已经选定了一个可行放置 \(\sigma\)，把这些必选素数放入相应的指数槽中。于是得到的数可以写成
$$N_\sigma=\left(\prod_{j=1}^{t} q_j^{e_{\sigma(j)}}\right)\left(\prod_{i\notin \operatorname{Im}(\sigma)} s_i^{e_i}\right),$$
其中剩余的底数 \(s_i\) 是彼此不同、且不整除 \(T\) 的素数。一旦必选素数的位置确定，剩余部分的最优补全就不再需要回溯，而是贪心唯一确定：把最小的可用附加素数分配给最大的剩余指数。
这一点来自交换不等式
$$a^x b^y\le a^y b^x\qquad(a<b,\ x\ge y),$$
它说明较小的素数应该和较大的指数配对。也就是说，对一个固定指数向量而言，真正需要搜索的只有“必选素数放在哪些合法槽位里”；一旦这部分定下，尾部补全就是确定的最优解。
因此，一个指数向量对应的最优值是
$$M(e_1,\dots,e_r)=\min_{\sigma} N_\sigma,$$
而某个约数个数 \(k\) 的全局最优值满足
$$m(k)=\min_{\prod_{i=1}^{r}(e_i+1)=k} M(e_1,\dots,e_r).$$
外层搜索按深度优先方式构造指数向量，并强制后一个指数不超过前一个指数。这样做的结果是：每一种指数多重集都只会以一种标准形式出现一次，不会漏，也不会重。
在 DFS 的任意一个节点，下面两项都已经完全确定：
$$\prod_{i=1}^{r} p_i^{e_i},\qquad T=\prod_{i=1}^{r}(e_i+1).$$
前者是用于剪枝的标准下界，后者是当前这个指数模式对应的约数个数值。由于很多不同的指数向量会汇聚到同一个 \(T\)，算法会为每一个 \(T\) 单独维护当前最好的候选值。同时，\(T\) 的素因子分解会被缓存，因为同样的约数个数在搜索树里会反复出现。
来看 \(k=12\)。因为
$$12=2^2\cdot 3,$$
所以任何满足 \(\tau(n)=12\) 的 Tau 数，都必须至少含有一个指数不小于 \(2\) 的素因子 \(2\)，并且还必须含有素因子 \(3\)。
满足
$$\prod(e_i+1)=12$$
的指数向量是
$$[11],\qquad [5,1],\qquad [3,2],\qquad [2,1,1].$$
\([11]\) 不可能，因为只有一个槽位，不可能同时容纳必选素数 \(2\) 和 \(3\)。对 \([5,1]\)，最小可行值是
$$2^5\cdot 3=96.$$
对 \([3,2]\)，最佳放置得到
$$2^3\cdot 3^2=72.$$
对 \([2,1,1]\)，必选素数 \(2\) 和 \(3\) 占据指数 \(2\) 与 \(1\) 的两个槽位，剩下那个指数 \(1\) 的槽位就放入最小的不整除 \(12\) 的附加素数 \(5\)，于是得到
$$2^2\cdot 3\cdot 5=60.$$
因此
$$m(12)=60.$$
算法对每一个可实现的约数个数都做同样的比较；这不是特例，而是整个方法的缩影。
C++、Python 和 Java 实现都会先生成足够长的素数表。然后外层 DFS 逐步构造指数向量，同时维护标准乘积 \(\prod p_i^{e_i}\) 和当前约数个数 \(T\) 的增量更新。每个被访问到的节点本身就对应一个完整的指数模式，因此会立刻被评估为其当前 \(T\) 的候选值。
每次访问节点时，程序都会读取或计算 \(T\) 的素因子分解，并把结果放进缓存以便复用。整个过程中还会使用“带上界的乘法”：一旦部分乘积将要超过 \(L\)，该分支就立即终止，从而同时完成剪枝和防溢出。
对当前指数向量，第二层 DFS 负责把 \(T\) 的必选素因子放进所有合法槽位。实现会按素数从大到小的顺序尝试这些必选素数，因为这样较差的分支通常更早暴露，剪枝效果更好。如果两个未使用槽位的指数相同，那么分别探索它们只会产生对称重复，因此只保留一个代表即可。
当所有必选素数都放好以后，剩余槽位就用不整除 \(T\) 的最小素数按贪心方式补齐。得到的完整数值只有在确实优于该约数个数键已有的最优值时才会写回。
总运行时间没有简单的闭式公式，因为外层搜索的规模取决于满足标准约束
$$\prod_{i=1}^{r} p_i^{e_i}\le L$$
的非增指数向量到底有多少个。把这批向量记作 \(V(L)\)，那么外层 DFS 恰好访问 \(V(L)\) 中的每个向量一次。
对于一个拥有 \(r\) 个指数槽、且其 \(T\) 含有 \(t\) 个不同素因子的向量，内层放置搜索是一个有界的回溯过程。朴素最坏情况下，它在 \(t\) 上是指数级的；但在实际运行里，槽位可行性测试、上界 \(L\)、当前最优补全、贪心尾部填充以及相同指数槽的对称消除，都会把搜索树大幅压缩。内存占用比较温和：主要是素数表、约数个数分解缓存、递归栈，以及保存各个最优 \(m(k)\) 的映射。
Tau-число — это положительное целое \(n\), для которого число делителей \(\tau(n)\) делит само \(n\). При фиксированной границе \(L=10^{16}\) задача рассматривает каждое значение \(k\), для которого существует хотя бы одно tau-число \(n\le L\) с \(\tau(n)=k\), и задает минимум
$$m(k)=\min\{n\le L:\tau(n)=k,\ k\mid n\}.$$
Нужно просуммировать все существующие значения \(m(k)\). Сюда, конечно, входит и тривиальный случай \(m(1)=1\), но основная трудность гораздо шире: для каждого достижимого значения числа делителей надо найти наименьший допустимый представитель.
Реализации не перебирают числа \(n\) напрямую. Они работают с векторами показателей в разложении на простые множители, потому что и \(\tau(n)\), и условие \(\tau(n)\mid n\), и нужные отсечения в этой записи становятся очень прозрачными.
Запишем кандидата в виде
$$n=\prod_{i=1}^{r} b_i^{e_i},\qquad b_1<b_2<\cdots<b_r,\qquad e_1\ge e_2\ge \cdots\ge e_r\ge 1.$$
Показатели идут по невозрастанию, потому что при фиксированном мультимножестве показателей минимальное число получается тогда, когда большие показатели ставятся при меньших простых. Тогда
$$\tau(n)=\prod_{i=1}^{r}(e_i+1)=:T.$$
Значит, каждый вектор \((e_1,\dots,e_r)\) определяет некоторое значение числа делителей \(T\). При этом разные векторы могут давать один и тот же \(T\), поэтому поиск обязан хранить наилучшее найденное число отдельно для каждого такого ключа.
Для данного вектора показателей наименьшая конкретная реализация получается, если взять первые \(r\) простых:
$$n_{\min}(e_1,\dots,e_r)=\prod_{i=1}^{r} p_i^{e_i},$$
где \(p_i\) — \(i\)-е простое. Это произведение само по себе не обязано уже быть tau-числом; оно лишь минимально среди чисел с тем же набором показателей. Но именно поэтому оно так полезно: если даже \(n_{\min}(e_1,\dots,e_r)>L\), то любая другая реализация того же вектора будет еще больше, и вся ветвь поиска может быть немедленно отсечена.
Именно эту величину внешняя DFS поддерживает пошагово. Это главный инвариант всей процедуры.
Теперь разложим само число делителей:
$$T=\prod_{j=1}^{t} q_j^{\nu_j}.$$
Здесь простые \(q_j\) попарно различны. Из условия \(T\mid n\) следует, что каждый простой делитель \(q_j\) числа \(T\) обязан входить и в разложение самого \(n\), причем с показателем не меньше \(\nu_j\).
Для фиксированного вектора это превращается в инъективную задачу размещения. Каждый обязательный простой \(q_j\) должен занять отдельный слот \(i\), удовлетворяющий
$$e_i\ge \nu_j.$$
Если обязательных простых больше, чем слотов, то есть \(t>r\), такой вектор невозможен сразу. То же верно, если даже максимальный показатель меньше некоторого требуемого \(\nu_j\).
Пусть уже выбрано допустимое размещение \(\sigma\) обязательных простых. Тогда получающееся число имеет вид
$$N_\sigma=\left(\prod_{j=1}^{t} q_j^{e_{\sigma(j)}}\right)\left(\prod_{i\notin \operatorname{Im}(\sigma)} s_i^{e_i}\right),$$
где оставшиеся основания \(s_i\) — различные простые, не делящие \(T\). После того как обязательные простые расставлены, хвост уже оптимален жадно: свободные слоты надо заполнить наименьшими доступными дополнительными простыми, сопоставляя меньшие простые большим оставшимся показателям.
Это следует из неравенства перестановки
$$a^x b^y\le a^y b^x\qquad(a<b,\ x\ge y),$$
которое показывает, что меньшие простые нужно ставить при больших показателях. Следовательно, для одного вектора вся настоящая развилка состоит лишь в том, куда именно поставить обязательные простые; после этого наилучшее продолжение уже однозначно.
Минимум, связанный с одним вектором, равен
$$M(e_1,\dots,e_r)=\min_{\sigma} N_\sigma,$$
а искомый минимум для значения числа делителей \(k\) имеет вид
$$m(k)=\min_{\prod_{i=1}^{r}(e_i+1)=k} M(e_1,\dots,e_r).$$
Внешняя DFS строит векторы показателей по невозрастанию. Начиная с наименьшего простого, каждый новый показатель не может превосходить предыдущий, поэтому каждое мультимножество показателей посещается ровно один раз в канонической форме.
В каждом узле уже известны две величины:
$$\prod_{i=1}^{r} p_i^{e_i},\qquad T=\prod_{i=1}^{r}(e_i+1).$$
Первое выражение — это граница для отсечения, второе — текущее значение числа делителей. Поскольку разные векторы могут давать один и тот же \(T\), алгоритм хранит лучший найденный результат отдельно для каждого такого \(T\). Кроме того, факторизация числа \(T\) кешируется, потому что одни и те же значения встречаются в поиске много раз.
Рассмотрим \(k=12\). Так как
$$12=2^2\cdot 3,$$
любое tau-число \(n\) с \(\tau(n)=12\) обязано содержать простой множитель \(2\) с показателем не меньше \(2\), а также простой множитель \(3\).
Векторы показателей, удовлетворяющие условию
$$\prod(e_i+1)=12,$$
таковы:
$$[11],\qquad [5,1],\qquad [3,2],\qquad [2,1,1].$$
Вектор \([11]\) невозможен, потому что один слот не может одновременно вместить оба обязательных простых. Для \([5,1]\) наименьшее допустимое число равно
$$2^5\cdot 3=96.$$
Для \([3,2]\) лучшая расстановка дает
$$2^3\cdot 3^2=72.$$
Для \([2,1,1]\) обязательные простые занимают показатели \(2\) и \(1\), а оставшийся слот получает наименьший дополнительный простой, не делящий \(12\), то есть \(5\):
$$2^2\cdot 3\cdot 5=60.$$
Следовательно,
$$m(12)=60.$$
Именно такой тип сравнения алгоритм выполняет для каждого достижимого значения числа делителей.
Реализации на C++, Python и Java сначала строят достаточно длинную таблицу простых чисел. Затем запускается внешняя DFS по векторам показателей, которая инкрементально поддерживает и канонический продукт \(\prod p_i^{e_i}\), и текущее значение числа делителей \(T\). Каждый посещенный узел уже соответствует полному шаблону показателей, поэтому он сразу оценивается как кандидат для своего значения \(T\).
При посещении узла программа получает или вычисляет факторизацию \(T\) и затем переиспользует ее из кеша. Во всех умножениях используется ограничение сверху: как только произведение должно превысить \(L\), ветвь немедленно обрывается, что одновременно дает и отсечение, и защиту от переполнения.
Для текущего вектора вторая DFS размещает обязательные простые из факторизации \(T\) по подходящим слотам. Эти простые пробуются в порядке убывания, чтобы неудачные ветви проявлялись раньше и сильнее работало отсечение. Если два свободных слота имеют одинаковый показатель, их раздельный перебор дал бы только симметрические дубликаты, поэтому сохраняется лишь один представитель.
Когда обязательные простые уже расставлены, оставшиеся слоты жадно заполняются наименьшими простыми, не делящими \(T\). Получившееся число записывается только в том случае, если оно действительно улучшает лучший известный результат для этого значения числа делителей.
Простой замкнутой формулы для полного времени работы нет, потому что размер внешнего поиска определяется количеством векторов показателей, удовлетворяющих канонической границе
$$\prod_{i=1}^{r} p_i^{e_i}\le L.$$
Обозначим это множество через \(V(L)\). Тогда внешняя DFS посещает каждый вектор из \(V(L)\) ровно один раз.
Для вектора с \(r\) слотами показателей и \(t\) различными простыми делителями в \(T\) внутренний поиск является ограниченным процессом backtracking. Его наивная худшая оценка экспоненциальна по \(t\), но на практике дерево резко уменьшается благодаря проверке допустимости слотов, границе \(L\), текущему лучшему завершению, жадному заполнению хвоста и удалению симметрий при равных показателях. Память расходуется умеренно: таблица простых, кеш факторизаций, рекурсивные стеки и отображение лучших значений \(m(k)\).
عدد تاو هو عدد صحيح موجب \(n\) يحقق الشرط \(\tau(n)\mid n\)، حيث تمثل \(\tau(n)\) عدد قواسم \(n\). عند الحد الثابت \(L=10^{16}\)، تنظر المسألة في كل قيمة \(k\) يوجد لها عدد تاو واحد على الاقل \(n\le L\) مع \(\tau(n)=k\)، ثم تعرف
$$m(k)=\min\{n\le L:\tau(n)=k,\ k\mid n\}.$$
والمطلوب هو جمع جميع القيم الدنيا الموجودة \(m(k)\). ويدخل في ذلك بطبيعة الحال الحد البسيط \(m(1)=1\)، لكن الصعوبة الحقيقية اوسع من ايجاد مثال واحد؛ اذ يجب ايجاد اصغر ممثل صالح لكل قيمة قابلة للتحقق من عدد القواسم.
التنفيذات الثلاثة لا تعدد الاعداد \(n\) مباشرة. هي تعمل على متجهات الاسس في التحليل الاولي، لان \(\tau(n)\) نفسه، والشرط \(\tau(n)\mid n\)، وقواعد التقليم كلها تصبح واضحة جدا في هذه الصياغة.
نكتب المرشح على الصورة
$$n=\prod_{i=1}^{r} b_i^{e_i},\qquad b_1<b_2<\cdots<b_r,\qquad e_1\ge e_2\ge \cdots\ge e_r\ge 1.$$
ترتب الاسس ترتيبا غير تصاعدي، لان العدد يكون اصغر ما يمكن عندما توضع الاسس الاكبر على الاعداد الاولية الاصغر مع ثبات مجموعة الاسس نفسها. وعندها تصبح دالة عدد القواسم
$$\tau(n)=\prod_{i=1}^{r}(e_i+1)=:T.$$
وهكذا يحدد كل متجه اسس قيمة من قيم عدد القواسم هي \(T\). وقد تنتج متجهات مختلفة القيمة نفسها \(T\)، ولهذا يجب على البحث ان يحتفظ بافضل عدد وُجد حتى اللحظة لكل مفتاح من هذه المفاتيح.
للمتجه نفسه، تتحقق اصغر صورة ممكنة باستعمال اول \(r\) اعداد اولية:
$$n_{\min}(e_1,\dots,e_r)=\prod_{i=1}^{r} p_i^{e_i},$$
حيث \(p_i\) هو العدد الاولي رقم \(i\). هذا الجداء لا يكون بالضرورة عددا من اعداد تاو؛ بل هو فقط اصغر عدد يملك مجموعة الاسس نفسها. وهنا تظهر اهميته: اذا كان هذا الحد المعياري نفسه يتجاوز \(L\)، فلا يمكن لاي تحقيق اخر للمتجه ذاته ان يقع تحت الحد، ولذلك يمكن حذف ذلك الفرع كله فورا.
ويحافظ البحث الخارجي عمقا على هذا الجداء خطوة خطوة. وهو الثابت الاهم الذي يجعل التعداد الكلي منتهيا.
الان نفكك قيمة عدد القواسم نفسها:
$$T=\prod_{j=1}^{t} q_j^{\nu_j}.$$
وهنا تكون \(q_j\) اوليات مختلفة. وبما ان \(T\) يجب ان يقسم \(n\)، فان كل اولي \(q_j\) يقسم \(T\) لا بد ان يظهر ايضا ضمن عوامل \(n\) الاولية، وباس لا يقل عن \(\nu_j\).
بالنسبة الى متجه اسس ثابت، يتحول هذا الى مسالة اسناد واحد لواحد. يجب وضع كل اولي الزامي \(q_j\) في خانة مختلفة \(i\) تحقق
$$e_i\ge \nu_j.$$
اذا كان عدد الاوليات الالزامية اكبر من عدد الخانات، اي اذا كان \(t>r\)، يصبح المتجه مستحيلا فورا. وكذلك اذا كان اكبر اس في المتجه ما زال اصغر من بعض القيم المطلوبة \(\nu_j\)، فلا توجد اي طريقة صحيحة للاسناد.
لنفترض اننا اخترنا اسنادا ممكنا \(\sigma\) يوزع الاوليات الالزامية على خانات الاسس. عندئذ يكون العدد الناتج
$$N_\sigma=\left(\prod_{j=1}^{t} q_j^{e_{\sigma(j)}}\right)\left(\prod_{i\notin \operatorname{Im}(\sigma)} s_i^{e_i}\right),$$
حيث تمثل \(s_i\) اوليات مختلفة لا تقسم \(T\). وبعد تثبيت الاوليات الالزامية، يصبح اكمال العدد امرا جشعا: تملأ الخانات الباقية باصغر الاوليات المتاحة، بحيث تقترن الاوليات الاصغر بالاسس الاكبر المتبقية.
وسبب ذلك هو متباينة التبديل البسيطة
$$a^x b^y\le a^y b^x\qquad(a<b,\ x\ge y).$$
اي ان الاولي الاصغر يجب ان يذهب الى الاس الاكبر. ولذلك، بالنسبة الى متجه اسس واحد، يبقى القرار غير التافه الوحيد هو كيفية توزيع الاوليات الالزامية \(q_j\) على الخانات المناسبة؛ وبعد هذا القرار يصبح افضل اكمال محددا.
افضل قيمة لذلك المتجه هي
$$M(e_1,\dots,e_r)=\min_{\sigma} N_\sigma,$$
اما القيمة الدنيا العالمية لعدد قواسم ثابت \(k\) فهي
$$m(k)=\min_{\prod_{i=1}^{r}(e_i+1)=k} M(e_1,\dots,e_r).$$
البحث الخارجي هو اجتياز عمقي فوق متجهات الاسس بترتيب غير تصاعدي. يبدأ من اصغر عدد اولي، ولا يسمح بان يكون الاس التالي اكبر من السابق، وبهذا تزور كل مجموعة اسس مرة واحدة فقط في صورتها المعيارية.
وفي كل عقدة من هذا الاجتياز تكون الكميتان التاليتان معروفتين مسبقا:
$$\prod_{i=1}^{r} p_i^{e_i},\qquad T=\prod_{i=1}^{r}(e_i+1).$$
الجداء الاول هو حد التقليم، اما الثاني فهو قيمة عدد القواسم التي نحاول تحسين افضل ممثل لها. وبما ان متجهات مختلفة قد تنتج القيمة نفسها \(T\)، يحتفظ الخوارزم بافضل نتيجة لكل قيمة \(T\) على حدة. كما تخزن تحليلـات \(T\) الاولية في ذاكرة مؤقتة، لان القيم نفسها تظهر مرارا داخل شجرة البحث.
لننظر الى \(k=12\). بما ان
$$12=2^2\cdot 3,$$
فان اي عدد تاو \(n\) يحقق \(\tau(n)=12\) لا بد ان يحتوي على العامل الاولي \(2\) باس لا يقل عن \(2\)، وعلى العامل الاولي \(3\) ايضا.
ومتجهات الاسس التي تحقق
$$\prod(e_i+1)=12$$
هي
$$[11],\qquad [5,1],\qquad [3,2],\qquad [2,1,1].$$
المتجه \([11]\) مستحيل، لان خانة واحدة لا يمكن ان تحمل الاوليين الالزاميين معا. بالنسبة الى \([5,1]\)، تكون اصغر قيمة ممكنة
$$2^5\cdot 3=96.$$
وبالنسبة الى \([3,2]\)، يعطي افضل اسناد
$$2^3\cdot 3^2=72.$$
اما \([2,1,1]\)، فتشغل الاوليات الالزامية \(2\) و\(3\) الخانتين ذواتي الاسين \(2\) و\(1\)، وتحصل الخانة المتبقية على اصغر اولي اضافي لا يقسم \(12\)، وهو \(5\)، فنحصل على
$$2^2\cdot 3\cdot 5=60.$$
اذن
$$m(12)=60.$$
وهذا هو النوع نفسه من المقارنات الذي يجريه الخوارزم لكل قيمة قابلة للتحقق من عدد القواسم.
تولد تنفيذات C++ وPython وJava اولا جدولا كافيا من الاعداد الاولية. ثم يجري DFS خارجي على متجهات الاسس مع الحفاظ تراكميا على كل من الجداء المعياري \(\prod p_i^{e_i}\) وقيمة عدد القواسم الحالية \(T\). وكل عقدة تتم زيارتها تمثل بالفعل نمطا كاملا من الاسس، ولذلك تقيم مباشرة كمرشح لقيمة \(T\) الخاصة بها.
وعند زيارة اي عقدة، يجلب التنفيذ تحليل \(T\) الاولي او يحسبه ثم يعيد استخدامه من الذاكرة المؤقتة. كما تستخدم في جميع المراحل عمليات ضرب مقيدة بالحد، بحيث تتوقف فورا اي شعبة سيتجاوز ناتجها \(L\)، وهذا يحقق التقليم ومنع الفيض في الوقت نفسه.
بالنسبة الى المتجه الحالي، يقوم DFS داخلي ثان بتوزيع الاوليات الالزامية الواردة في تحليل \(T\) على الخانات المناسبة. وتجرب هذه الاوليات بترتيب تنازلي حتى تظهر الفروع السيئة في وقت ابكر ويصبح التقليم اقوى. واذا كانت خانتان غير مستخدمتين تحملان الاس نفسه، فان استكشافهما منفصلتين لا ينتج الا حالة متناظرة مكررة، ولذلك يحتفظ بممثل واحد فقط.
وبعد تثبيت جميع الاوليات الالزامية، تملأ الخانات المتبقية جشعا باصغر الاوليات التي لا تقسم \(T\). ثم يقارن العدد الناتج مع افضل قيمة مخزنة لتلك القيمة من عدد القواسم، ولا يحدث السجل الا عند وجود تحسن حقيقي.
لا توجد صيغة مغلقة بسيطة للزمن الكلي، لان حجم البحث الخارجي يعتمد على عدد متجهات الاسس غير التصاعدية التي تحقق القيد المعياري
$$\prod_{i=1}^{r} p_i^{e_i}\le L.$$
ولنسم هذه المجموعة \(V(L)\). يزور البحث الخارجي كل متجه في \(V(L)\) مرة واحدة بالضبط.
وبالنسبة الى متجه يحوي \(r\) خانات اسس وتكون القيمة \(T\) المرتبطة به ذات \(t\) عوامل اولية مختلفة، فان البحث الداخلي هو عملية backtracking محدودة. وفي اسوأ حالة ساذجة يكون اسيا في \(t\)، لكن الشجرة الفعلية تصغر كثيرا بفضل اختبار صلاحية الخانات، وحد \(L\)، وافضل اكمال معروف حتى اللحظة، والذيل الجشع، وحذف الاختيارات المتناظرة عند تساوي الاسس. اما استهلاك الذاكرة فيبقى معتدلا: جدول للاوليات، وذاكرة مؤقتة لتحليلات قيم عدد القواسم، ومكدسات الاستدعاء، وخريطة تحفظ افضل القيم \(m(k)\).