For each integer \(n\ge 3\), the quantity \(T(n)\) is the sum of all positive offsets \(k\) that survive the divisor reformulation used by the implementations. If we write the corresponding endpoint as \(D=n+k\), then the admissible values are exactly those divisors of \(n(n-1)\) whose complementary factor has the opposite parity. Define
$$E(n)=\left\{D>n: D\mid n(n-1),\ D\not\equiv \frac{n(n-1)}{D}\pmod 2\right\}.$$
Then
$$T(n)=\sum_{D\in E(n)}(D-n),\qquad U(N)=\sum_{n=3}^{N}T(n).$$
The brute-force view would search through many possible offsets \(k\). The useful number-theoretic view is that the parity restriction becomes very simple after separating the full power of \(2\) from \(n(n-1)\).
The implementations are built around a divisor description of the admissible endpoints. Once that description is written down, every contribution comes from the odd part of \(n(n-1)\).
Write the positive offset as \(k=D-n\), so \(D=n+k\) and \(D>n\). The admissible values are precisely those for which \(D\) appears in a factor pair
$$D\,Q=n(n-1)$$
with opposite parity:
$$D\not\equiv Q\pmod 2.$$
For every such divisor \(D\), the contribution to \(T(n)\) is just the excess \(D-n\). Therefore the entire problem becomes a structured divisor sum over \(n(n-1)\).
Write
$$n(n-1)=2^t m,\qquad m\text{ odd}.$$
Every divisor of \(n(n-1)\) can be written uniquely as
$$D=2^j d,\qquad 0\le j\le t,\qquad d\mid m.$$
Its complementary factor is then
$$Q=2^{t-j}\frac{m}{d}.$$
The parity condition says that exactly one of \(D\) and \(Q\) must be odd. That happens only in the two extreme cases \(j=0\) or \(j=t\). So the admissible endpoints are exactly
$$D=d\qquad\text{or}\qquad D=2^t d\qquad(d\mid m).$$
All intermediate choices \(0<j<t\) make both factors even, so they never contribute.
Factor the odd kernel as
$$m=\prod_{r=1}^{s} p_r^{e_r}.$$
Then every odd divisor of \(m\) has the form
$$d=\prod_{r=1}^{s} p_r^{\alpha_r},\qquad 0\le \alpha_r\le e_r.$$
So once the prime exponents of \(m\) are known, generating all admissible odd divisors is a standard exponent-recursion over \(\alpha_1,\dots,\alpha_s\). This is why the implementations spend their effort on fast factorization and clean divisor enumeration rather than on testing offsets directly.
Each odd divisor \(d\mid m\) produces two candidate endpoints, \(d\) and \(2^t d\). Only values larger than \(n\) generate a positive offset, so the contribution formula is
$$T(n)=\sum_{d\mid m}\left(\max\{d-n,0\}+\max\{2^t d-n,0\}\right).$$
This formula is equivalent to the earlier definition using \(E(n)\), but it is far more efficient because the loop now runs only over divisors of the odd part \(m\).
Here
$$12\cdot 11=132=2^2\cdot 33,$$
so \(t=2\) and \(m=33\). The odd divisors of \(33\) are
$$1,\ 3,\ 11,\ 33.$$
By Step 2, the admissible endpoints are the odd divisors themselves and the same divisors multiplied by \(2^t=4\):
$$1,\ 3,\ 11,\ 33,\qquad 4,\ 12,\ 44,\ 132.$$
Only the endpoints exceeding \(12\) contribute, namely \(33\), \(44\), and \(132\). Therefore
$$T(12)=(33-12)+(44-12)+(132-12)=21+32+120=173.$$
The divisors \(22\) and \(66\) do not appear, because they would correspond to the intermediate two-adic choice \(j=1\); their complementary factors are also even, so the parity condition fails.
After computing \(T(n)\) for one value of \(n\), the final answer is simply
$$U(N)=\sum_{n=3}^{N}T(n).$$
There is no need for a separate closed form. The important reduction is the divisor formula for each \(T(n)\), because that is what makes the range up to \(1{,}234{,}567\) practical.
The C++, Python, and Java implementations all follow the same algorithm. First, they build a smallest-prime-factor table up to \(N\), which makes repeated factorizations cheap. Then, for each \(n\), they remove all factors of \(2\) from \(n\) and \(n-1\), so the total removed exponent is exactly the \(t\) in
$$n(n-1)=2^t m.$$
The remaining odd parts are factored with the precomputed table, and their prime exponents are merged to obtain the factorization of \(m\). A recursive divisor generator then visits every odd divisor \(d\mid m\) exactly once. For each such \(d\), the implementation checks the two admissible endpoints \(d\) and \(2^t d\); whenever an endpoint exceeds \(n\), it adds the excess over \(n\) to the running total for \(T(n)\). Finally, it accumulates those values from \(n=3\) up to \(N\) to produce \(U(N)\).
Building the smallest-prime-factor table costs \(O(N\log\log N)\) time and \(O(N)\) memory. For a fixed \(n\), stripping powers of two is negligible, factoring the odd parts is proportional to the number of prime factors encountered, and the divisor-generation step visits exactly \(\tau(m)\) odd divisors, where \(m=\operatorname{odd}(n(n-1))\). Thus the natural overall bound is
$$O\!\left(N\log\log N+\sum_{n=3}^{N}\tau\!\bigl(\operatorname{odd}(n(n-1))\bigr)\right),$$
with \(O(N)\) memory for the sieve plus a small amount of recursion state for the current factorization.
Für jedes ganze \(n\ge 3\) ist \(T(n)\) die Summe aller positiven Verschiebungen \(k\), die in der Divisorformulierung der Implementierungen übrig bleiben. Schreibt man den zugehörigen Endpunkt als \(D=n+k\), dann sind genau diejenigen Werte zulässig, bei denen \(D\) ein Teiler von \(n(n-1)\) ist und der komplementäre Faktor die entgegengesetzte Parität hat. Definiere
$$E(n)=\left\{D>n: D\mid n(n-1),\ D\not\equiv \frac{n(n-1)}{D}\pmod 2\right\}.$$
Dann gilt
$$T(n)=\sum_{D\in E(n)}(D-n),\qquad U(N)=\sum_{n=3}^{N}T(n).$$
Eine naive Suche über viele mögliche Verschiebungen \(k\) wäre viel zu langsam. Die entscheidende Beobachtung ist, dass die Paritätsbedingung nach dem Herausziehen der gesamten Zweierpotenz aus \(n(n-1)\) sehr einfach wird.
Die Implementierungen beruhen auf einer Teilerbeschreibung der zulässigen Endpunkte. Sobald diese Beschreibung steht, kommt jeder Beitrag nur noch aus dem ungeraden Kern von \(n(n-1)\).
Schreibe die positive Verschiebung als \(k=D-n\), also \(D=n+k\) mit \(D>n\). Die zulässigen Werte sind genau die Fälle, in denen \(D\) in einer Faktorzerlegung
$$D\,Q=n(n-1)$$
mit entgegengesetzter Parität auftritt:
$$D\not\equiv Q\pmod 2.$$
Zu jedem solchen Teiler \(D\) gehört der Beitrag \(D-n\). Damit wird das ganze Problem zu einer strukturierten Teilersumme über \(n(n-1)\).
Schreibe
$$n(n-1)=2^t m,\qquad m\text{ ungerade}.$$
Jeder Teiler von \(n(n-1)\) hat dann eindeutig die Form
$$D=2^j d,\qquad 0\le j\le t,\qquad d\mid m.$$
Der komplementäre Faktor ist
$$Q=2^{t-j}\frac{m}{d}.$$
Die Paritätsbedingung verlangt, dass genau einer der beiden Faktoren ungerade ist. Das passiert nur in den beiden Extremfällen \(j=0\) oder \(j=t\). Also sind die zulässigen Endpunkte genau
$$D=d\qquad\text{oder}\qquad D=2^t d\qquad(d\mid m).$$
Alle Zwischenwerte \(0<j<t\) machen beide Faktoren gerade und tragen deshalb nie bei.
Faktorisieren wir den ungeraden Kern als
$$m=\prod_{r=1}^{s} p_r^{e_r}.$$
Dann hat jeder ungerade Teiler von \(m\) die Form
$$d=\prod_{r=1}^{s} p_r^{\alpha_r},\qquad 0\le \alpha_r\le e_r.$$
Sobald die Primexponenten von \(m\) bekannt sind, kann man also alle zulässigen ungeraden Teiler durch eine Standard-Rekursion über die Exponenten \(\alpha_1,\dots,\alpha_s\) erzeugen. Genau deshalb investieren die Implementierungen ihre Arbeit in schnelle Faktorisierung und saubere Teilergenerierung statt in direkte Tests vieler Verschiebungen.
Jeder ungerade Teiler \(d\mid m\) liefert zwei mögliche Endpunkte, nämlich \(d\) und \(2^t d\). Nur Werte größer als \(n\) erzeugen eine positive Verschiebung, also lautet die Beitragsformel
$$T(n)=\sum_{d\mid m}\left(\max\{d-n,0\}+\max\{2^t d-n,0\}\right).$$
Diese Formel ist äquivalent zur früheren Definition mit \(E(n)\), aber deutlich effizienter, weil jetzt nur noch über die Teiler des ungeraden Teils \(m\) iteriert wird.
Hier gilt
$$12\cdot 11=132=2^2\cdot 33,$$
also \(t=2\) und \(m=33\). Die ungeraden Teiler von \(33\) sind
$$1,\ 3,\ 11,\ 33.$$
Nach Schritt 2 sind die zulässigen Endpunkte die ungeraden Teiler selbst und dieselben Teiler multipliziert mit \(2^t=4\):
$$1,\ 3,\ 11,\ 33,\qquad 4,\ 12,\ 44,\ 132.$$
Nur die Werte größer als \(12\) tragen bei, also \(33\), \(44\) und \(132\). Deshalb
$$T(12)=(33-12)+(44-12)+(132-12)=21+32+120=173.$$
Die Teiler \(22\) und \(66\) erscheinen nicht, denn sie würden der Zwischenwahl \(j=1\) entsprechen; ihre komplementären Faktoren sind ebenfalls gerade, also scheitert die Paritätsbedingung.
Ist \(T(n)\) für ein festes \(n\) berechnet, dann ist die Endsumme einfach
$$U(N)=\sum_{n=3}^{N}T(n).$$
Eine separate geschlossene Formel ist nicht nötig. Die entscheidende Reduktion ist die Teilerdarstellung jedes einzelnen \(T(n)\), denn genau sie macht den Bereich bis \(1{,}234{,}567\) praktikabel.
Die C++-, Python- und Java-Implementierungen folgen demselben Algorithmus. Zuerst bauen sie eine Tabelle der kleinsten Primfaktoren bis \(N\) auf, damit wiederholte Faktorisierungen billig werden. Dann entfernen sie für jedes \(n\) alle Zweierfaktoren aus \(n\) und \(n-1\); die Summe der entfernten Exponenten ist genau das \(t\) aus
$$n(n-1)=2^t m.$$
Die verbleibenden ungeraden Teile werden mit der vorberechneten Tabelle faktorisiert, und ihre Primexponenten werden zusammengeführt, um die Faktorisierung von \(m\) zu erhalten. Ein rekursiver Teilergenerator besucht danach jeden ungeraden Teiler \(d\mid m\) genau einmal. Für jedes solche \(d\) prüft die Implementierung die beiden zulässigen Endpunkte \(d\) und \(2^t d\); überschreitet ein Endpunkt den Wert \(n\), wird der Überschuss über \(n\) zur laufenden Summe für \(T(n)\) addiert. Anschließend werden diese Werte von \(n=3\) bis \(N\) zu \(U(N)\) aufsummiert.
Der Aufbau der Tabelle der kleinsten Primfaktoren kostet \(O(N\log\log N)\) Zeit und \(O(N)\) Speicher. Für ein festes \(n\) ist das Entfernen der Zweierpotenzen vernachlässigbar, die Faktorisierung der ungeraden Teile ist proportional zur Anzahl der gefundenen Primfaktoren, und die Teilergenerierung besucht genau \(\tau(m)\) ungerade Teiler, wobei \(m=\operatorname{odd}(n(n-1))\) ist. Daher ergibt sich als natürliche Gesamtschranke
$$O\!\left(N\log\log N+\sum_{n=3}^{N}\tau\!\bigl(\operatorname{odd}(n(n-1))\bigr)\right),$$
bei \(O(N)\) Speicher für das Sieb plus einem kleinen Rekursionszustand für die aktuelle Faktorisierung.
Her \(n\ge 3\) için \(T(n)\), uygulamaların kullandığı bölen reformülasyonunda ayakta kalan bütün pozitif kaydırmaların \(k\) toplamıdır. İlgili uç noktayı \(D=n+k\) olarak yazarsak, geçerli değerler tam olarak \(n(n-1)\)'in böleni olan ve tamamlayıcı çarpanı ters pariteye sahip olan değerlerdir. Şunu tanımlayalım:
$$E(n)=\left\{D>n: D\mid n(n-1),\ D\not\equiv \frac{n(n-1)}{D}\pmod 2\right\}.$$
O zaman
$$T(n)=\sum_{D\in E(n)}(D-n),\qquad U(N)=\sum_{n=3}^{N}T(n).$$
Ham kuvvet yaklaşımı çok sayıda olası \(k\) değerini denemek zorunda kalır ve gerçek sınır için uygun değildir. Asıl numara, \(n(n-1)\)'deki tüm \(2\) kuvvetleri ayrıldıktan sonra parite koşulunun çok sade hale gelmesidir.
Uygulamalar, geçerli uç noktaları bölenler üzerinden tarif eden bir görüşe dayanır. Bu tarif yazıldıktan sonra her katkı yalnızca \(n(n-1)\)'in tek kısmından gelir.
Pozitif kaydırmayı \(k=D-n\) şeklinde yazalım; burada \(D=n+k\) ve \(D>n\). Geçerli değerler tam olarak
$$D\,Q=n(n-1)$$
çarpan çiftinde yer alan ve karşı taraftaki çarpanla ters pariteye sahip olan \(D\) değerleridir:
$$D\not\equiv Q\pmod 2.$$
Böyle her \(D\) için \(T(n)\)'ye eklenen miktar sadece \(D-n\)'dir. Böylece problem, \(n(n-1)\) üzerinde düzenli bir bölen toplamına dönüşür.
Şöyle yazalım:
$$n(n-1)=2^t m,\qquad m\text{ tek}.$$
Bu durumda \(n(n-1)\)'in her böleni tekil olarak
$$D=2^j d,\qquad 0\le j\le t,\qquad d\mid m$$
şeklindedir. Tamamlayıcı çarpan ise
$$Q=2^{t-j}\frac{m}{d}$$
olur. Parite koşulu, bu iki çarpandan yalnızca birinin tek olmasını ister. Bu da sadece iki uç durumda mümkündür: \(j=0\) veya \(j=t\). Dolayısıyla geçerli uç noktalar tam olarak
$$D=d\qquad\text{veya}\qquad D=2^t d\qquad(d\mid m)$$
şeklindedir. Aradaki \(0<j<t\) seçimleri her iki çarpanı da çift yapar ve bu yüzden hiç katkı vermez.
Tek çekirdeği
$$m=\prod_{r=1}^{s} p_r^{e_r}$$
şeklinde çarpanlara ayıralım. O zaman \(m\)'in her tek böleni
$$d=\prod_{r=1}^{s} p_r^{\alpha_r},\qquad 0\le \alpha_r\le e_r$$
biçimindedir. Yani \(m\)'in asal üsleri bilindiğinde, tüm geçerli tek bölenler \(\alpha_1,\dots,\alpha_s\) üsleri üzerinde yapılan standart bir özyinelemeli dolaşım ile birer kez üretilebilir. Uygulamaların hızlı çarpanlara ayırma ve temiz bölen üretimine odaklanmasının sebebi budur.
Her \(d\mid m\) tek böleni iki aday uç nokta üretir: \(d\) ve \(2^t d\). Yalnızca \(n\)'den büyük olanlar pozitif bir kaydırma üretir. Bu yüzden katkı formülü
$$T(n)=\sum_{d\mid m}\left(\max\{d-n,0\}+\max\{2^t d-n,0\}\right)$$
olur. Bu ifade, \(E(n)\) ile verilen önceki tanımla tamamen eşdeğerdir; fakat artık döngü yalnızca \(m\)'in tek bölenleri üzerinde çalıştığı için çok daha verimlidir.
Burada
$$12\cdot 11=132=2^2\cdot 33,$$
yani \(t=2\) ve \(m=33\)'tür. \(33\)'ün tek bölenleri
$$1,\ 3,\ 11,\ 33$$
olur. Adım 2'ye göre geçerli uç noktalar bu bölenlerin kendileri ve \(2^t=4\) ile çarpılmış halleri olur:
$$1,\ 3,\ 11,\ 33,\qquad 4,\ 12,\ 44,\ 132.$$
\(12\)'den büyük olanlar yalnızca \(33\), \(44\) ve \(132\) olduğundan
$$T(12)=(33-12)+(44-12)+(132-12)=21+32+120=173.$$
\(22\) ve \(66\) bölenleri kullanılmaz; çünkü bunlar ara seçim olan \(j=1\)'e karşılık gelir ve tamamlayıcı çarpanları da çifttir. Dolayısıyla parite koşulu bozulur.
Sabit bir \(n\) için \(T(n)\) hesaplandıktan sonra nihai toplam
$$U(N)=\sum_{n=3}^{N}T(n)$$
şeklindedir. Ayrı bir kapalı form gerekmiyor. Kritik sadeleştirme, her \(T(n)\)'yi bölenler üzerinden yazabilmektir; pratikliği sağlayan şey tam olarak budur.
C++, Python ve Java uygulamaları aynı algoritmayı izler. Önce \(N\)'ye kadar en küçük asal çarpan tablosu hazırlanır; böylece tekrar tekrar çarpanlara ayırma ucuz hale gelir. Sonra her \(n\) için \(n\) ve \(n-1\) içindeki tüm \(2\) çarpanları çıkarılır; çıkarılan üslerin toplamı tam olarak
$$n(n-1)=2^t m$$
ayrımındaki \(t\)'dir. Geriye kalan tek parçalar önceden hazırlanmış tabloyla çarpanlara ayrılır ve üsler birleştirilerek \(m\)'in asal ayrışımı elde edilir. Ardından özyinelemeli bir bölen üreticisi, her \(d\mid m\) tek bölenini tam bir kez gezer. Her bölen için iki geçerli uç nokta olan \(d\) ve \(2^t d\) kontrol edilir; bir uç nokta \(n\)'den büyükse, \(n\)'i aşan miktar \(T(n)\)'nin biriken toplamına eklenir. Son olarak bu değerler \(n=3\)'ten \(N\)'ye kadar toplanarak \(U(N)\) elde edilir.
En küçük asal çarpan tablosunu kurmak \(O(N\log\log N)\) zaman ve \(O(N)\) bellek ister. Sabit bir \(n\) için iki kuvvetlerini ayırma maliyeti ihmal edilebilir düzeydedir; tek parçaların çarpanlara ayrılması karşılaşılan asal çarpan sayısıyla orantılıdır ve bölen üretimi tam olarak \(\tau(m)\) adet tek bölen ziyaret eder; burada \(m=\operatorname{odd}(n(n-1))\)'dir. Bu yüzden doğal toplam üst sınır
$$O\!\left(N\log\log N+\sum_{n=3}^{N}\tau\!\bigl(\operatorname{odd}(n(n-1))\bigr)\right)$$
olur. Bellek kullanımı, elek için \(O(N)\) ve güncel çarpanlaşma için küçük bir özyineleme durumudur.
Para cada entero \(n\ge 3\), la cantidad \(T(n)\) es la suma de todos los desplazamientos positivos \(k\) que sobreviven a la reformulación por divisores utilizada por las implementaciones. Si escribimos el extremo correspondiente como \(D=n+k\), los valores admisibles son exactamente aquellos divisores de \(n(n-1)\) cuyo factor complementario tiene paridad opuesta. Definimos
$$E(n)=\left\{D>n: D\mid n(n-1),\ D\not\equiv \frac{n(n-1)}{D}\pmod 2\right\}.$$
Entonces
$$T(n)=\sum_{D\in E(n)}(D-n),\qquad U(N)=\sum_{n=3}^{N}T(n).$$
Una búsqueda directa sobre muchos valores posibles de \(k\) sería demasiado lenta. La observación decisiva es que la condición de paridad se vuelve muy simple una vez separada la potencia completa de \(2\) en \(n(n-1)\).
Las implementaciones se apoyan en una descripción por divisores de los extremos válidos. Una vez escrita esa descripción, toda contribución procede únicamente de la parte impar de \(n(n-1)\).
Escribimos el desplazamiento positivo como \(k=D-n\), de modo que \(D=n+k\) y \(D>n\). Los valores admisibles son exactamente aquellos en los que \(D\) aparece en una factorización
$$D\,Q=n(n-1)$$
con paridad opuesta:
$$D\not\equiv Q\pmod 2.$$
Cada divisor \(D\) de este tipo aporta simplemente \(D-n\). Así, todo el problema se convierte en una suma estructurada sobre los divisores de \(n(n-1)\).
Escribimos
$$n(n-1)=2^t m,\qquad m\text{ impar}.$$
Cualquier divisor de \(n(n-1)\) se escribe de manera única como
$$D=2^j d,\qquad 0\le j\le t,\qquad d\mid m.$$
El factor complementario es
$$Q=2^{t-j}\frac{m}{d}.$$
La condición de paridad exige que exactamente uno de \(D\) y \(Q\) sea impar. Eso solo ocurre en los casos extremos \(j=0\) o \(j=t\). Por tanto, los extremos admisibles son exactamente
$$D=d\qquad\text{o}\qquad D=2^t d\qquad(d\mid m).$$
Todas las elecciones intermedias \(0<j<t\) hacen que ambos factores sean pares, así que nunca aportan nada.
Factorizamos el núcleo impar como
$$m=\prod_{r=1}^{s} p_r^{e_r}.$$
Entonces cada divisor impar de \(m\) tiene la forma
$$d=\prod_{r=1}^{s} p_r^{\alpha_r},\qquad 0\le \alpha_r\le e_r.$$
Una vez conocidos los exponentes primos de \(m\), generar todos los divisores impares admisibles es solo una recursión estándar sobre \(\alpha_1,\dots,\alpha_s\). Por eso las implementaciones concentran el trabajo en factorizar rápido y en generar divisores de forma ordenada, en lugar de probar desplazamientos uno por uno.
Cada divisor impar \(d\mid m\) produce dos extremos candidatos, \(d\) y \(2^t d\). Solo los valores mayores que \(n\) generan un desplazamiento positivo, de modo que
$$T(n)=\sum_{d\mid m}\left(\max\{d-n,0\}+\max\{2^t d-n,0\}\right).$$
Esta fórmula es equivalente a la definición anterior mediante \(E(n)\), pero resulta mucho más eficiente porque el recorrido solo se hace sobre los divisores de la parte impar \(m\).
Aquí
$$12\cdot 11=132=2^2\cdot 33,$$
de modo que \(t=2\) y \(m=33\). Los divisores impares de \(33\) son
$$1,\ 3,\ 11,\ 33.$$
Según el Paso 2, los extremos admisibles son esos divisores y los mismos divisores multiplicados por \(2^t=4\):
$$1,\ 3,\ 11,\ 33,\qquad 4,\ 12,\ 44,\ 132.$$
Solo contribuyen los que superan a \(12\), es decir, \(33\), \(44\) y \(132\). Por tanto,
$$T(12)=(33-12)+(44-12)+(132-12)=21+32+120=173.$$
Los divisores \(22\) y \(66\) no aparecen, porque corresponderían a la elección intermedia \(j=1\); sus factores complementarios también son pares y la condición de paridad falla.
Una vez calculado \(T(n)\) para un valor fijo de \(n\), la respuesta final es simplemente
$$U(N)=\sum_{n=3}^{N}T(n).$$
No hace falta una fórmula cerrada adicional. La reducción importante es la fórmula por divisores para cada \(T(n)\), porque eso es lo que vuelve práctico el rango hasta \(1{,}234{,}567\).
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Primero construyen una tabla del menor factor primo hasta \(N\), lo que abarata las factorizaciones repetidas. Después, para cada \(n\), eliminan todos los factores \(2\) de \(n\) y de \(n-1\); la suma de los exponentes extraídos es precisamente el \(t\) de
$$n(n-1)=2^t m.$$
Las partes impares restantes se factorizan con la tabla precomputada y sus exponentes se combinan para obtener la factorización de \(m\). Luego un generador recursivo de divisores visita cada divisor impar \(d\mid m\) exactamente una vez. Para cada \(d\), la implementación prueba los dos extremos admisibles \(d\) y \(2^t d\); cuando un extremo supera a \(n\), añade el exceso sobre \(n\) al acumulado de \(T(n)\). Finalmente suma esos valores desde \(n=3\) hasta \(N\) para producir \(U(N)\).
Construir la tabla del menor factor primo cuesta \(O(N\log\log N)\) en tiempo y \(O(N)\) en memoria. Para un \(n\) fijo, eliminar potencias de dos es despreciable, factorizar las partes impares es proporcional al número de factores primos encontrados, y la generación de divisores visita exactamente \(\tau(m)\) divisores impares, donde \(m=\operatorname{odd}(n(n-1))\). Por tanto, la cota natural total es
$$O\!\left(N\log\log N+\sum_{n=3}^{N}\tau\!\bigl(\operatorname{odd}(n(n-1))\bigr)\right),$$
con memoria \(O(N)\) para la criba más un pequeño estado recursivo para la factorización actual.
对每个整数 \(n\ge 3\)，量 \(T(n)\) 都可以理解为一批正偏移量 \(k\) 的总和。若把对应的端点写成 \(D=n+k\)，那么实现所使用的等价形式说明：只有当 \(D\) 是 \(n(n-1)\) 的一个因子，并且它的互补因子与它奇偶性相反时，这个端点才会产生贡献。定义
$$E(n)=\left\{D>n: D\mid n(n-1),\ D\not\equiv \frac{n(n-1)}{D}\pmod 2\right\}.$$
于是
$$T(n)=\sum_{D\in E(n)}(D-n),\qquad U(N)=\sum_{n=3}^{N}T(n).$$
如果直接枚举大量可能的偏移量 \(k\)，在 \(N=1{,}234{,}567\) 时完全不可行。真正有效的观察是：把 \(n(n-1)\) 中完整的 \(2\) 的幂次剥离出来以后，奇偶性条件会变得非常简单，从而可以把问题压缩成对奇数核的因子枚举。
三种实现都基于同一个数论重写：先把可行端点写成 \(n(n-1)\) 的特殊因子，再把这些因子缩减为奇数部分的因子。这样一来，整个问题的核心就变成了“如何快速分解并枚举奇数核的所有因子”。
把正偏移量写成 \(k=D-n\)，也就是 \(D=n+k\)，并且 \(D>n\)。实现采用的可行性描述是：端点 \(D\) 必须落在某个分解
$$D\,Q=n(n-1)$$
中，而且 \(D\) 与互补因子 \(Q\) 的奇偶性相反：
$$D\not\equiv Q\pmod 2.$$
只要这样的 \(D\) 存在，它对应的贡献就只是超出 \(n\) 的那一段，也就是 \(D-n\)。因此 \(T(n)\) 本质上是一类带有奇偶性约束的因子和。
写成
$$n(n-1)=2^t m,\qquad m\text{ 为奇数}.$$
这样 \(n(n-1)\) 的任意一个因子都能唯一写成
$$D=2^j d,\qquad 0\le j\le t,\qquad d\mid m.$$
与之配对的互补因子则是
$$Q=2^{t-j}\frac{m}{d}.$$
现在奇偶性条件非常直观：在 \(D\) 和 \(Q\) 之间，必须恰好有一个是奇数。这只有在两种极端情况下才会发生。
当 \(j=0\) 时，\(D=d\) 是奇数，而 \(Q\) 带有全部的 \(2^t\)。
当 \(j=t\) 时，\(D=2^t d\) 带有全部的 \(2^t\)，而 \(Q=m/d\) 是奇数。
所以所有可行端点恰好是
$$D=d\qquad\text{或}\qquad D=2^t d\qquad(d\mid m).$$
任何中间选择 \(0<j<t\) 都会让 \(D\) 和 \(Q\) 同时为偶数，因此根本不满足条件。
把奇数核 \(m\) 分解为
$$m=\prod_{r=1}^{s} p_r^{e_r}.$$
那么 \(m\) 的任意奇因子都具有标准形式
$$d=\prod_{r=1}^{s} p_r^{\alpha_r},\qquad 0\le \alpha_r\le e_r.$$
这意味着，只要知道 \(m\) 的素因子指数，就可以通过对 \(\alpha_1,\dots,\alpha_s\) 做递归枚举，把所有奇因子 \(d\) 一次不漏地生成出来。实现中真正需要高效处理的部分也正是这里：快速分解，随后系统地遍历所有指数选择。
每个奇因子 \(d\mid m\) 会产生两个候选端点：\(d\) 和 \(2^t d\)。只有当端点大于 \(n\) 时，对应的偏移量 \(k=D-n\) 才是正的，所以贡献公式可以直接写成
$$T(n)=\sum_{d\mid m}\left(\max\{d-n,0\}+\max\{2^t d-n,0\}\right).$$
这与前面通过集合 \(E(n)\) 给出的定义完全等价，但计算上高效得多，因为循环对象已经从“所有可能端点”缩减成了“奇数核 \(m\) 的所有因子”。
先看一个能把奇偶性限制展示得很清楚的例子。这里有
$$12\cdot 11=132=2^2\cdot 33,$$
因此 \(t=2\)，\(m=33\)。\(33\) 的奇因子为
$$1,\ 3,\ 11,\ 33.$$
按照步骤 2，可行端点就是这些奇因子本身，以及它们乘上 \(2^t=4\) 之后得到的值：
$$1,\ 3,\ 11,\ 33,\qquad 4,\ 12,\ 44,\ 132.$$
其中真正大于 \(12\) 的只有 \(33\)、\(44\) 和 \(132\)。所以
$$T(12)=(33-12)+(44-12)+(132-12)=21+32+120=173.$$
注意 \(22\) 和 \(66\) 虽然也是 \(132\) 的因子，却不会出现在这个列表里。原因是它们对应的是中间幂次 \(j=1\)，此时互补因子分别是 \(6\) 和 \(2\)，两边都是偶数，奇偶性条件不成立。这正是“只保留 \(j=0\) 和 \(j=t\)”这一结论的实际含义。
当某个固定 \(n\) 的 \(T(n)\) 已经算出来以后，最终答案就是
$$U(N)=\sum_{n=3}^{N}T(n).$$
这里不需要再寻找额外的闭式。真正关键的是把单个 \(T(n)\) 化成可枚举的因子和，因为这一步才让上界 \(1{,}234{,}567\) 变得可计算。
C++、Python 和 Java 实现采用同一套流程。首先预处理到 \(N\) 的最小素因子表，这样后续对许多整数反复分解时都能快速完成。然后对每个 \(n\)，把 \(n\) 与 \(n-1\) 中的所有 \(2\) 因子剥离出来；剥离的总指数正好就是
$$n(n-1)=2^t m$$
里的 \(t\)。剩下的两个奇数部分再借助预处理表做素因子分解，并把指数合并，得到奇数核 \(m\) 的完整分解。接下来，递归式的因子生成器会把每一个奇因子 \(d\mid m\) 精确访问一次。对每个生成出的 \(d\)，实现都检查两个合法端点 \(d\) 与 \(2^t d\)；只要端点大于 \(n\)，就把超出的部分加入当前 \(T(n)\) 的累计值。最后再把 \(n=3\) 到 \(N\) 的所有 \(T(n)\) 相加，得到 \(U(N)\)。
最小素因子表的预处理复杂度为 \(O(N\log\log N)\)，空间复杂度为 \(O(N)\)。对固定的 \(n\) 而言，去掉 \(2\) 的幂次几乎可以忽略；分解剩余奇数部分的代价与出现的素因子个数成正比；而递归枚举阶段恰好会访问 \(\tau(m)\) 个奇因子，这里 \(m=\operatorname{odd}(n(n-1))\)。因此整体上一个自然的时间界是
$$O\!\left(N\log\log N+\sum_{n=3}^{N}\tau\!\bigl(\operatorname{odd}(n(n-1))\bigr)\right),$$
空间则是筛表所需的 \(O(N)\)，外加当前分解过程中的少量递归状态。
Для каждого целого \(n\ge 3\) величина \(T(n)\) есть сумма всех положительных смещений \(k\), которые остаются после делительной переформулировки, используемой в реализациях. Если обозначить соответствующую точку как \(D=n+k\), то допустимыми являются ровно те значения, для которых \(D\) делит \(n(n-1)\), а дополнительный множитель имеет противоположную чётность. Определим
$$E(n)=\left\{D>n: D\mid n(n-1),\ D\not\equiv \frac{n(n-1)}{D}\pmod 2\right\}.$$
Тогда
$$T(n)=\sum_{D\in E(n)}(D-n),\qquad U(N)=\sum_{n=3}^{N}T(n).$$
Прямой перебор возможных смещений \(k\) был бы слишком медленным. Ключевое наблюдение состоит в том, что условие на чётность становится очень простым после выделения полной степени двойки из произведения \(n(n-1)\).
Все три реализации опираются на одно и то же описание допустимых конечных точек через делители. После этого каждый вклад получается только из нечётного ядра числа \(n(n-1)\).
Запишем положительное смещение как \(k=D-n\), то есть \(D=n+k\) и \(D>n\). Допустимыми являются ровно те случаи, когда \(D\) входит в разложение
$$D\,Q=n(n-1)$$
и имеет чётность, противоположную чётности \(Q\):
$$D\not\equiv Q\pmod 2.$$
Каждый такой делитель \(D\) вносит вклад \(D-n\). Тем самым задача превращается в структурированную сумму по делителям числа \(n(n-1)\).
Пусть
$$n(n-1)=2^t m,\qquad m\text{ нечётно}.$$
Тогда любой делитель числа \(n(n-1)\) единственным образом имеет вид
$$D=2^j d,\qquad 0\le j\le t,\qquad d\mid m.$$
Дополнительный множитель равен
$$Q=2^{t-j}\frac{m}{d}.$$
Условие на чётность требует, чтобы нечётным был ровно один из двух множителей. Это возможно только в крайних случаях \(j=0\) или \(j=t\). Поэтому допустимые конечные точки имеют вид
$$D=d\qquad\text{или}\qquad D=2^t d\qquad(d\mid m).$$
Все промежуточные варианты \(0<j<t\) делают оба множителя чётными и потому никогда не подходят.
Разложим нечётное ядро:
$$m=\prod_{r=1}^{s} p_r^{e_r}.$$
Тогда любой нечётный делитель числа \(m\) записывается как
$$d=\prod_{r=1}^{s} p_r^{\alpha_r},\qquad 0\le \alpha_r\le e_r.$$
Значит, после того как известны показатели простых в \(m\), все допустимые нечётные делители можно породить стандартной рекурсией по показателям \(\alpha_1,\dots,\alpha_s\). Именно поэтому реализации тратят основные усилия на быстрое разложение и аккуратное перечисление делителей, а не на проверку смещений по одному.
Каждый нечётный делитель \(d\mid m\) даёт две кандидатные конечные точки: \(d\) и \(2^t d\). Положительное смещение возникает только тогда, когда конечная точка больше \(n\), поэтому
$$T(n)=\sum_{d\mid m}\left(\max\{d-n,0\}+\max\{2^t d-n,0\}\right).$$
Эта формула эквивалентна исходному определению через \(E(n)\), но вычислительно значительно удобнее, поскольку перебор идёт только по делителям нечётной части \(m\).
Здесь
$$12\cdot 11=132=2^2\cdot 33,$$
то есть \(t=2\), \(m=33\). Нечётные делители числа \(33\) равны
$$1,\ 3,\ 11,\ 33.$$
По шагу 2 допустимыми конечными точками являются сами эти делители и те же делители, умноженные на \(2^t=4\):
$$1,\ 3,\ 11,\ 33,\qquad 4,\ 12,\ 44,\ 132.$$
Из них больше \(12\) только \(33\), \(44\) и \(132\). Следовательно,
$$T(12)=(33-12)+(44-12)+(132-12)=21+32+120=173.$$
Делители \(22\) и \(66\) здесь не появляются: они соответствуют промежуточному выбору \(j=1\), при котором дополнительные множители тоже чётные, а значит условие на противоположную чётность нарушается.
После вычисления \(T(n)\) для фиксированного \(n\) окончательный ответ имеет вид
$$U(N)=\sum_{n=3}^{N}T(n).$$
Дополнительная закрытая формула не требуется. Вся трудность снимается именно делительной формой для одного \(T(n)\), потому что она делает диапазон до \(1{,}234{,}567\) вычислимым на практике.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала строится таблица наименьших простых делителей до \(N\), что делает повторяющиеся факторизации дешёвыми. Затем для каждого \(n\) из чисел \(n\) и \(n-1\) удаляются все множители \(2\); суммарный удалённый показатель и есть тот самый \(t\) из разложения
$$n(n-1)=2^t m.$$
Оставшиеся нечётные части раскладываются с помощью заранее построенной таблицы, а их показатели объединяются, чтобы получить факторизацию \(m\). После этого рекурсивный генератор делителей посещает каждый нечётный делитель \(d\mid m\) ровно один раз. Для каждого такого \(d\) реализация проверяет две допустимые конечные точки \(d\) и \(2^t d\); если конечная точка больше \(n\), избыток над \(n\) добавляется к текущему значению \(T(n)\). В конце эти значения суммируются от \(n=3\) до \(N\), давая \(U(N)\).
Построение таблицы наименьших простых делителей требует \(O(N\log\log N)\) времени и \(O(N)\) памяти. Для фиксированного \(n\) удаление степеней двойки пренебрежимо мало, факторизация нечётных частей пропорциональна числу встретившихся простых множителей, а шаг перечисления делителей посещает ровно \(\tau(m)\) нечётных делителей, где \(m=\operatorname{odd}(n(n-1))\). Поэтому естественная общая оценка такова:
$$O\!\left(N\log\log N+\sum_{n=3}^{N}\tau\!\bigl(\operatorname{odd}(n(n-1))\bigr)\right),$$
при \(O(N)\) памяти на решето и небольшом рекурсивном состоянии для текущей факторизации.
لكل عدد صحيح \(n\ge 3\)، فإن الكمية \(T(n)\) هي مجموع جميع الإزاحات الموجبة \(k\) التي تبقى بعد إعادة الصياغة بالقواسم كما تستعملها التطبيقات. إذا كتبنا نقطة النهاية الموافقة على صورة \(D=n+k\)، فإن القيم المقبولة هي بالضبط القواسم \(D\) للعدد \(n(n-1)\) التي يكون عاملها المتمم ذا فردية معاكسة. نعرّف
$$E(n)=\left\{D>n: D\mid n(n-1),\ D\not\equiv \frac{n(n-1)}{D}\pmod 2\right\}.$$
وعندئذ
$$T(n)=\sum_{D\in E(n)}(D-n),\qquad U(N)=\sum_{n=3}^{N}T(n).$$
البحث المباشر عبر كثير من القيم الممكنة لـ \(k\) سيكون بطيئًا جدًا. الفكرة الحاسمة هي أن شرط الفردية والزوجية يصبح بسيطًا جدًا بعد فصل القوة الكاملة للعدد \(2\) من \(n(n-1)\).
تعتمد التطبيقات الثلاثة على الوصف نفسه لنقاط النهاية المقبولة باستعمال القواسم. وبعد كتابة هذا الوصف، يتبين أن كل مساهمة تأتي فقط من النواة الفردية للعدد \(n(n-1)\).
نكتب الإزاحة الموجبة على الصورة \(k=D-n\)، أي \(D=n+k\) مع \(D>n\). وتكون القيمة مقبولة بالضبط عندما يظهر \(D\) في التحليل
$$D\,Q=n(n-1)$$
بحيث تكون فردية \(D\) معاكسة لفردية \(Q\):
$$D\not\equiv Q\pmod 2.$$
وكل قاسم من هذا النوع يضيف المقدار \(D-n\). وهكذا تتحول المسألة كلها إلى مجموع منظّم على قواسم \(n(n-1)\).
نكتب
$$n(n-1)=2^t m.$$
حيث إن \(m\) عدد فردي.
وعندئذ يمكن كتابة كل قاسم للعدد \(n(n-1)\) بصورة وحيدة على الشكل
$$D=2^j d,\qquad 0\le j\le t,\qquad d\mid m.$$
أما العامل المتمم فيكون
$$Q=2^{t-j}\frac{m}{d}.$$
شرط الفردية يعني أن واحدًا فقط من \(D\) و\(Q\) يجب أن يكون فرديًا. وهذا لا يحدث إلا في الحالتين الطرفيتين \(j=0\) أو \(j=t\). لذلك فإن نقاط النهاية المقبولة هي بالضبط
$$D=d\qquad\text{or}\qquad D=2^t d\qquad(d\mid m).$$
أما القيم الوسطى \(0<j<t\) فتجعل العاملين زوجيين معًا، ولذلك لا تسهم أبدًا.
نحلل النواة الفردية على الصورة
$$m=\prod_{r=1}^{s} p_r^{e_r}.$$
وعندئذ فإن كل قاسم فردي لـ \(m\) يكتب بالشكل
$$d=\prod_{r=1}^{s} p_r^{\alpha_r},\qquad 0\le \alpha_r\le e_r.$$
وبمجرد معرفة أسس العوامل الأولية في \(m\)، يصبح توليد جميع القواسم الفردية المقبولة مجرد تعداد عودي قياسي للأسس \(\alpha_1,\dots,\alpha_s\). ولهذا السبب تركز التطبيقات على التحليل السريع إلى عوامل أولية ثم على تعداد القواسم بصورة منهجية بدل اختبار الإزاحات واحدة واحدة.
كل قاسم فردي \(d\mid m\) يولد نقطتي نهاية محتملتين هما \(d\) و\(2^t d\). ولا تنتج إزاحة موجبة إلا إذا كانت نقطة النهاية أكبر من \(n\)، ولذلك نحصل على الصيغة
$$T(n)=\sum_{d\mid m}\left(\max\{d-n,0\}+\max\{2^t d-n,0\}\right).$$
هذه الصيغة مكافئة تمامًا للتعريف السابق باستعمال \(E(n)\)، لكنها أكفأ بكثير لأن الدوران أصبح محصورًا في قواسم الجزء الفردي \(m\).
لدينا هنا
$$12\cdot 11=132=2^2\cdot 33,$$
ومن ثم \(t=2\) و\(m=33\). والقواسم الفردية لـ \(33\) هي
$$1,\ 3,\ 11,\ 33.$$
وبحسب الخطوة الثانية، فإن نقاط النهاية المقبولة هي هذه القواسم نفسها ثم هذه القواسم مضروبة في \(2^t=4\):
$$1,\ 3,\ 11,\ 33,\qquad 4,\ 12,\ 44,\ 132.$$
ولا يسهم إلا ما كان أكبر من \(12\)، أي \(33\) و\(44\) و\(132\). لذلك
$$T(12)=(33-12)+(44-12)+(132-12)=21+32+120=173.$$
أما القاسمان \(22\) و\(66\) فلا يظهران هنا، لأنهما يقابلان الاختيار الوسطي \(j=1\)، وفي هذه الحالة يكون العامل المتمم زوجيًا أيضًا، فيفشل شرط اختلاف الفردية.
بعد حساب \(T(n)\) لقيمة ثابتة من \(n\)، تكون الإجابة النهائية ببساطة
$$U(N)=\sum_{n=3}^{N}T(n).$$
ولا حاجة إلى صيغة مغلقة إضافية. التخفيض المهم فعلًا هو كتابة كل \(T(n)\) في صورة مجموع على القواسم، لأن هذا هو ما يجعل المدى حتى \(1{,}234{,}567\) عمليًا.
تتبع تطبيقات C++ وPython وJava الخوارزمية نفسها. أولًا تبني جدول أصغر عامل أولي حتى \(N\)، وهذا يجعل التحليل المتكرر إلى عوامل أولية سريعًا. ثم لكل \(n\)، تزيل جميع عوامل \(2\) من \(n\) ومن \(n-1\)، ويكون مجموع الأسس المنزوعة هو نفسه \(t\) في التفكيك
$$n(n-1)=2^t m.$$
بعد ذلك تُحلَّل الأجزاء الفردية الباقية باستعمال الجدول المُسبق، ثم تُدمج الأسس للحصول على تحليل \(m\). وبعدها يزور مولّد قواسم عودي كل قاسم فردي \(d\mid m\) مرة واحدة فقط. ولكل \(d\)، يفحص التنفيذ نقطتي النهاية المقبولتين \(d\) و\(2^t d\)؛ وإذا تجاوزت نقطة النهاية القيمة \(n\)، فإنه يضيف الزيادة على \(n\) إلى المجموع الجاري لـ \(T(n)\). وفي النهاية تُجمع هذه القيم من \(n=3\) حتى \(N\) للحصول على \(U(N)\).
بناء جدول أصغر عامل أولي يكلف \(O(N\log\log N)\) زمنًا و\(O(N)\) ذاكرة. وبالنسبة إلى \(n\) ثابت، فإن نزع قوى العدد \(2\) مهمل تقريبًا، وتحليل الجزأين الفرديين يتناسب مع عدد العوامل الأولية التي تظهر، أما خطوة تعداد القواسم فتزور بالضبط \(\tau(m)\) من القواسم الفردية حيث \(m=\operatorname{odd}(n(n-1))\). ولذلك فإن التقدير الطبيعي الكلي هو
$$O\!\left(N\log\log N+\sum_{n=3}^{N}\tau\!\bigl(\operatorname{odd}(n(n-1))\bigr)\right),$$
مع \(O(N)\) ذاكرة للغربال إضافة إلى حالة عودية صغيرة للتحليل الحالي.