Let \(T_r=\frac{r(r+1)}2\) be the \(r\)-th triangular number, with \(T_0=0\). The implementations start from \(T_2=3\) and repeatedly look for the next nontrivial identity of the form
$$T_n-T_w=T_m,$$
where \(n>m\) and \(w>0\). At each hit, the solver chooses the smallest possible later index \(n\), adds the corresponding offset \(w\) to the running search position, replaces \(m\) by \(n\), and continues. The required output is the accumulated position of the 70th hit, not the triangular value itself.
A naive search would test huge numbers of pairs \((n,w)\) for every current \(m\). The local solutions avoid that completely by turning the existence of such a triangle identity into a divisor problem for \(m(m+1)\), so each step becomes: factor two consecutive integers, enumerate divisors, and jump directly to the next valid state.
Start from
$$T_n-T_w=\frac{n(n+1)-w(w+1)}2=T_m=\frac{m(m+1)}2.$$
Multiplying by 2 and factoring the left-hand side gives
$$n(n+1)-w(w+1)=(n-w)(n+w+1)=m(m+1).$$
Define
$$P=m(m+1),\qquad u=n-w,\qquad v=n+w+1.$$
Then every nontrivial hit corresponds to a divisor pair
$$uv=P.$$
Because \(u+v=2n+1\), the sum \(u+v\) must be odd. Conversely, if \(u\) and \(v\) are divisors of \(P\) with odd sum, then they reconstruct integers \(n\) and \(w\).
Solving the two linear equations for \(n\) and \(w\) gives
$$n=\frac{u+v-1}{2},\qquad w=\frac{v-u-1}{2}.$$
The condition \(w>0\) is exactly
$$v>u+1.$$
This matters because the divisor pair \((u,v)=(m,m+1)\) always exists and gives \(n=m,\ w=0\), which is only the trivial identity \(T_m-T_0=T_m\). The implementations deliberately reject that case and keep only genuinely later hits.
For fixed \(P\) and \(u\le \sqrt{P}\), we have \(v=P/u\), so
$$n(u)=\frac{u+P/u-1}{2}.$$
On the interval \(1\le u\le \sqrt{P}\), increasing \(u\) decreases \(P/u\), and \(n(u)\) becomes smaller. Therefore the smallest later triangle index \(n\) is obtained by taking the largest admissible divisor \(u\) not exceeding \(\sqrt{P}\). That is exactly what the depth-first divisor search is tracking.
The factorization itself is also simplified by the identity
$$\gcd(m,m+1)=1.$$
So instead of factoring the large product \(P\) directly, the implementations factor \(m\) and \(m+1\) separately and merge their prime exponents.
Take \(m=6\). Then
$$T_6=21,\qquad P=m(m+1)=42.$$
The divisor pairs with \(u\le\sqrt{42}\) are
$$ (1,42),\ (2,21),\ (3,14),\ (6,7). $$
All four pairs have odd sum, but \((6,7)\) gives \(w=0\), so it is the trivial representation and is discarded. Among the remaining pairs, the largest admissible \(u\) is \(u=3\), with \(v=14\). Hence
$$n=\frac{3+14-1}{2}=8,\qquad w=\frac{14-3-1}{2}=5.$$
Indeed,
$$T_8-T_5=36-15=21=T_6.$$
The other admissible pairs would produce later hits such as \(T_{11}-T_9\) and \(T_{21}-T_{20}\), but the algorithm wants the nearest one, so it keeps \(n=8\).
Each iteration begins with the current triangular index \(m\). The implementations factor \(m\) and \(m+1\) separately using deterministic Miller-Rabin primality checks for 64-bit inputs together with Pollard-Rho for composite splitting. This is much faster than scanning divisors naively, and it exploits the coprimality of consecutive integers.
Once the prime exponents are known, a recursive divisor generator enumerates every divisor \(u\) of \(P=m(m+1)\). Only candidates with \(u\le\sqrt{P}\) are needed, because the partner divisor is \(v=P/u\). For each candidate, the code tests the two number-theoretic conditions already derived:
$$u+v\equiv 1\pmod{2},\qquad v>u+1.$$
The best divisor is simply the largest \(u\) that passes both tests. After that, the code converts \((u,v)\) into the next state \((w,n)\) via the closed formulas above.
The running answer is advanced by the offset \(w\), and the current triangular index is replaced by \(n\). Repeating this step-by-step jump avoids any brute-force scan through failed candidates. The C++, Python, and Java implementations all follow the same mathematics; they differ only in low-level integer handling. They also check a common validation point: the 10th hit occurs at accumulated position \(2964\) and lands on \(T_{1696}=1{,}439{,}056\).
If \(H\) hits are required, the total work is the sum of \(H-1\) transition costs. One transition consists of factoring two consecutive integers and then enumerating the divisors of their product. If \(\tau(P)\) is the number of divisors of \(P=m(m+1)\), the divisor search is \(O(\tau(P))\) because each divisor is generated once.
The harder part is integer factorization. Pollard-Rho is a randomized algorithm, so the cleanest statement is heuristic: in practice the runtime is dominated by a modest number of 64-bit factorizations, and the method is easily fast enough for the requested 70th hit. Memory use stays small, since the program stores only a prime-exponent map, a recursion stack for divisor generation, and a handful of wide integers for \(P\), \(\sqrt{P}\), \(n\), and \(w\).
Sei \(T_r=\frac{r(r+1)}2\) die \(r\)-te Dreieckszahl, mit \(T_0=0\). Die Implementierungen starten bei \(T_2=3\) und suchen dann wiederholt eine nichttriviale Darstellung
$$T_n-T_w=T_m,$$
wobei \(n>m\) und \(w>0\) gelten. In jedem Treffer wird der kleinstmögliche spätere Index \(n\) gewählt, der zugehörige Offset \(w\) zur laufenden Suchposition addiert und anschließend \(m\leftarrow n\) gesetzt. Gesucht ist also die akkumulierte Position des 70. Treffers und nicht einfach der Zahlenwert der 70. Dreieckszahl.
Eine direkte Suche über viele Paare \((n,w)\) wäre völlig unpraktisch. Die lokalen Lösungen ersetzen diese Suche durch Zahlentheorie: Die Bedingung für einen Treffer wird in eine Teilerzerlegung von \(m(m+1)\) übersetzt. Dadurch besteht jeder Schritt nur noch aus Faktorisierung, Divisoren-DFS und einem direkten Sprung zum nächsten gültigen Zustand.
Ausgehend von
$$T_n-T_w=\frac{n(n+1)-w(w+1)}2=T_m=\frac{m(m+1)}2$$
erhält man nach Multiplikation mit 2 und Faktorisierung
$$n(n+1)-w(w+1)=(n-w)(n+w+1)=m(m+1).$$
Setze
$$P=m(m+1),\qquad u=n-w,\qquad v=n+w+1.$$
Dann entspricht jeder nichttriviale Treffer einem Teilerpaar
$$uv=P.$$
Außerdem ist
$$u+v=2n+1,$$
also muss \(u+v\) ungerade sein. Umgekehrt liefert jedes Teilerpaar von \(P\) mit ungerader Summe wieder ganzzahlige Werte für \(n\) und \(w\).
Aus den beiden linearen Beziehungen folgt sofort
$$n=\frac{u+v-1}{2},\qquad w=\frac{v-u-1}{2}.$$
Die Bedingung \(w>0\) ist äquivalent zu
$$v>u+1.$$
Genau dadurch wird das triviale Paar \((u,v)=(m,m+1)\) ausgeschlossen, denn dieses liefert nur \(n=m,\ w=0\) und damit die banale Identität \(T_m-T_0=T_m\). Die Implementierungen suchen ausdrücklich nach einem späteren Treffer.
Für festes \(P\) und \(u\le\sqrt{P}\) gilt \(v=P/u\), also
$$n(u)=\frac{u+P/u-1}{2}.$$
Im Bereich \(1\le u\le\sqrt{P}\) wird \(n(u)\) kleiner, wenn \(u\) größer wird. Daher erhält man den nächstliegenden späteren Index \(n\), indem man den größten zulässigen Divisor \(u\) wählt. Genau diesen Wert merkt sich die Divisoren-Suche.
Zusätzlich nutzt der Code
$$\gcd(m,m+1)=1.$$
Dadurch können \(m\) und \(m+1\) getrennt faktorisiert und ihre Primexponenten anschließend zusammengeführt werden, statt das Produkt \(P\) direkt zu zerlegen.
Für \(m=6\) gilt
$$T_6=21,\qquad P=6\cdot 7=42.$$
Die Teilerpaare mit \(u\le\sqrt{42}\) sind
$$ (1,42),\ (2,21),\ (3,14),\ (6,7). $$
Alle vier Summen sind ungerade, aber \((6,7)\) führt zu \(w=0\) und ist deshalb nur der triviale Fall. Der größte verbleibende zulässige Divisor ist \(u=3\), also \(v=14\). Damit folgt
$$n=\frac{3+14-1}{2}=8,\qquad w=\frac{14-3-1}{2}=5.$$
Tatsächlich ist
$$T_8-T_5=36-15=21=T_6.$$
Die anderen zulässigen Paare würden spätere Treffer wie \(T_{11}-T_9\) oder \(T_{21}-T_{20}\) liefern. Da der Algorithmus den nächsten Treffer sucht, behält er \(n=8\).
Jede Iteration beginnt mit dem aktuellen Index \(m\). Die Implementierungen testen Primzahlen mit einem für 64-Bit-Eingaben deterministischen Miller-Rabin-Verfahren und zerlegen zusammengesetzte Zahlen mit Pollard-Rho. Weil zwei aufeinanderfolgende Zahlen teilerfremd sind, ist es effizienter, \(m\) und \(m+1\) getrennt zu faktorisierten und erst danach zu kombinieren.
Aus den Primexponenten wird per rekursiver Tiefensuche jeder Divisor \(u\) von \(P=m(m+1)\) erzeugt. Benötigt werden nur Kandidaten bis \(\sqrt{P}\), denn der Partner ist stets \(v=P/u\). Für jeden Kandidaten prüft der Code die beiden mathematischen Bedingungen
$$u+v\equiv 1\pmod{2},\qquad v>u+1.$$
Der beste Kandidat ist einfach der größte \(u\), der beide Tests besteht. Danach werden \(n\) und \(w\) mit den geschlossenen Formeln berechnet.
Der laufende Suchindex wird um \(w\) erhöht, und als neuer aktueller Dreieckszahlindex wird \(n\) verwendet. So überspringt die Lösung alle Fehlschläge und springt direkt von einem Treffer zum nächsten. Die C++-, Python- und Java-Versionen benutzen dieselbe Mathematik; sie unterscheiden sich nur in den verwendeten Ganzzahltypen. Als gemeinsame Kontrolle prüfen sie außerdem, dass der 10. Treffer bei Position \(2964\) liegt und auf \(T_{1696}=1{,}439{,}056\) endet.
Für \(H\) benötigte Treffer setzt sich die Gesamtlaufzeit aus \(H-1\) Übergängen zusammen. Ein Übergang besteht aus der Faktorisierung von zwei aufeinanderfolgenden Zahlen und einer Divisorensuche über das Produkt \(P\). Ist \(\tau(P)\) die Anzahl der Divisoren von \(P\), dann kostet der DFS-Teil \(O(\tau(P))\), weil jeder Divisor höchstens einmal erzeugt wird.
Die eigentliche Schwierigkeit liegt in der Faktorisierung. Für Pollard-Rho ist eine saubere Worst-Case-Schätzung hier weniger wichtig als das praktische Verhalten: Im relevanten Bereich dominieren einige wenige 64-Bit-Faktorisierungen, und das genügt für den 70. Treffer problemlos. Der Speicherbedarf bleibt klein, weil nur eine Primfaktortabelle, ein Rekursionsstapel und einige breite Ganzzahlen für \(P\), \(\sqrt{P}\), \(n\) und \(w\) gehalten werden.
\(T_r=\frac{r(r+1)}2\) ile \(r\)-inci üçgensel sayıyı gösterelim ve \(T_0=0\) kabul edelim. Uygulamalar \(T_2=3\) ile başlıyor ve sonra tekrar tekrar
$$T_n-T_w=T_m$$
biçimindeki gayritrivial eşitliğin bir sonraki örneğini arıyor. Burada \(n>m\) ve \(w>0\). Her vuruşta mümkün olan en küçük sonraki indeks \(n\) seçiliyor, karşılık gelen kayma miktarı \(w\) toplam arama konumuna ekleniyor, ardından yeni durum \(m\leftarrow n\) yapılıyor. Yani istenen çıktı 70. vuruşta ulaşılan üçgensel sayı değil, o vuruşun birikimli konumudur.
Doğrudan yöntem, her adımda çok sayıda \((n,w)\) çiftini denemeyi gerektirirdi. Yerel çözümler bunu yapmıyor; bunun yerine vuruş koşulunu \(m(m+1)\) sayısının bölen yapısına çeviriyor. Böylece her geçiş, ardışık iki sayıyı çarpanlara ayırıp bölenleri gezerek bir sonraki geçerli duruma doğrudan sıçrıyor.
Başlangıç denklemi
$$T_n-T_w=\frac{n(n+1)-w(w+1)}2=T_m=\frac{m(m+1)}2$$
olduğuna göre, 2 ile çarpıp çarpanlara ayırınca
$$n(n+1)-w(w+1)=(n-w)(n+w+1)=m(m+1)$$
elde edilir. Şimdi
$$P=m(m+1),\qquad u=n-w,\qquad v=n+w+1$$
tanımlarını yapalım. O zaman her gayritrivial vuruş bir bölen çifti ile eşdeğerdir:
$$uv=P.$$
Ayrıca
$$u+v=2n+1$$
olduğundan toplam mutlaka tektir. Tersine, toplamı tek olan her bölen çifti de bize tamsayı \(n\) ve \(w\) verir.
İki doğrusal eşitliği çözünce
$$n=\frac{u+v-1}{2},\qquad w=\frac{v-u-1}{2}$$
çıkar. Burada \(w>0\) koşulu tam olarak
$$v>u+1$$
demektir. Bunun önemi şudur: \((u,v)=(m,m+1)\) çifti her zaman vardır ve bu çift yalnızca \(n=m,\ w=0\) vererek trivial özdeşlik \(T_m-T_0=T_m\) üretir. Kod bu durumu özellikle dışarıda bırakır; çünkü aranan şey aynı üçgensel sayının bir sonraki gerçek görünümüdür.
\(P\) sabit ve \(u\le\sqrt{P}\) iken \(v=P/u\) olur. Dolayısıyla
$$n(u)=\frac{u+P/u-1}{2}.$$
\(1\le u\le\sqrt{P}\) aralığında \(u\) büyüdükçe \(P/u\) küçülür ve buna bağlı olarak \(n(u)\) da küçülür. Demek ki en yakın sonraki vuruş, \(\sqrt{P}\)'yi aşmayan en büyük geçerli \(u\) ile gelir. DFS tam olarak bu değeri takip eder.
Bir başka önemli sadeleşme de
$$\gcd(m,m+1)=1$$
eşitliğidir. Bu sayede \(P\)'yi doğrudan ayırmak yerine \(m\) ve \(m+1\) ayrı ayrı çarpanlara ayrılır, sonra üsler birleştirilir.
\(m=6\) için
$$T_6=21,\qquad P=6\cdot 7=42.$$
\(u\le\sqrt{42}\) koşulunu sağlayan bölen çiftleri
$$ (1,42),\ (2,21),\ (3,14),\ (6,7) $$
şeklindedir. Hepsinin toplamı tektir; ancak \((6,7)\) çifti \(w=0\) verdiği için yalnızca trivial duruma karşılık gelir. Kalan adaylar arasında en büyük geçerli \(u\) değeri \(3\) olduğundan \(v=14\) alınır. Böylece
$$n=\frac{3+14-1}{2}=8,\qquad w=\frac{14-3-1}{2}=5$$
olur ve gerçekten
$$T_8-T_5=36-15=21=T_6.$$
\((2,21)\) veya \((1,42)\) seçilseydi daha geç eşitlikler elde edilirdi. Algoritma ise ilk sonraki görünümü istediği için \(n=8\)'i tutar.
Her iterasyon güncel \(m\) ile başlar. Uygulamalar 64 bit aralığında kesin çalışan Miller-Rabin asallık testi ve bileşik sayıları bölmek için Pollard-Rho kullanır. Ardışık iki sayı aralarında asal olduğundan, bu iki sayıyı ayrı ayrı ayırıp sonuçları birleştirmek hem doğal hem de verimlidir.
Asal üslerden başlayarak özyinelemeli bir DFS, \(P=m(m+1)\)'in bütün bölenlerini üretir. Yalnızca \(u\le\sqrt{P}\) adayları incelenir; çünkü diğer eş bölen doğrudan \(v=P/u\) olur. Her aday için kod şu iki koşulu test eder:
$$u+v\equiv 1\pmod{2},\qquad v>u+1.$$
İki testi de geçen en büyük \(u\) seçilir; sonra kapalı formüllerle yeni \(n\) ve \(w\) hesaplanır.
Toplam arama konumu \(w\) kadar artırılır ve güncel üçgensel indeks \(n\) ile değiştirilir. Bu yüzden program başarısız denemeleri tek tek gezmez; doğrudan bir vuruştan ötekine sıçrar. C++, Python ve Java sürümlerinin matematiği aynıdır; sadece geniş tamsayıları ele alış biçimleri değişir. Üçü de ortak bir doğrulama noktası kullanır: 10. vuruşun konumu \(2964\) olur ve bu adım \(T_{1696}=1{,}439{,}056\) değerine ulaşır.
\(H\) adet vuruş isteniyorsa toplam süre \(H-1\) geçişin toplamıdır. Bir geçişte iki ardışık sayının çarpanlara ayrılması ve \(P\)'nin bölenlerinin üretilmesi gerekir. \(P\)'nin bölen sayısı \(\tau(P)\) ise DFS bölümü \(O(\tau(P))\) maliyetlidir; çünkü her bölen en fazla bir kez oluşturulur.
Daha pahalı kısım tam sayı çarpanlara ayırmadır. Pollard-Rho rastgeleleştirilmiş bir yöntem olduğu için burada en anlamlı ifade pratik maliyettir: gerekli 70. vuruş için yalnızca az sayıda 64 bit ayırma işlemi yeterli olur. Bellek kullanımı küçüktür; asal üs tablosu, özyineleme yığını ve \(P\), \(\sqrt{P}\), \(n\), \(w\) gibi birkaç geniş tamsayı dışında büyük yapı tutulmaz.
Sea \(T_r=\frac{r(r+1)}2\) el \(r\)-ésimo número triangular, con \(T_0=0\). Las implementaciones empiezan en \(T_2=3\) y luego buscan repetidamente una identidad no trivial de la forma
$$T_n-T_w=T_m,$$
con \(n>m\) y \(w>0\). En cada acierto se elige el menor índice posterior \(n\), se suma el desplazamiento asociado \(w\) a la posición acumulada de búsqueda, y después se reemplaza \(m\) por \(n\). Por eso la salida pedida es la posición acumulada del acierto número 70, no el valor triangular alcanzado en ese paso.
Una búsqueda ingenua probaría muchos pares \((n,w)\) para cada estado actual. Las soluciones locales evitan esa exploración completa convirtiendo la condición triangular en un problema de divisores de \(m(m+1)\). Así, cada transición se reduce a factorizar dos enteros consecutivos, enumerar divisores y saltar directamente al siguiente estado válido.
Partimos de
$$T_n-T_w=\frac{n(n+1)-w(w+1)}2=T_m=\frac{m(m+1)}2.$$
Al multiplicar por 2 y factorizar el lado izquierdo obtenemos
$$n(n+1)-w(w+1)=(n-w)(n+w+1)=m(m+1).$$
Definimos
$$P=m(m+1),\qquad u=n-w,\qquad v=n+w+1.$$
Entonces cada acierto no trivial corresponde a un par de divisores
$$uv=P.$$
Además, como
$$u+v=2n+1,$$
la suma \(u+v\) tiene que ser impar. Y a la inversa, cualquier par de divisores con suma impar permite reconstruir \(n\) y \(w\) como enteros.
Resolver el sistema lineal da
$$n=\frac{u+v-1}{2},\qquad w=\frac{v-u-1}{2}.$$
La condición \(w>0\) equivale exactamente a
$$v>u+1.$$
Esto excluye el par \((u,v)=(m,m+1)\), que siempre existe pero solo produce \(n=m,\ w=0\), es decir, la identidad trivial \(T_m-T_0=T_m\). El algoritmo quiere el siguiente acierto real, no esa repetición inmediata.
Para \(P\) fijo y \(u\le\sqrt{P}\), se cumple \(v=P/u\), luego
$$n(u)=\frac{u+P/u-1}{2}.$$
En el intervalo \(1\le u\le\sqrt{P}\), al crecer \(u\) disminuye \(P/u\), y por tanto también disminuye \(n(u)\). Así, el siguiente índice triangular se obtiene eligiendo el mayor divisor admisible \(u\). Eso es exactamente lo que conserva la búsqueda en profundidad sobre los divisores.
Otra simplificación importante es
$$\gcd(m,m+1)=1.$$
Por eso las implementaciones factoran \(m\) y \(m+1\) por separado y luego fusionan los exponentes primos, en vez de atacar directamente el producto completo \(P\).
Si \(m=6\), entonces
$$T_6=21,\qquad P=6\cdot 7=42.$$
Los pares de divisores con \(u\le\sqrt{42}\) son
$$ (1,42),\ (2,21),\ (3,14),\ (6,7). $$
Todos tienen suma impar, pero \((6,7)\) da \(w=0\) y por eso representa el caso trivial. Entre los restantes, el mayor \(u\) admisible es \(u=3\), con \(v=14\). Entonces
$$n=\frac{3+14-1}{2}=8,\qquad w=\frac{14-3-1}{2}=5.$$
En efecto,
$$T_8-T_5=36-15=21=T_6.$$
Si se eligieran \((2,21)\) o \((1,42)\), aparecerían representaciones posteriores como \(T_{11}-T_9\) o \(T_{21}-T_{20}\). La lógica del programa es quedarse con la más cercana, o sea \(n=8\).
Cada iteración empieza con el índice triangular actual \(m\). Las implementaciones usan Miller-Rabin determinista para entradas de 64 bits y Pollard-Rho para partir compuestos. Como \(m\) y \(m+1\) son coprimos, factorizar ambos por separado es natural y eficiente.
Con los factores primos disponibles, una DFS recursiva genera todos los divisores \(u\) de \(P=m(m+1)\). Solo hacen falta los divisores hasta \(\sqrt{P}\), porque el compañero es \(v=P/u\). Para cada candidato, el código comprueba
$$u+v\equiv 1\pmod{2},\qquad v>u+1.$$
El mejor candidato es simplemente el mayor \(u\) que supera ambos filtros. A partir de él se calculan \(n\) y \(w\) con las fórmulas cerradas derivadas antes.
La posición acumulada aumenta en \(w\) y el nuevo estado pasa a ser \(n\). De esta manera el programa no barre candidatos fallidos uno por uno, sino que salta directamente de un acierto al siguiente. Las versiones en C++, Python y Java siguen exactamente la misma matemática; solo cambian los detalles de tipos enteros y aritmética amplia. Todas verifican además el mismo punto de control: el décimo acierto aparece en la posición \(2964\) y llega a \(T_{1696}=1{,}439{,}056\).
Si se necesitan \(H\) aciertos, el trabajo total es la suma de \(H-1\) transiciones. En una transición se factorizan dos enteros consecutivos y luego se enumeran los divisores de \(P\). Si \(\tau(P)\) es el número de divisores de \(P=m(m+1)\), la parte de DFS cuesta \(O(\tau(P))\), porque cada divisor se genera una sola vez.
La parte menos regular es la factorización entera. Pollard-Rho es aleatorio, así que la descripción más honesta es práctica: el tiempo está dominado por unas pocas factorizaciones de 64 bits y resulta suficiente para alcanzar el acierto 70 con holgura. El uso de memoria es pequeño: un mapa de exponentes primos, la pila recursiva de la DFS y unas pocas variables enteras grandes para \(P\), \(\sqrt{P}\), \(n\) y \(w\).
设 \(T_r=\frac{r(r+1)}2\) 为第 \(r\) 个三角数，并约定 \(T_0=0\)。这些实现从 \(T_2=3\) 开始，之后不断寻找下一条非平凡恒等式
$$T_n-T_w=T_m,$$
其中 \(n>m\) 且 \(w>0\)。每找到一次命中，就选取满足条件的最小后继下标 \(n\)，把对应的偏移量 \(w\) 加到累计搜索位置上，再把当前状态更新为 \(m\leftarrow n\)。因此程序真正要求的是第 70 次命中的累计位置，而不是第 70 次出现时的三角数值本身。
如果直接枚举所有可能的 \((n,w)\)，每一步都要做大量无效检查。局部解法的关键是把三角数差值条件改写成 \(m(m+1)\) 的因子问题。这样每一步都变成了三个明确阶段：分解两个相邻整数，枚举乘积的约数，然后直接跳到下一个有效命中点。
从
$$T_n-T_w=\frac{n(n+1)-w(w+1)}2=T_m=\frac{m(m+1)}2$$
出发，两边乘以 2 后可得
$$n(n+1)-w(w+1)=(n-w)(n+w+1)=m(m+1).$$
记
$$P=m(m+1),\qquad u=n-w,\qquad v=n+w+1.$$
于是每一个非平凡命中都对应于一个约数对
$$uv=P.$$
又因为
$$u+v=2n+1,$$
所以 \(u+v\) 必须是奇数。反过来，只要 \(u\) 与 \(v\) 是 \(P\) 的约数且和为奇数，就能恢复出整数 \(n\) 和 \(w\)。
联立方程直接得到
$$n=\frac{u+v-1}{2},\qquad w=\frac{v-u-1}{2}.$$
这里 \(w>0\) 与
$$v>u+1$$
完全等价。这个条件正好排除了始终存在的平凡约数对 \((u,v)=(m,m+1)\)，因为它只会给出 \(n=m,\ w=0\)，也就是平凡恒等式 \(T_m-T_0=T_m\)。程序要找的是下一次真正的再出现，而不是当前状态本身。
当 \(P\) 固定且 \(u\le\sqrt{P}\) 时，有 \(v=P/u\)，于是
$$n(u)=\frac{u+P/u-1}{2}.$$
在区间 \(1\le u\le\sqrt{P}\) 上，\(u\) 变大时 \(P/u\) 变小，因此 \(n(u)\) 也随之减小。换句话说，想要得到“最近的下一次命中”，就必须选取不超过 \(\sqrt{P}\) 的最大可行约数 \(u\)。这正是深度优先约数枚举在维护的目标。
还有一个很重要的化简是
$$\gcd(m,m+1)=1.$$
因此实现并不直接分解整个 \(P\)，而是先分别分解 \(m\) 与 \(m+1\)，再把素因子指数合并起来。
取 \(m=6\)，则
$$T_6=21,\qquad P=6\cdot 7=42.$$
满足 \(u\le\sqrt{42}\) 的约数对为
$$ (1,42),\ (2,21),\ (3,14),\ (6,7). $$
这四对的和都是奇数，但 \((6,7)\) 会产生 \(w=0\)，所以只是平凡情形。剩下的可行候选里，最大的 \(u\) 是 \(3\)，对应 \(v=14\)。于是
$$n=\frac{3+14-1}{2}=8,\qquad w=\frac{14-3-1}{2}=5.$$
验证可知
$$T_8-T_5=36-15=21=T_6.$$
如果选 \((2,21)\) 或 \((1,42)\)，也能得到正确表示，但对应的是更靠后的命中，比如 \(T_{11}-T_9\) 或 \(T_{21}-T_{20}\)。程序需要的是最近的一次，所以保留 \(n=8\)。
每次迭代都从当前下标 \(m\) 开始。实现使用适用于 64 位范围的确定性 Miller-Rabin 素性测试，并用 Pollard-Rho 拆分合数。由于连续整数互素，分别分解 \(m\) 和 \(m+1\) 再合并结果，比直接处理整个乘积更自然也更高效。
得到素因子分解后，递归 DFS 会生成 \(P=m(m+1)\) 的所有约数 \(u\)。只需要检查 \(u\le\sqrt{P}\) 的一半，因为另一半可以由 \(v=P/u\) 自动得到。对每个候选，代码检查前面推导出的两个条件：
$$u+v\equiv 1\pmod{2},\qquad v>u+1.$$
通过这两个条件的最大 \(u\) 就是最佳选择。随后用封闭公式把它转回新的 \((w,n)\) 状态。
累计搜索位置增加 \(w\)，当前三角数下标更新为 \(n\)。这样程序完全不需要逐项扫描失败情况，而是直接从一个命中跳到下一个命中。C++、Python 和 Java 三个版本使用同一套数学逻辑，只是在宽整数表示上有所区别。它们还共享一个验证点：第 10 次命中的累计位置是 \(2964\)，对应的三角数为 \(T_{1696}=1{,}439{,}056\)。
若需要 \(H\) 次命中，总工作量就是 \(H-1\) 次状态转移的总和。一次转移包括对两个相邻整数做因式分解，以及枚举 \(P=m(m+1)\) 的约数。若 \(\tau(P)\) 表示 \(P\) 的约数个数，那么 DFS 部分的代价是 \(O(\tau(P))\)，因为每个约数只会生成一次。
更难精确刻画的是因式分解本身。Pollard-Rho 带有随机性，因此这里更适合给出实践层面的结论：运行时间主要由少量 64 位整数分解决定，而这对第 70 次命中已经足够快。内存占用很小，只需保存素因子指数表、DFS 调用栈，以及若干个用于存放 \(P\)、\(\sqrt{P}\)、\(n\)、\(w\) 的宽整数变量。
Пусть \(T_r=\frac{r(r+1)}2\) обозначает \(r\)-е треугольное число, причём \(T_0=0\). Реализации стартуют с \(T_2=3\) и далее многократно ищут нетривиальное равенство
$$T_n-T_w=T_m,$$
где \(n>m\) и \(w>0\). На каждом попадании выбирается наименьший возможный более поздний индекс \(n\), связанный с ним сдвиг \(w\) прибавляется к накопленной позиции поиска, после чего текущее состояние заменяется на \(m\leftarrow n\). Поэтому требуется не значение 70-го треугольного числа в цепочке, а накопленная позиция 70-го попадания.
Прямой перебор пар \((n,w)\) быстро становится бесполезным. Локальные решения обходят это за счёт переписывания условия попадания как задачи о делителях числа \(m(m+1)\). В результате каждый шаг сводится к факторизации двух соседних чисел, перечислению делителей их произведения и мгновенному переходу к следующему допустимому состоянию.
Начинаем с равенства
$$T_n-T_w=\frac{n(n+1)-w(w+1)}2=T_m=\frac{m(m+1)}2.$$
После умножения на 2 и факторизации получаем
$$n(n+1)-w(w+1)=(n-w)(n+w+1)=m(m+1).$$
Обозначим
$$P=m(m+1),\qquad u=n-w,\qquad v=n+w+1.$$
Тогда каждое нетривиальное попадание соответствует паре делителей
$$uv=P.$$
Поскольку
$$u+v=2n+1,$$
сумма \(u+v\) обязана быть нечётной. И наоборот, любая пара делителей \(P\) с нечётной суммой позволяет восстановить целые \(n\) и \(w\).
Из линейной системы сразу следует
$$n=\frac{u+v-1}{2},\qquad w=\frac{v-u-1}{2}.$$
Условие \(w>0\) в точности эквивалентно
$$v>u+1.$$
Именно оно отбрасывает всегда существующую пару \((u,v)=(m,m+1)\), которая даёт только \(n=m,\ w=0\), то есть тривиальное равенство \(T_m-T_0=T_m\). Алгоритм ищет следующее реальное появление, а не этот базовый случай.
При фиксированном \(P\) и \(u\le\sqrt{P}\) имеем \(v=P/u\), поэтому
$$n(u)=\frac{u+P/u-1}{2}.$$
На отрезке \(1\le u\le\sqrt{P}\) функция \(n(u)\) убывает при росте \(u\). Следовательно, ближайшее следующее попадание получается при выборе максимального допустимого делителя \(u\), не превосходящего \(\sqrt{P}\). Именно этот максимум и поддерживает перебор делителей.
Дополнительное упрощение даёт равенство
$$\gcd(m,m+1)=1.$$
Поэтому реализации факторизуют \(m\) и \(m+1\) отдельно и только потом объединяют показатели простых множителей.
Пусть \(m=6\). Тогда
$$T_6=21,\qquad P=6\cdot 7=42.$$
Пары делителей с \(u\le\sqrt{42}\) таковы:
$$ (1,42),\ (2,21),\ (3,14),\ (6,7). $$
У всех сумма нечётна, но пара \((6,7)\) даёт \(w=0\), а значит является только тривиальным случаем. Среди оставшихся наибольший допустимый делитель равен \(u=3\), откуда \(v=14\). Тогда
$$n=\frac{3+14-1}{2}=8,\qquad w=\frac{14-3-1}{2}=5.$$
И действительно,
$$T_8-T_5=36-15=21=T_6.$$
Пары \((2,21)\) и \((1,42)\) тоже дают верные представления, но уже более поздние, например \(T_{11}-T_9\) или \(T_{21}-T_{20}\). Алгоритм оставляет ближайший вариант \(n=8\).
Каждая итерация начинается с текущего индекса \(m\). Для проверки простоты используется детерминированный набор оснований Миллера-Рабина для 64-битного диапазона, а для разбиения составных чисел применяется алгоритм Полларда rho. Так как соседние числа взаимно просты, раздельная факторизация \(m\) и \(m+1\) здесь особенно удобна.
После получения простых множителей рекурсивный DFS перечисляет все делители \(u\) числа \(P=m(m+1)\). Достаточно рассматривать только \(u\le\sqrt{P}\), потому что второй делитель всегда равен \(v=P/u\). Для каждого кандидата код проверяет условия
$$u+v\equiv 1\pmod{2},\qquad v>u+1.$$
Лучшая пара определяется очень просто: берётся максимальный \(u\), прошедший оба фильтра. Затем из него по замкнутым формулам вычисляются \(n\) и \(w\).
Накопленная позиция увеличивается на \(w\), а текущий индекс треугольного числа заменяется на \(n\). Благодаря этому программа не просматривает длинные серии неудачных кандидатов, а сразу прыгает к следующему попаданию. Реализации на C++, Python и Java используют одну и ту же математику; отличаются только детали работы с широкими целыми типами. Все они проверяют общий контрольный пример: десятое попадание имеет накопленную позицию \(2964\) и приводит к \(T_{1696}=1{,}439{,}056\).
Если требуется \(H\) попаданий, общая работа равна сумме \(H-1\) переходов. Один переход включает факторизацию двух соседних чисел и перечисление делителей числа \(P\). Если \(\tau(P)\) обозначает количество делителей \(P=m(m+1)\), то часть с DFS имеет стоимость \(O(\tau(P))\), потому что каждый делитель генерируется один раз.
Менее регулярна именно факторизация. Алгоритм Pollard-Rho рандомизирован, поэтому здесь естественнее говорить о практической, а не жёсткой худшей оценке: время определяется несколькими факторизациями 64-битных чисел и этого более чем достаточно для 70-го попадания. Память остаётся небольшой, поскольку хранятся лишь таблица простых множителей, стек рекурсии и несколько широких целых переменных для \(P\), \(\sqrt{P}\), \(n\) и \(w\).
لنكتب العدد المثلثي رقم \(r\) على الصورة \(T_r=\frac{r(r+1)}2\)، مع الاتفاق على أن \(T_0=0\). تبدأ التطبيقات من \(T_2=3\)، ثم تبحث مرارًا عن علاقة غير تافهة من الشكل
$$T_n-T_w=T_m,$$
حيث \(n>m\) و\(w>0\). عند كل إصابة تُختار أصغر قيمة لاحقة ممكنة لـ \(n\)، ويُضاف الإزاحة المقابلة \(w\) إلى موضع البحث التراكمي، ثم تُستبدل الحالة الحالية بـ \(m\leftarrow n\). لذلك فالمخرج المطلوب هو الموضع التراكمي للإصابة السبعين، وليس قيمة العدد المثلثي التي نصل إليها في تلك الخطوة.
البحث المباشر عن الأزواج \((n,w)\) يضيع وقتًا كبيرًا في محاولات فاشلة. الحلول المحلية تتجاوز ذلك بتحويل شرط ظهور العدد المثلثي إلى مسألة قواسم للعدد \(m(m+1)\). وهكذا تتحول كل نقلة إلى: تحليل عددين متتاليين إلى عوامل أولية، ثم تعداد القواسم، ثم القفز مباشرة إلى الحالة الصحيحة التالية.
نبدأ من الهوية
$$T_n-T_w=\frac{n(n+1)-w(w+1)}2=T_m=\frac{m(m+1)}2.$$
وبعد الضرب في 2 وتحليل الطرف الأيسر نحصل على
$$n(n+1)-w(w+1)=(n-w)(n+w+1)=m(m+1).$$
لنعرّف
$$P=m(m+1),\qquad u=n-w,\qquad v=n+w+1.$$
عندئذٍ تصبح كل إصابة غير تافهة مكافئة لزوج قواسم يحقق
$$uv=P.$$
ولدينا أيضًا
$$u+v=2n+1,$$
ولذلك يجب أن يكون \(u+v\) عددًا فرديًا. وبالعكس، كل زوج قواسم لمقدار \(P\) مجموعهما فردي يعيد بناء قيم صحيحة لكل من \(n\) و\(w\).
بحل المعادلتين الخطيّتين نحصل مباشرة على
$$n=\frac{u+v-1}{2},\qquad w=\frac{v-u-1}{2}.$$
والشرط \(w>0\) يكافئ تمامًا
$$v>u+1.$$
هذا الشرط يستبعد الزوج \((u,v)=(m,m+1)\) الموجود دائمًا، لأنه لا يعطي إلا \(n=m\) و\(w=0\)، أي الهوية التافهة \(T_m-T_0=T_m\). المطلوب في المسألة هو الظهور الحقيقي التالي، لا هذا التمثيل الابتدائي.
عند تثبيت \(P\) واشتراط \(u\le\sqrt{P}\) يكون \(v=P/u\)، ومن ثم
$$n(u)=\frac{u+P/u-1}{2}.$$
على المجال \(1\le u\le\sqrt{P}\)، كلما ازداد \(u\) تناقصت \(P/u\)، وبالتالي تتناقص \(n(u)\) أيضًا. إذًا أقرب إصابة لاحقة تُستخرج من أكبر قاسم صالح \(u\) لا يتجاوز \(\sqrt{P}\). وهذا هو بالضبط ما تحتفظ به عملية تعداد القواسم.
كما أن هناك تبسيطًا مهمًا آخر:
$$\gcd(m,m+1)=1.$$
ولهذا تُحلَّل \(m\) و\(m+1\) كلٌّ على حدة ثم تُدمج الأسس الأولية، بدل محاولة تحليل حاصل الضرب الكامل مباشرة.
إذا أخذنا \(m=6\)، فإن
$$T_6=21,\qquad P=6\cdot 7=42.$$
وأزواج القواسم التي تحقق \(u\le\sqrt{42}\) هي
$$ (1,42),\ (2,21),\ (3,14),\ (6,7). $$
مجموع كل زوج فردي، لكن الزوج \((6,7)\) يعطي \(w=0\)، ولذلك فهو الحالة التافهة فقط. بين الأزواج المتبقية يكون أكبر \(u\) صالح هو \(u=3\)، ومعه \(v=14\). وعندها نحصل على
$$n=\frac{3+14-1}{2}=8,\qquad w=\frac{14-3-1}{2}=5.$$
وبالفعل
$$T_8-T_5=36-15=21=T_6.$$
ولو اخترنا \((2,21)\) أو \((1,42)\) لحصلنا على تمثيلات صحيحة أيضًا، لكنها أبعد زمنيًا مثل \(T_{11}-T_9\) أو \(T_{21}-T_{20}\). منطق الخوارزمية هو أخذ أقرب ظهور تالٍ، ولذلك تحتفظ بـ \(n=8\).
تبدأ كل دورة بالقيمة الحالية \(m\). تستخدم التطبيقات اختبار Miller-Rabin الحتمي ضمن مجال 64 بت، وتستخدم Pollard-Rho لتجزئة الأعداد المركبة. وبما أن العددين المتتاليين متباعدان نسبيًا، فإن تحليل كل واحد منهما على حدة ثم دمج النتائج هو الخيار الطبيعي والأسرع.
بعد معرفة العوامل الأولية، يولّد بحث عمق تكراري جميع القواسم \(u\) للعدد \(P=m(m+1)\). ولا يلزم فحص إلا القيم التي تحقق \(u\le\sqrt{P}\)، لأن القاسم المقابل هو دائمًا \(v=P/u\). لكل مرشح تختبر الشيفرة الشرطين
$$u+v\equiv 1\pmod{2},\qquad v>u+1.$$
ثم تختار أكبر \(u\) يمر بهذين الاختبارين، وتحوّل هذا الزوج بعد ذلك إلى القيمتين الجديدتين \(n\) و\(w\) بواسطة الصيغ المغلقة.
يُزاد موضع البحث التراكمي بمقدار \(w\)، وتُحدَّث الحالة الحالية إلى \(n\). بهذه الطريقة لا تمر الشيفرة على محاولات فاشلة واحدةً واحدة، بل تنتقل مباشرة من إصابة إلى التي تليها. وتستخدم نسخ C++ وPython وJava الرياضيات نفسها تمامًا، مع اختلافات طفيفة فقط في تمثيل الأعداد الكبيرة. كما تتحقق كلها من نقطة فحص مشتركة: الإصابة العاشرة تقع عند الموضع \(2964\) وتصل إلى \(T_{1696}=1{,}439{,}056\).
إذا كنا نحتاج إلى \(H\) إصابة، فإن الكلفة الكلية هي مجموع كلفة \(H-1\) انتقالات. كل انتقال يتطلب تحليل عددين متتاليين إلى عوامل أولية ثم تعداد قواسم \(P\). وإذا رمزنا بعدد القواسم بالرمز \(\tau(P)\)، فإن جزء DFS يكلف \(O(\tau(P))\) لأن كل قاسم يُولَّد مرة واحدة فقط.
أما الجزء الأقل انتظامًا فهو التحليل إلى عوامل أولية نفسه. خوارزمية Pollard-Rho عشوائية، لذا فالوصف الأكثر دقة هنا هو الوصف العملي: الزمن تهيمن عليه بضع عمليات تحليل ضمن مجال 64 بت، وهذا كافٍ جدًا للوصول إلى الإصابة السبعين. أما الذاكرة فتبقى صغيرة، لأنها تقتصر على جدول للعوامل الأولية، ومكدس الاستدعاء التكراري، وعدة متغيرات عددية واسعة من أجل \(P\) و\(\sqrt{P}\) و\(n\) و\(w\).