The \(n\)-th triangular number is
$$T_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$$
The task is to find the first triangular number whose number of positive divisors is greater than a threshold \(D\). The Project Euler instance uses \(D = 500\), while the implementations are written in a slightly more general form and can solve the same question for any nonnegative threshold.
A naive approach would form each \(T_n\) and factor it directly. The crucial observation is that consecutive integers are coprime, so the factorization of \(T_n\) can be split into two smaller and independent pieces before the divisor count is computed.
The entire solution rests on three facts: triangular numbers are built from consecutive integers, the divisor-count function is multiplicative on coprime inputs, and one of \(n\) or \(n+1\) is always even.
The closed form
$$T_n = \frac{n(n+1)}{2}$$
already suggests how to search: for each \(n\), determine how many divisors \(T_n\) has, and stop at the first \(n\) for which that count exceeds \(D\).
The obstacle is that \(T_n\) grows quadratically, so direct factorization becomes steadily more expensive. The implementations therefore avoid treating \(T_n\) as one monolithic integer whenever possible.
If a positive integer has prime factorization
$$m = \prod_{i=1}^{r} p_i^{\alpha_i},$$
then every divisor of \(m\) is obtained by choosing an exponent \(0 \le \beta_i \le \alpha_i\) for each prime \(p_i\). Hence the number of divisors is
$$\tau(m) = \prod_{i=1}^{r} (\alpha_i + 1).$$
This is the only divisor formula the code needs. It never enumerates divisors explicitly; it only extracts the prime exponents and multiplies the corresponding \((\alpha_i + 1)\) factors.
Because consecutive integers share no common factor,
$$\gcd(n, n+1) = 1.$$
Exactly one of \(n\) and \(n+1\) is even, so the factor \(2\) in \(T_n\) can be absorbed into that even term:
$$ (a,b) = \begin{cases} \left(\frac{n}{2}, n+1\right), & \text{if } n \text{ is even}, \\ \left(n, \frac{n+1}{2}\right), & \text{if } n \text{ is odd}. \end{cases} $$
Then two useful identities hold at every iteration:
$$ab = T_n, \qquad \gcd(a,b) = 1.$$
The coprimality is easy to check. For example, if \(n\) is even and some \(d\) divides both \(n/2\) and \(n+1\), then \(d\) also divides \(n\), so \(d\) divides both \(n\) and \(n+1\); therefore \(d=1\). The odd case is identical in spirit.
Now multiplicativity applies:
$$\tau(T_n) = \tau(ab) = \tau(a)\tau(b).$$
This is the main invariant used by the implementations. Instead of factoring one larger triangular number, they factor two smaller coprime numbers and multiply their divisor counts.
Take \(n=7\). Then
$$T_7 = \frac{7 \cdot 8}{2} = 7 \cdot 4.$$
Here \(a=7\) and \(b=4\), which are coprime. Their prime factorizations are
$$7 = 7^1, \qquad 4 = 2^2.$$
Therefore
$$\tau(7) = 2, \qquad \tau(4) = 3, \qquad \tau(T_7) = 2 \cdot 3 = 6.$$
The earlier triangular numbers \(1, 3, 6, 10, 15,\) and \(21\) have at most \(4\) divisors, so the first triangular number with more than \(5\) divisors is \(28\). That is exactly the small checkpoint used by the implementations.
Once the problem is reduced to computing \(\tau(a)\) and \(\tau(b)\), each count is obtained by trial division. The implementation removes all factors of \(2\), then tests odd candidates \(3, 5, 7, \dots\) up to the square root of the remaining value. If a residue larger than \(1\) survives, it must itself be prime and contributes one final factor of \(2\) to the divisor count.
This matches the formula for \(\tau(m)\) exactly: every time the factorization reveals an exponent \(\alpha\), the running answer is multiplied by \(\alpha+1\).
The C++, Python, and Java implementations iterate through \(n = 1, 2, 3, \dots\). For each \(n\), they form the pair \((a,b)\) described above rather than factorizing \(T_n\) directly. This keeps the arithmetic closer to the structure of the formula and preserves the invariant \(ab = T_n\) with \(\gcd(a,b)=1\).
For each of the two factors, the implementation first strips out the power of \(2\), recording its exponent. It then checks only odd trial divisors, counting how many times each one divides the current remainder. Every discovered exponent contributes a multiplier of the form \(\alpha+1\). If the remaining value is still greater than \(1\) after the loop, that remainder is prime and contributes one more factor of \(2\).
After the two divisor counts are computed, the implementation multiplies them to obtain \(\tau(T_n)\). As soon as this product exceeds the requested threshold \(D\), it returns
$$\frac{n(n+1)}{2}.$$
All three versions include a small correctness check based on the fact that the first triangular number with more than \(5\) divisors is \(28\). The C++ version also exposes the threshold as an optional runtime parameter, while the core search strategy remains the same in every language.
Let \(n_*\) be the first index such that \(\tau(T_{n_*}) \gt D\). On the \(n\)-th iteration, the implementation factorizes two numbers of size \(O(n)\) by trial division, so the work per iteration is \(O(\sqrt{n})\).
Summing this from \(1\) through \(n_*\) gives
$$\sum_{n=1}^{n_*} O(\sqrt{n}) = O(n_*^{3/2}).$$
The memory usage is \(O(1)\): the algorithm stores only a handful of integers and does not build a sieve, a divisor table, or a cache of previous factorizations.
Die \(n\)-te Dreieckszahl ist
$$T_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$$
Gesucht ist die erste Dreieckszahl, deren Anzahl positiver Teiler einen Schwellwert \(D\) übersteigt. Die eigentliche Project-Euler-Aufgabe verwendet \(D = 500\), aber die Implementierungen sind leicht verallgemeinert und können dieselbe Suche für jeden nichtnegativen Schwellwert ausführen.
Ein naiver Ansatz würde jede Dreieckszahl direkt bilden und vollständig faktorisieren. Der entscheidende Punkt ist jedoch, dass aufeinanderfolgende ganze Zahlen teilerfremd sind. Dadurch lässt sich die Faktorisierung von \(T_n\) in zwei kleinere, voneinander unabhängige Teile zerlegen, bevor überhaupt die Teileranzahl berechnet wird.
Die gesamte Lösung beruht auf drei Tatsachen: Dreieckszahlen bestehen aus zwei aufeinanderfolgenden Faktoren, die Teilerfunktion ist auf teilerfremden Argumenten multiplikativ, und genau einer der beiden Faktoren \(n\) oder \(n+1\) ist gerade.
Die geschlossene Formel
$$T_n = \frac{n(n+1)}{2}$$
liefert bereits die Suchstrategie: Für jedes \(n\) bestimmt man die Anzahl der Teiler von \(T_n\) und stoppt beim ersten \(n\), für das diese Anzahl größer als \(D\) ist.
Das Problem dabei ist das quadratische Wachstum von \(T_n\). Direkte Faktorisierung wird also stetig teurer. Deshalb behandeln die Implementierungen \(T_n\) nicht als ein einziges großes Objekt, wenn sich seine Struktur besser ausnutzen lässt.
Hat eine positive ganze Zahl die Primfaktorzerlegung
$$m = \prod_{i=1}^{r} p_i^{\alpha_i},$$
dann entsteht jeder Teiler von \(m\) dadurch, dass für jedes \(p_i\) ein Exponent \(0 \le \beta_i \le \alpha_i\) gewählt wird. Deshalb gilt
$$\tau(m) = \prod_{i=1}^{r} (\alpha_i + 1).$$
Mehr braucht der Code nicht. Es werden keine Teilerlisten aufgebaut; stattdessen werden nur die Exponenten der Primfaktoren bestimmt und die zugehörigen Faktoren \((\alpha_i+1)\) multipliziert.
Da aufeinanderfolgende Zahlen keinen gemeinsamen Teiler haben, gilt
$$\gcd(n, n+1) = 1.$$
Genau eine der Zahlen \(n\) und \(n+1\) ist gerade, also kann der Faktor \(2\) aus \(T_n\) in diesen geraden Teil hineingezogen werden:
$$ (a,b) = \begin{cases} \left(\frac{n}{2}, n+1\right), & \text{falls } n \text{ gerade ist}, \\ \left(n, \frac{n+1}{2}\right), & \text{falls } n \text{ ungerade ist}. \end{cases} $$
Dann gelten in jedem Schleifendurchlauf die beiden Invarianten
$$ab = T_n, \qquad \gcd(a,b) = 1.$$
Die Teilerfremdheit ist leicht nachzuweisen. Ist \(n\) gerade und teilt ein \(d\) sowohl \(n/2\) als auch \(n+1\), dann teilt \(d\) auch \(n\) und \(n+1\), also muss \(d=1\) sein. Der ungerade Fall funktioniert genauso.
Damit darf man die Multiplikativität der Teilerfunktion anwenden:
$$\tau(T_n) = \tau(ab) = \tau(a)\tau(b).$$
Genau das ist das Kernprinzip der Implementierungen. Statt eine größere Dreieckszahl direkt zu faktorisieren, faktorisieren sie zwei kleinere teilerfremde Zahlen und multiplizieren anschließend deren Teileranzahlen.
Nehmen wir \(n=7\). Dann ist
$$T_7 = \frac{7 \cdot 8}{2} = 7 \cdot 4.$$
Hier sind also \(a=7\) und \(b=4\), und diese beiden Zahlen sind teilerfremd. Ihre Primfaktorzerlegungen lauten
$$7 = 7^1, \qquad 4 = 2^2.$$
Damit folgt
$$\tau(7) = 2, \qquad \tau(4) = 3, \qquad \tau(T_7) = 2 \cdot 3 = 6.$$
Die vorherigen Dreieckszahlen \(1, 3, 6, 10, 15\) und \(21\) besitzen höchstens \(4\) Teiler. Also ist \(28\) die erste Dreieckszahl mit mehr als \(5\) Teilern. Genau diesen kleinen Test prüfen die Implementierungen zur Selbstkontrolle.
Sobald das Problem auf \(\tau(a)\) und \(\tau(b)\) reduziert ist, genügt für beide Zahlen Probedivision. Die Implementierung entfernt zuerst alle Zweierpotenzen und testet danach nur noch ungerade Kandidaten \(3, 5, 7, \dots\) bis zur Quadratwurzel des aktuellen Restes. Bleibt am Ende ein Rest größer als \(1\), dann ist dieser Rest selbst prim und liefert noch einen letzten Faktor \(2\) zur Teileranzahl.
Das passt exakt zur Formel für \(\tau(m)\): Jedes Mal, wenn ein Exponent \(\alpha\) gefunden wird, wird die laufende Antwort mit \(\alpha+1\) multipliziert.
Die C++-, Python- und Java-Implementierungen gehen \(n = 1, 2, 3, \dots\) der Reihe nach durch. Für jedes \(n\) arbeiten sie mit dem oben beschriebenen Paar \((a,b)\), statt \(T_n\) direkt zu faktorisieren. Dadurch bleibt die Struktur der Formel sichtbar, und die Invariante \(ab = T_n\) mit \(\gcd(a,b)=1\) ist in jedem Schritt sofort verfügbar.
Für jeden der beiden Faktoren werden zuerst alle Zweierfaktoren entfernt und deren Exponent gezählt. Anschließend prüft die Implementierung nur ungerade Testteiler und zählt jeweils, wie oft sie den aktuellen Rest teilen. Jeder gefundene Exponent trägt einen Multiplikator der Form \(\alpha+1\) bei. Wenn nach der Schleife noch ein Rest größer als \(1\) übrig ist, ist dieser Rest prim und liefert einen zusätzlichen Faktor \(2\).
Danach werden die beiden Teileranzahlen multipliziert, um \(\tau(T_n)\) zu erhalten. Sobald dieses Produkt den geforderten Schwellwert \(D\) übersteigt, gibt die Implementierung
$$\frac{n(n+1)}{2}$$
zurück. Alle drei Versionen enthalten einen kleinen Korrektheitstest auf Basis der Tatsache, dass die erste Dreieckszahl mit mehr als \(5\) Teilern gleich \(28\) ist. Die C++-Version erlaubt zusätzlich, den Schwellwert zur Laufzeit zu setzen; die eigentliche Suchidee ist jedoch in allen drei Sprachen identisch.
Sei \(n_*\) der erste Index mit \(\tau(T_{n_*}) \gt D\). Im \(n\)-ten Schritt werden zwei Zahlen der Größe \(O(n)\) per Probedivision faktorisiert, daher kostet ein Schleifendurchlauf \(O(\sqrt{n})\).
Über alle Schritte von \(1\) bis \(n_*\) summiert ergibt das
$$\sum_{n=1}^{n_*} O(\sqrt{n}) = O(n_*^{3/2}).$$
Der Speicherverbrauch ist \(O(1)\): Der Algorithmus hält nur wenige Ganzzahlen gleichzeitig vor und baut weder Sieb noch Teilertabelle noch Faktorisierungsarchiv auf.
\(n\). üçgen sayı
$$T_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$$
İstenen şey, pozitif bölen sayısı bir eşik değeri \(D\)'yi aşan ilk üçgen sayıyı bulmaktır. Project Euler sürümünde \(D = 500\) alınır; uygulamalar ise aynı fikri biraz daha genel biçimde kurup herhangi bir negatif olmayan eşik için çalıştırır.
Doğrudan yaklaşım, her \(T_n\)'yi üretip tamamen çarpanlara ayırmak olurdu. Esas fikir daha keskindir: ardışık iki tamsayı aralarında asaldır. Bu yüzden \(T_n\)'nin çarpan yapısı, bölen sayısı hesaplanmadan önce iki daha küçük ve bağımsız parçaya ayrılabilir.
Çözüm üç temel gerçeğe dayanır: üçgen sayılar ardışık iki terimden oluşur, bölen sayısı fonksiyonu aralarında asal sayılarda çarpımsaldır ve \(n\) ile \(n+1\)'den tam olarak biri çifttir.
Kapalı formül
$$T_n = \frac{n(n+1)}{2}$$
arama stratejisini doğrudan verir: her \(n\) için \(T_n\)'nin kaç böleni olduğunu hesapla ve bu sayı ilk kez \(D\)'yi geçtiğinde dur.
Asıl zorluk, \(T_n\)'nin kuadratik büyümesidir. Bu nedenle doğrudan çarpanlara ayırma maliyeti giderek artar. Uygulamalar bu yüzden \(T_n\)'yi tek ve büyük bir tam sayı gibi ele almak yerine, iç yapısından yararlanır.
Bir pozitif tamsayının asal çarpan ayrışımı
$$m = \prod_{i=1}^{r} p_i^{\alpha_i}$$
ise, her bölen her asal için \(0 \le \beta_i \le \alpha_i\) seçilerek elde edilir. Dolayısıyla
$$\tau(m) = \prod_{i=1}^{r} (\alpha_i + 1)$$
olur. Kodun kullandığı tek bölen sayısı formülü budur. Hiçbir yerde bölenlerin listesi çıkarılmaz; yalnızca asal üsler bulunur ve ilgili \((\alpha_i+1)\) çarpanları biriktirilir.
Ardışık iki sayı ortak bölen paylaşmadığı için
$$\gcd(n, n+1) = 1.$$
\(n\) ile \(n+1\)'den biri mutlaka çifttir; dolayısıyla \(T_n\)'deki \(2\) çarpanı o çift terimin içine alınabilir:
$$ (a,b) = \begin{cases} \left(\frac{n}{2}, n+1\right), & \text{eğer } n \text{ çiftse}, \\ \left(n, \frac{n+1}{2}\right), & \text{eğer } n \text{ tekse}. \end{cases} $$
Böylece her adımda şu iki değişmez elde edilir:
$$ab = T_n, \qquad \gcd(a,b) = 1.$$
Aralarında asallık kolayca doğrulanır. Örneğin \(n\) çiftken bir \(d\) hem \(n/2\)'yi hem \(n+1\)'i bölüyorsa, \(d\) aynı zamanda \(n\)'yi de böler; o halde \(d\), hem \(n\)'yi hem \(n+1\)'i böler ve bu da ancak \(d=1\) ile mümkündür. Tek durum da aynı mantıkla çözülür.
Artık çarpımsallık uygulanabilir:
$$\tau(T_n) = \tau(ab) = \tau(a)\tau(b).$$
Uygulamaların ana değişmezi tam olarak budur. Büyük bir üçgen sayıyı tek seferde çarpanlara ayırmak yerine, iki daha küçük aralarında asal sayının bölen sayıları bulunur ve çarpılır.
\(n=7\) alalım. Bu durumda
$$T_7 = \frac{7 \cdot 8}{2} = 7 \cdot 4.$$
Burada \(a=7\) ve \(b=4\) olur; bu iki sayı aralarında asaldır. Asal çarpan ayrışımları
$$7 = 7^1, \qquad 4 = 2^2$$
şeklindedir. Dolayısıyla
$$\tau(7) = 2, \qquad \tau(4) = 3, \qquad \tau(T_7) = 2 \cdot 3 = 6.$$
Önceki üçgen sayılar \(1, 3, 6, 10, 15\) ve \(21\) en fazla \(4\) bölen taşır. Bu yüzden \(5\)'ten fazla böleni olan ilk üçgen sayı \(28\)'dir. Uygulamalardaki küçük doğrulama testi de tam olarak bu gerçeğe dayanır.
Problem \(\tau(a)\) ve \(\tau(b)\) hesabına indirildikten sonra her iki sayı için de deneme bölmesi yeterlidir. Uygulama önce tüm \(2\) çarpanlarını temizler, sonra yalnızca tek adayları \(3, 5, 7, \dots\) mevcut kalanın kareköküne kadar dener. Döngü bittiğinde \(1\)'den büyük bir artık kalırsa, bu artığın kendisi asaldır ve bölen sayısına son bir \(2\) çarpanı ekler.
Bu süreç \(\tau(m)\) formülüyle birebir uyumludur: her yeni üs \(\alpha\) bulunduğunda çalışan sonuç \(\alpha+1\) ile çarpılır.
C++, Python ve Java uygulamaları \(n = 1, 2, 3, \dots\) değerlerini sırayla dener. Her \(n\) için doğrudan \(T_n\)'yi çarpanlara ayırmak yerine yukarıdaki \((a,b)\) çiftini kurarlar. Böylece hem formülün yapısı korunur hem de \(ab = T_n\) ve \(\gcd(a,b)=1\) değişmezi her adımda açık biçimde elde edilir.
İki çarpanın her biri için önce \(2\)'nin kuvveti ayrılır ve üssü sayılır. Sonra yalnızca tek deneme bölenleri üzerinden gidilir; her bölenin mevcut kalanı kaç kez böldüğü sayılır. Bulunan her üs, cevaba \(\alpha+1\) biçiminde katkı yapar. Döngünün sonunda kalan değer hâlâ \(1\)'den büyükse, o değer asaldır ve ek bir \(2\) çarpanı getirir.
Ardından iki bölen sayısı çarpılarak \(\tau(T_n)\) elde edilir. Bu çarpım istenen eşik \(D\)'yi aşar aşmaz uygulama
$$\frac{n(n+1)}{2}$$
değerini döndürür. Üç sürümün hepsinde, \(5\)'ten fazla böleni olan ilk üçgen sayının \(28\) olduğu bilgisini kullanan küçük bir doğruluk denetimi vardır. C++ sürümü ayrıca eşiği çalışma anında değiştirmeye izin verir; fakat temel arama mantığı bütün dillerde aynıdır.
\(\tau(T_n) \gt D\) koşulunu ilk sağlayan indis \(n_*\) olsun. \(n\). adımda deneme bölmesiyle büyüklüğü \(O(n)\) olan iki sayı çarpanlara ayrıldığı için bir iterasyonun maliyeti \(O(\sqrt{n})\) olur.
Bunu \(1\)'den \(n_*\)'ye kadar topladığımızda
$$\sum_{n=1}^{n_*} O(\sqrt{n}) = O(n_*^{3/2})$$
elde edilir. Bellek kullanımı \(O(1)\)'dir; algoritma yalnızca birkaç tamsayı saklar ve ne bir asal eleği ne bir bölen tablosu ne de önceki çarpan ayrışımlarının arşivini oluşturur.
El \(n\)-ésimo número triangular es
$$T_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$$
La tarea consiste en encontrar el primer número triangular cuyo número de divisores positivos sea mayor que un umbral \(D\). En la versión de Project Euler se toma \(D = 500\), pero las implementaciones están escritas de forma un poco más general y pueden resolver la misma búsqueda para cualquier umbral no negativo.
Un enfoque ingenuo construiría cada \(T_n\) y lo factorizaría directamente. La observación decisiva es que dos enteros consecutivos son coprimos. Eso permite dividir la factorización de \(T_n\) en dos piezas más pequeñas e independientes antes de calcular cuántos divisores tiene.
Toda la solución descansa en tres hechos: los números triangulares provienen de dos términos consecutivos, la función que cuenta divisores es multiplicativa sobre entradas coprimas y exactamente uno de \(n\) o \(n+1\) es par.
La forma cerrada
$$T_n = \frac{n(n+1)}{2}$$
ya sugiere la estrategia de búsqueda: para cada \(n\), calcular cuántos divisores tiene \(T_n\) y detenerse en el primer caso en que esa cantidad supera \(D\).
El inconveniente es que \(T_n\) crece cuadráticamente, así que la factorización directa se vuelve cada vez más costosa. Por eso las implementaciones no tratan a \(T_n\) como un entero grande sin estructura, sino que aprovechan su forma algebraica.
Si un entero positivo tiene descomposición prima
$$m = \prod_{i=1}^{r} p_i^{\alpha_i},$$
entonces cualquier divisor se obtiene escogiendo, para cada primo \(p_i\), un exponente \(0 \le \beta_i \le \alpha_i\). Por lo tanto
$$\tau(m) = \prod_{i=1}^{r} (\alpha_i + 1).$$
Esa es la única fórmula de divisores que necesita el código. Nunca genera la lista completa de divisores; únicamente extrae los exponentes de la factorización prima y acumula los factores \((\alpha_i+1)\).
Como dos enteros consecutivos no comparten factores, se cumple
$$\gcd(n, n+1) = 1.$$
Además, uno y solo uno entre \(n\) y \(n+1\) es par, de modo que el factor \(2\) de \(T_n\) puede absorberse dentro del término par:
$$ (a,b) = \begin{cases} \left(\frac{n}{2}, n+1\right), & \text{si } n \text{ es par}, \\ \left(n, \frac{n+1}{2}\right), & \text{si } n \text{ es impar}. \end{cases} $$
Con esa elección, en cada iteración se mantienen dos identidades importantes:
$$ab = T_n, \qquad \gcd(a,b) = 1.$$
La coprimalidad se comprueba enseguida. Por ejemplo, si \(n\) es par y un \(d\) divide tanto a \(n/2\) como a \(n+1\), entonces también divide a \(n\); por consiguiente divide a \(n\) y a \(n+1\), lo cual obliga a \(d=1\). El caso impar es análogo.
Ahora sí puede aplicarse la multiplicatividad:
$$\tau(T_n) = \tau(ab) = \tau(a)\tau(b).$$
Este es el invariante central usado por las implementaciones. En lugar de factorizar directamente un número triangular más grande, factorizan dos números coprimos más pequeños y multiplican luego sus cantidades de divisores.
Tomemos \(n=7\). Entonces
$$T_7 = \frac{7 \cdot 8}{2} = 7 \cdot 4.$$
Aquí \(a=7\) y \(b=4\), y efectivamente son coprimos. Sus factorizaciones primas son
$$7 = 7^1, \qquad 4 = 2^2.$$
De ahí se obtiene
$$\tau(7) = 2, \qquad \tau(4) = 3, \qquad \tau(T_7) = 2 \cdot 3 = 6.$$
Los números triangulares anteriores \(1, 3, 6, 10, 15\) y \(21\) tienen a lo sumo \(4\) divisores. Por eso el primer número triangular con más de \(5\) divisores es \(28\). Ese es exactamente el pequeño caso de comprobación utilizado por las implementaciones.
Una vez que el problema se reduce a calcular \(\tau(a)\) y \(\tau(b)\), basta aplicar división de prueba a cada uno. La implementación elimina primero todas las potencias de \(2\) y luego prueba solo divisores impares \(3, 5, 7, \dots\) hasta la raíz cuadrada del residuo actual. Si al final queda un residuo mayor que \(1\), ese residuo es primo y aporta un último factor \(2\) al conteo de divisores.
Eso coincide exactamente con la fórmula de \(\tau(m)\): cada vez que la factorización revela un exponente \(\alpha\), la respuesta parcial se multiplica por \(\alpha+1\).
Las implementaciones en C++, Python y Java recorren \(n = 1, 2, 3, \dots\). Para cada \(n\), construyen el par \((a,b)\) descrito arriba en vez de factorizar directamente \(T_n\). De ese modo, la aritmética sigue fielmente la estructura de la fórmula y el invariante \(ab = T_n\) con \(\gcd(a,b)=1\) se mantiene explícito.
Para cada uno de los dos factores, la implementación separa primero la potencia de \(2\) y registra su exponente. Después prueba únicamente divisores impares y cuenta cuántas veces cada uno divide al residuo actual. Cada exponente encontrado aporta un multiplicador de la forma \(\alpha+1\). Si al terminar el bucle el valor restante sigue siendo mayor que \(1\), ese valor es primo y añade un factor extra de \(2\).
Luego se multiplican las dos cantidades de divisores para obtener \(\tau(T_n)\). En cuanto ese producto supera el umbral pedido \(D\), la implementación devuelve
$$\frac{n(n+1)}{2}.$$
Las tres versiones incluyen una pequeña comprobación de corrección basada en que el primer número triangular con más de \(5\) divisores es \(28\). La versión en C++ además permite fijar el umbral durante la ejecución, aunque la estrategia matemática central es la misma en los tres lenguajes.
Sea \(n_*\) el primer índice tal que \(\tau(T_{n_*}) \gt D\). En la iteración \(n\), la implementación factoriza por división de prueba dos números de tamaño \(O(n)\), así que el coste por iteración es \(O(\sqrt{n})\).
Al sumar desde \(1\) hasta \(n_*\), se obtiene
$$\sum_{n=1}^{n_*} O(\sqrt{n}) = O(n_*^{3/2}).$$
El uso de memoria es \(O(1)\): el algoritmo mantiene solo unos pocos enteros y no construye ni una criba de primos, ni una tabla de divisores, ni una caché de factorizaciones previas.
第 \(n\) 个三角数是
$$T_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$$
题目要求找出第一个正因子个数严格大于阈值 \(D\) 的三角数。Project Euler 的原题取 \(D = 500\)，而这些实现把问题稍微推广成了“给定任意非负阈值，寻找第一个满足条件的三角数”。
如果直接做，可以逐个生成 \(T_n\) 并把每个三角数完整分解。但真正高效的切入点在于：相邻整数互素。因此 \(T_n\) 的分解可以先拆成两个更小、彼此独立的部分，再去计算因子个数。
整个解法建立在三个事实上：三角数来自两个相邻整数的乘积，因子个数函数在互素输入上具有乘法性，而且 \(n\) 与 \(n+1\) 中恰好有一个是偶数。
闭式公式
$$T_n = \frac{n(n+1)}{2}$$
已经给出了搜索框架：对每个 \(n\)，求出 \(T_n\) 的正因子个数；当这个数量第一次超过 \(D\) 时停止。
困难在于 \(T_n\) 按二次速度增长，因此如果把每个 \(T_n\) 都当成一个整体去分解，代价会越来越高。实现并没有忽略这个结构，而是直接利用了公式中“相邻整数乘积”的形状。
若正整数 \(m\) 的素因子分解为
$$m = \prod_{i=1}^{r} p_i^{\alpha_i},$$
那么 \(m\) 的任意一个因子，都可以通过为每个素数 \(p_i\) 选择一个指数 \(0 \le \beta_i \le \alpha_i\) 得到。因此
$$\tau(m) = \prod_{i=1}^{r} (\alpha_i + 1).$$
代码需要的只有这条公式。它从不显式枚举全部因子，而是只提取素因子指数，再把对应的 \((\alpha_i+1)\) 逐项相乘。
因为相邻整数没有公因子，所以
$$\gcd(n, n+1) = 1.$$
同时，\(n\) 与 \(n+1\) 中必有且只有一个是偶数，因此 \(T_n\) 中的那个 \(2\) 可以并入偶数项：
$$ (a,b) = \begin{cases} \left(\frac{n}{2}, n+1\right), & \text{当 } n \text{ 为偶数时}, \\ \left(n, \frac{n+1}{2}\right), & \text{当 } n \text{ 为奇数时}. \end{cases} $$
这样一来，每次迭代都同时满足两个重要不变量：
$$ab = T_n, \qquad \gcd(a,b) = 1.$$
互素性并不难证明。比如 \(n\) 为偶数时，若某个 \(d\) 同时整除 \(n/2\) 和 \(n+1\)，那么它也整除 \(n\)，于是它同时整除 \(n\) 与 \(n+1\)，只能得到 \(d=1\)。奇数情形完全同理。
于是可以直接应用乘法性：
$$\tau(T_n) = \tau(ab) = \tau(a)\tau(b).$$
这就是实现中最核心的数学不变量。程序并不直接分解较大的三角数，而是分别分解两个更小的互素整数，再把各自的因子个数相乘。
取 \(n=7\)。此时
$$T_7 = \frac{7 \cdot 8}{2} = 7 \cdot 4.$$
因此 \(a=7\)，\(b=4\)，并且二者互素。它们的素因子分解分别是
$$7 = 7^1, \qquad 4 = 2^2.$$
所以
$$\tau(7) = 2, \qquad \tau(4) = 3, \qquad \tau(T_7) = 2 \cdot 3 = 6.$$
更早的三角数 \(1, 3, 6, 10, 15, 21\) 的因子个数都不超过 \(4\)。因此第一个因子个数大于 \(5\) 的三角数就是 \(28\)。实现中的小型正确性检查正是利用了这个例子。
一旦问题被化成计算 \(\tau(a)\) 与 \(\tau(b)\)，对这两个数分别做试除就够了。实现先剥离所有因子 \(2\)，记录其指数；然后只检查奇数候选 \(3, 5, 7, \dots\)，直到当前剩余值的平方根为止。如果循环结束后还剩下一个大于 \(1\) 的数，那么这个剩余值本身就是素数，会再贡献一个因子 \(2\) 给因子个数。
这个过程与 \(\tau(m)\) 的公式完全一致：每当分解中发现一个指数 \(\alpha\)，当前答案就乘上 \(\alpha+1\)。
C++、Python 和 Java 实现都按顺序枚举 \(n = 1, 2, 3, \dots\)。对于每个 \(n\)，它们都先构造上面的 \((a,b)\) 对，而不是直接去分解 \(T_n\)。这样做既保留了公式结构，也把 \(ab = T_n\) 与 \(\gcd(a,b)=1\) 这两个关键不变量显式保持在每一步中。
对两个因子中的任意一个，程序都会先把 \(2\) 的幂次全部除掉并统计指数。随后只用奇数试除因子去检测当前剩余值，并统计每个因子出现了多少次。每得到一个指数，就把部分结果乘上 \(\alpha+1\)。如果循环结束后剩余值仍大于 \(1\)，说明这个剩余值是素数，还需要再乘一个 \(2\)。
两个因子的因子个数算出后，相乘即可得到 \(\tau(T_n)\)。一旦这个乘积严格超过给定阈值 \(D\)，实现就返回
$$\frac{n(n+1)}{2}.$$
三种语言的版本都包含一个小规模正确性检查，利用的是“因子个数大于 \(5\) 的第一个三角数是 \(28\)”这一事实。C++ 版本还允许在运行时指定阈值，但三种实现的核心搜索逻辑完全一致。
设 \(n_*\) 是第一个满足 \(\tau(T_{n_*}) \gt D\) 的下标。第 \(n\) 次迭代中，程序用试除法分解两个大小为 \(O(n)\) 的整数，因此单次迭代代价为 \(O(\sqrt{n})\)。
把这个代价从 \(1\) 累加到 \(n_*\)，得到
$$\sum_{n=1}^{n_*} O(\sqrt{n}) = O(n_*^{3/2}).$$
空间复杂度为 \(O(1)\)：算法只保存少量整数，不构建素数筛、不维护因子表，也不缓存过去所有分解结果。
\(n\)-е треугольное число равно
$$T_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$$
Нужно найти первое треугольное число, у которого число положительных делителей строго больше заданного порога \(D\). В исходной задаче Project Euler используется \(D = 500\), но реализации написаны немного шире и позволяют решать тот же поиск для любого неотрицательного порога.
Наивный путь состоял бы в том, чтобы поочередно строить каждое \(T_n\) и полностью разлагать его на простые множители. Однако гораздо важнее другое наблюдение: соседние целые числа взаимно просты. Значит, разложение \(T_n\) можно заранее расколоть на две меньшие независимые части и лишь затем считать число делителей.
Вся идея решения держится на трех фактах: треугольное число выражается через два соседних множителя, функция числа делителей мультипликативна на взаимно простых аргументах, и ровно одно из чисел \(n\) и \(n+1\) является четным.
Замкнутая формула
$$T_n = \frac{n(n+1)}{2}$$
сразу подсказывает стратегию: для каждого \(n\) надо выяснить, сколько делителей имеет \(T_n\), и остановиться на первом индексе, где это число превосходит \(D\).
Проблема в том, что \(T_n\) растет квадратично, поэтому прямая факторизация становится все дороже. Именно поэтому реализации не рассматривают \(T_n\) как один большой неструктурированный объект, а используют форму формулы напрямую.
Если положительное число имеет разложение
$$m = \prod_{i=1}^{r} p_i^{\alpha_i},$$
то любой делитель \(m\) получается выбором показателя \(0 \le \beta_i \le \alpha_i\) для каждого простого \(p_i\). Поэтому
$$\tau(m) = \prod_{i=1}^{r} (\alpha_i + 1).$$
Это единственная формула о делителях, которая нужна коду. Полный список делителей нигде не строится; извлекаются только показатели простых множителей, после чего перемножаются соответствующие множители \((\alpha_i+1)\).
Поскольку соседние числа не имеют общего делителя, верно
$$\gcd(n, n+1) = 1.$$
Кроме того, ровно одно из чисел \(n\) и \(n+1\) четно, поэтому множитель \(2\) из \(T_n\) можно перенести внутрь четной части:
$$ (a,b) = \begin{cases} \left(\frac{n}{2}, n+1\right), & \text{если } n \text{ четно}, \\ \left(n, \frac{n+1}{2}\right), & \text{если } n \text{ нечетно}. \end{cases} $$
При таком выборе на каждом шаге выполняются два полезных инварианта:
$$ab = T_n, \qquad \gcd(a,b) = 1.$$
Взаимная простота доказывается сразу. Например, если \(n\) четно и некоторое \(d\) делит и \(n/2\), и \(n+1\), то оно делит и \(n\). Значит, \(d\) делит одновременно \(n\) и \(n+1\), а это возможно только при \(d=1\). В нечетном случае рассуждение полностью аналогично.
Теперь можно применить мультипликативность:
$$\tau(T_n) = \tau(ab) = \tau(a)\tau(b).$$
Именно этот инвариант лежит в центре всех реализаций. Вместо прямой факторизации более крупного треугольного числа они факторизуют два меньших взаимно простых числа и затем перемножают полученные количества делителей.
Возьмем \(n=7\). Тогда
$$T_7 = \frac{7 \cdot 8}{2} = 7 \cdot 4.$$
Здесь \(a=7\) и \(b=4\), и эти числа взаимно просты. Их разложения имеют вид
$$7 = 7^1, \qquad 4 = 2^2.$$
Следовательно,
$$\tau(7) = 2, \qquad \tau(4) = 3, \qquad \tau(T_7) = 2 \cdot 3 = 6.$$
Предыдущие треугольные числа \(1, 3, 6, 10, 15, 21\) имеют не более \(4\) делителей. Поэтому первым треугольным числом с числом делителей больше \(5\) оказывается \(28\). На этом примере построена небольшая проверка корректности в реализациях.
После перехода к вычислению \(\tau(a)\) и \(\tau(b)\) для каждой из этих величин достаточно обычного пробного деления. Реализация сначала удаляет все множители \(2\), запоминая их показатель, а затем проверяет только нечетные кандидаты \(3, 5, 7, \dots\) вплоть до квадратного корня из текущего остатка. Если после завершения цикла остается число больше \(1\), то этот остаток сам прост и дает еще один множитель \(2\) в формуле для числа делителей.
Это полностью соответствует формуле для \(\tau(m)\): каждый найденный показатель \(\alpha\) добавляет множитель \(\alpha+1\) к текущему ответу.
Реализации на C++, Python и Java последовательно перебирают \(n = 1, 2, 3, \dots\). Для каждого \(n\) они строят пару \((a,b)\), описанную выше, вместо того чтобы напрямую факторизовать \(T_n\). Благодаря этому структура формулы используется буквально, а инвариант \(ab = T_n\) при \(\gcd(a,b)=1\) сохраняется явно.
Для каждого из двух множителей программа сначала выделяет степень двойки и запоминает ее показатель. Затем она проверяет только нечетные пробные делители и считает, сколько раз каждый из них делит текущий остаток. Каждый найденный показатель вносит множитель вида \(\alpha+1\). Если после цикла остаток все еще больше \(1\), то этот остаток прост и добавляет еще один множитель \(2\).
После этого два количества делителей перемножаются, что дает \(\tau(T_n)\). Как только произведение становится строго больше порога \(D\), реализация возвращает
$$\frac{n(n+1)}{2}.$$
Во всех трех версиях есть небольшой тест корректности, основанный на факте, что первым треугольным числом с более чем \(5\) делителями является \(28\). Версия на C++ дополнительно позволяет задать порог во время запуска, но математическая схема поиска во всех языках одинакова.
Пусть \(n_*\) обозначает первый индекс, для которого \(\tau(T_{n_*}) \gt D\). На \(n\)-й итерации программа факторизует пробным делением два числа размера \(O(n)\), поэтому стоимость одного шага равна \(O(\sqrt{n})\).
Суммирование от \(1\) до \(n_*\) дает
$$\sum_{n=1}^{n_*} O(\sqrt{n}) = O(n_*^{3/2}).$$
Память требуется в объеме \(O(1)\): алгоритм хранит лишь несколько целых чисел и не строит ни решето, ни таблицу делителей, ни архив прежних факторизаций.
العدد المثلثي رقم \(n\) هو
$$T_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$$
المطلوب هو إيجاد أول عدد مثلثي يكون عدد قواسمه الموجبة أكبر من حدّ معيّن \(D\). في صيغة Project Euler الأصلية نأخذ \(D = 500\)، لكن التنفيذات صيغت بصورة أعم قليلًا بحيث يمكنها حل المسألة نفسها لأي حد غير سالب.
الطريقة الساذجة هي تكوين كل \(T_n\) ثم تحليله مباشرة إلى عوامله الأولية. لكن الفكرة الحاسمة هنا هي أن عددين متتاليين يكونان أوليين فيما بينهما، ولذلك يمكن تفكيك بنية \(T_n\) إلى جزأين أصغر ومستقلين قبل حساب عدد القواسم.
الحل كله يعتمد على ثلاث حقائق: العدد المثلثي يتكوّن من حاصل ضرب عددين متتاليين، ودالة عدد القواسم ضربية على المدخلات المتباينة أوليًا، وأحد العددين \(n\) أو \(n+1\) فقط يكون زوجيًا.
الصيغة المغلقة
$$T_n = \frac{n(n+1)}{2}$$
تعطي مباشرة خطة البحث: لكل \(n\)، نحسب عدد قواسم \(T_n\)، ونتوقف عند أول قيمة يتجاوز فيها هذا العدد الحد \(D\).
المشكلة أن \(T_n\) ينمو نموًا تربيعيًا، ولذلك يصبح التحليل المباشر أكثر كلفة مع ازدياد \(n\). لهذا لا تتعامل التنفيذات مع \(T_n\) كعدد ضخم بلا بنية، بل تستغل شكله الجبري نفسه.
إذا كان التحليل الأولي لعدد موجب \(m\) هو
$$m = \prod_{i=1}^{r} p_i^{\alpha_i},$$
فإن كل قاسم لـ \(m\) ينتج من اختيار أس \(0 \le \beta_i \le \alpha_i\) لكل أولي \(p_i\). لذلك
$$\tau(m) = \prod_{i=1}^{r} (\alpha_i + 1).$$
هذه هي الصيغة الوحيدة التي يحتاجها الكود. لا يتم توليد قائمة القواسم نفسها، بل تُستخرج أسس العوامل الأولية ثم تُضرب الحدود \((\alpha_i+1)\) بعضها في بعض.
بما أن عددين متتاليين لا يشتركان في أي عامل، فإن
$$\gcd(n, n+1) = 1.$$
كذلك يكون أحد العددين \(n\) و\(n+1\) زوجيًا بالضبط، ولذلك يمكن امتصاص العامل \(2\) الموجود في \(T_n\) داخل الحد الزوجي. فإذا كان \(n\) زوجيًا نأخذ \(a = n/2\) و\(b = n+1\)، وإذا كان \(n\) فرديًا نأخذ \(a = n\) و\(b = (n+1)/2\).
وعندها يظهر في كل دورة متغيران ثابتان مهمان:
$$ab = T_n, \qquad \gcd(a,b) = 1.$$
وإثبات التباين الأولي بسيط. إذا كان \(n\) زوجيًا ووجدنا \(d\) يقسم كلًا من \(n/2\) و\(n+1\)، فإنه يقسم أيضًا \(n\)، وبالتالي يقسم \(n\) و\(n+1\) معًا، وهذا لا يحدث إلا عندما يكون \(d=1\). والحالة الفردية مماثلة تمامًا.
الآن يمكن استعمال الضربية:
$$\tau(T_n) = \tau(ab) = \tau(a)\tau(b).$$
هذا هو الثابت الرياضي المركزي في التنفيذات. فبدل تحليل عدد مثلثي أكبر مباشرة، يتم تحليل عددين أصغر متباينين أوليًا، ثم يُضرب عدد قواسم كل منهما في الآخر.
لنأخذ \(n=7\). عندئذ
$$T_7 = \frac{7 \cdot 8}{2} = 7 \cdot 4.$$
إذن \(a=7\) و\(b=4\)، وهما متباينان أوليًا. وتحليلهما الأولي هو
$$7 = 7^1, \qquad 4 = 2^2.$$
ومن ثم
$$\tau(7) = 2, \qquad \tau(4) = 3, \qquad \tau(T_7) = 2 \cdot 3 = 6.$$
أما الأعداد المثلثية السابقة \(1, 3, 6, 10, 15, 21\) فلا يملك أي منها أكثر من \(4\) قواسم. لذلك يكون أول عدد مثلثي يملك أكثر من \(5\) قواسم هو \(28\). وهذه هي حالة التحقق الصغيرة التي تعتمد عليها التنفيذات للتأكد من صحة المنهج.
بعد اختزال المسألة إلى حساب \(\tau(a)\) و\(\tau(b)\)، تكفي القسمة التجريبية لكل واحد منهما. يبدأ التنفيذ بإزالة جميع عوامل \(2\) وتسجيل أسها، ثم يختبر فقط القواسم الفردية \(3, 5, 7, \dots\) حتى الجذر التربيعي للباقي الحالي. وإذا بقي في النهاية عدد أكبر من \(1\)، فهذا يعني أن هذا الباقي نفسه أولي، ويضيف عاملًا أخيرًا مقداره \(2\) إلى عدد القواسم.
وهذا يطابق تمامًا صيغة \(\tau(m)\): فكلما كُشف أس جديد \(\alpha\)، ضُربت النتيجة الجزئية في \(\alpha+1\).
تنفيذات C++ وPython وJava تمر على \(n = 1, 2, 3, \dots\) بالتتابع. ولكل \(n\) تبني الزوج \((a,b)\) المذكور أعلاه بدلًا من تحليل \(T_n\) مباشرة. بهذه الطريقة تبقى بنية الصيغة واضحة، كما يبقى الثابت \(ab = T_n\) مع \(\gcd(a,b)=1\) حاضرًا صراحة في كل خطوة.
بالنسبة إلى كل واحد من العاملين، يبدأ التنفيذ بفصل قوة العدد \(2\) وتسجيل أسها. بعد ذلك يختبر فقط القواسم الفردية ويحصر عدد مرات قسمة كل قاسم للباقي الحالي. وكل أس يتم العثور عليه يضيف عاملًا من الشكل \(\alpha+1\) إلى الناتج. وإذا ظل بعد انتهاء الحلقة باقي أكبر من \(1\)، فإن هذا الباقي عدد أولي ويضيف عاملًا إضافيًا مقداره \(2\).
بعد حساب عددي القواسم للعاملين، يتم ضربهما للحصول على \(\tau(T_n)\). وما إن يصبح هذا الناتج أكبر من الحد \(D\)، يعيد التنفيذ القيمة
$$\frac{n(n+1)}{2}.$$
وتتضمن النسخ الثلاث اختبارًا صغيرًا للصحة يعتمد على أن أول عدد مثلثي يملك أكثر من \(5\) قواسم هو \(28\). كما تسمح نسخة C++ بتمرير الحد أثناء التشغيل، لكن الفكرة الرياضية الأساسية للبحث واحدة في جميع اللغات.
ليكن \(n_*\) أول فهرس يحقق \(\tau(T_{n_*}) \gt D\). في الدورة رقم \(n\)، يقوم التنفيذ بتحليل عددين حجمهما \(O(n)\) بواسطة القسمة التجريبية، ولذلك تكون كلفة الدورة الواحدة \(O(\sqrt{n})\).
وبجمع ذلك من \(1\) حتى \(n_*\) نحصل على
$$\sum_{n=1}^{n_*} O(\sqrt{n}) = O(n_*^{3/2}).$$
أما الذاكرة فهي \(O(1)\)، لأن الخوارزمية لا تحتفظ إلا بعدد قليل من القيم الصحيحة، ولا تبني غربالًا للأعداد الأولية ولا جدولًا للقواسم ولا مخزنًا لتحليلات سابقة.