For the first \(n\) positive integers, compare two quantities:
$$A_n=\left(\sum_{k=1}^{n} k\right)^2,\qquad B_n=\sum_{k=1}^{n} k^2.$$
The problem asks for
$$D_n=A_n-B_n.$$
In the Project Euler instance, \(n=100\). The statement also gives the smaller checkpoint \(n=10\), where the answer is \(2640\).
The implementations reduce the problem to two classical closed forms. The relevant mathematical objects are the ordinary sum
$$S_n=\sum_{k=1}^{n} k,$$
the sum of squares
$$Q_n=\sum_{k=1}^{n} k^2,$$
and the difference \(D_n=S_n^2-Q_n\).
The phrase “square of the sum minus sum of the squares” hides a clean combinatorial identity. Expanding the square gives
$$\left(\sum_{k=1}^{n} k\right)^2=\sum_{k=1}^{n} k^2+2\sum_{1\le i<j\le n} ij.$$
Therefore
$$D_n=2\sum_{1\le i<j\le n} ij.$$
So the answer measures all cross-terms between distinct numbers. The invariant here is simple: every unordered pair \(\{i,j\}\) with \(i<j\) appears exactly twice in the square expansion, once as \(ij\) and once as \(ji\).
To compute \(S_n\), pair the first and last terms, the second and second-last terms, and so on:
$$1+n=n+1,\qquad 2+(n-1)=n+1,\qquad 3+(n-2)=n+1.$$
Each pair contributes \(n+1\). This leads to the classical triangular-number formula
$$S_n=\frac{n(n+1)}{2}.$$
This identity is the first ingredient used by the implementations.
For \(Q_n\), a compact derivation uses the telescoping identity
$$(k+1)^3-k^3=3k^2+3k+1.$$
Summing from \(k=1\) to \(n\) collapses the left-hand side:
$$(n+1)^3-1=3\sum_{k=1}^{n} k^2+3\sum_{k=1}^{n} k+n.$$
In terms of \(Q_n\) and \(S_n\), this is
$$(n+1)^3-1=3Q_n+3S_n+n.$$
Substitute \(S_n=\frac{n(n+1)}{2}\):
$$3Q_n=(n+1)^3-1-\frac{3n(n+1)}{2}-n=\frac{n(n+1)(2n+1)}{2}.$$
Hence
$$Q_n=\frac{n(n+1)(2n+1)}{6}.$$
Now substitute the two closed forms into \(D_n=S_n^2-Q_n\):
$$D_n=\left(\frac{n(n+1)}{2}\right)^2-\frac{n(n+1)(2n+1)}{6}.$$
Factoring common terms gives a single polynomial expression:
$$D_n=\frac{n(n+1)(3n^2-n-2)}{12}=\frac{n(n-1)(n+1)(3n+2)}{12}.$$
The implementations use the first subtraction form directly, but this factorization shows even more clearly that the entire problem has been collapsed to a closed expression in \(n\).
For \(n=10\),
$$S_{10}=55,\qquad Q_{10}=385,\qquad D_{10}=55^2-385=2640.$$
This is the built-in checkpoint used to verify the formula. For the actual Euler input \(n=100\),
$$S_{100}=5050,\qquad Q_{100}=338350,\qquad D_{100}=5050^2-338350=25164150.$$
The C++, Python, and Java implementations all follow the same mathematical recipe: compute the triangular sum, compute the square-sum formula, square the first quantity, subtract the second, and print the result. No loop over \(1,2,\dots,n\) is required.
The implementation first forms
$$\frac{n(n+1)}{2}$$
and
$$\frac{n(n+1)(2n+1)}{6}.$$
After that, the answer is just one subtraction. Each language version also checks the known case \(n=10\mapsto2640\) before reporting the default Project Euler case \(n=100\).
The compiled implementations use 64-bit integer arithmetic, while the Python version uses integer arithmetic naturally. For this problem size the intermediate values are comfortably within range, and the divisions by \(2\) and \(6\) are exact because the closed forms are integer-valued for every positive integer \(n\).
A direct summation approach would already be modest at \(O(n)\) time, but the closed-form derivation removes iteration entirely. The running time is therefore \(O(1)\).
The memory usage is also \(O(1)\), since the computation stores only a fixed number of integer quantities. There is no table, recursion, or auxiliary array.
Für die ersten \(n\) positiven ganzen Zahlen werden zwei Größen verglichen:
$$A_n=\left(\sum_{k=1}^{n} k\right)^2,\qquad B_n=\sum_{k=1}^{n} k^2.$$
Gesucht ist also
$$D_n=A_n-B_n.$$
Im eigentlichen Euler-Fall gilt \(n=100\). Die Aufgabenstellung nennt außerdem den kleineren Kontrollwert \(n=10\) mit Ergebnis \(2640\).
Die Implementierungen reduzieren das Problem auf zwei klassische geschlossene Formeln. Die zentralen Objekte sind die gewöhnliche Summe
$$S_n=\sum_{k=1}^{n} k,$$
die Quadratsumme
$$Q_n=\sum_{k=1}^{n} k^2,$$
und die Differenz \(D_n=S_n^2-Q_n\).
Die Formulierung „Quadrat der Summe minus Summe der Quadrate“ verbirgt eine saubere Identität. Beim Ausmultiplizieren erhält man
$$\left(\sum_{k=1}^{n} k\right)^2=\sum_{k=1}^{n} k^2+2\sum_{1\le i<j\le n} ij.$$
Damit folgt sofort
$$D_n=2\sum_{1\le i<j\le n} ij.$$
Die gesuchte Größe ist also die Gesamtsumme aller Kreuzterme zwischen verschiedenen Zahlen. Die entscheidende Invariante lautet: Jedes ungeordnete Paar \(\{i,j\}\) mit \(i<j\) erscheint in der Quadratentwicklung genau zweimal, einmal als \(ij\) und einmal als \(ji\).
Zur Berechnung von \(S_n\) paart man den ersten mit dem letzten Term, den zweiten mit dem vorletzten und so weiter:
$$1+n=n+1,\qquad 2+(n-1)=n+1,\qquad 3+(n-2)=n+1.$$
Jedes Paar liefert also \(n+1\). Daraus ergibt sich die klassische Formel der Dreieckszahlen
$$S_n=\frac{n(n+1)}{2}.$$
Diese Identität ist die erste Zutat der Implementierungen.
Für \(Q_n\) ist die Teleskopidentität
$$(k+1)^3-k^3=3k^2+3k+1$$
besonders praktisch. Summiert man von \(k=1\) bis \(n\), fällt die linke Seite zusammen zu
$$(n+1)^3-1=3\sum_{k=1}^{n} k^2+3\sum_{k=1}^{n} k+n.$$
In der Kurzschreibweise mit \(Q_n\) und \(S_n\) heißt das
$$(n+1)^3-1=3Q_n+3S_n+n.$$
Nach Einsetzen von \(S_n=\frac{n(n+1)}{2}\) bekommt man
$$3Q_n=(n+1)^3-1-\frac{3n(n+1)}{2}-n=\frac{n(n+1)(2n+1)}{2},$$
also
$$Q_n=\frac{n(n+1)(2n+1)}{6}.$$
Setzt man beide Formeln in \(D_n=S_n^2-Q_n\) ein, so erhält man
$$D_n=\left(\frac{n(n+1)}{2}\right)^2-\frac{n(n+1)(2n+1)}{6}.$$
Durch Ausklammern gemeinsamer Faktoren folgt die kompakte Polynomform
$$D_n=\frac{n(n+1)(3n^2-n-2)}{12}=\frac{n(n-1)(n+1)(3n+2)}{12}.$$
Die Implementierungen verwenden direkt die erste Subtraktionsform, aber die Faktorisierung macht sichtbar, dass das gesamte Problem vollständig auf einen Ausdruck in \(n\) reduziert ist.
Für \(n=10\) gilt
$$S_{10}=55,\qquad Q_{10}=385,\qquad D_{10}=55^2-385=2640.$$
Das ist genau der eingebaute Kontrollwert. Für den eigentlichen Euler-Fall \(n=100\) erhält man
$$S_{100}=5050,\qquad Q_{100}=338350,\qquad D_{100}=5050^2-338350=25164150.$$
Die C++-, Python- und Java-Implementierungen folgen alle demselben Rezept: zuerst die Dreieckszahl berechnen, dann die Formel für die Quadratsumme auswerten, anschließend die erste Größe quadrieren, die zweite abziehen und das Ergebnis ausgeben. Eine Schleife über \(1,2,\dots,n\) ist nicht nötig.
Zuerst werden
$$\frac{n(n+1)}{2}$$
und
$$\frac{n(n+1)(2n+1)}{6}$$
gebildet. Danach bleibt nur noch eine Subtraktion. Alle Sprachversionen prüfen außerdem den bekannten Fall \(n=10\mapsto2640\), bevor der Standardfall \(n=100\) ausgegeben wird.
Die kompilierten Implementierungen benutzen 64-Bit-Ganzzahlen, während Python ohnehin mit Ganzzahlen rechnet. Für diese Problemgröße sind die Zwischenwerte klein genug, und die Divisionen durch \(2\) und \(6\) sind exakt, weil die geschlossenen Formeln für jedes positive ganzzahlige \(n\) wieder ganze Zahlen liefern.
Eine direkte Aufsummierung wäre bereits nur \(O(n)\), doch die geschlossene Formel eliminiert jede Iteration. Deshalb beträgt die Laufzeit \(O(1)\).
Auch der Speicherverbrauch ist \(O(1)\), da nur wenige Ganzzahlen gehalten werden. Es gibt weder Tabellen noch Rekursion noch Hilfsarrays.
İlk \(n\) pozitif tam sayı için iki büyüklük karşılaştırılır:
$$A_n=\left(\sum_{k=1}^{n} k\right)^2,\qquad B_n=\sum_{k=1}^{n} k^2.$$
İstenen değer
$$D_n=A_n-B_n$$
olur. Project Euler örneğinde \(n=100\) alınır. Soruda ayrıca \(n=10\) için sonucun \(2640\) olduğu küçük bir kontrol örneği verilir.
Uygulamalar problemi iki klasik kapalı formüle indirger. Gerçekten kullanılan matematiksel nesneler sıradan toplam
$$S_n=\sum_{k=1}^{n} k,$$
kareler toplamı
$$Q_n=\sum_{k=1}^{n} k^2,$$
ve farkın kendisi \(D_n=S_n^2-Q_n\) ifadesidir.
“Toplamın karesi eksi karelerin toplamı” ifadesi, açılınca çok net bir kimliğe dönüşür:
$$\left(\sum_{k=1}^{n} k\right)^2=\sum_{k=1}^{n} k^2+2\sum_{1\le i<j\le n} ij.$$
Buradan
$$D_n=2\sum_{1\le i<j\le n} ij$$
elde edilir. Yani aranan şey, farklı sayı çiftlerinden gelen bütün çapraz terimlerin toplamıdır. Buradaki temel değişmez şudur: \(i<j\) olan her sırasız \(\{i,j\}\) çifti kare açılımında tam iki kez görünür; biri \(ij\), diğeri \(ji\) olarak.
\(S_n\)'yi hesaplamak için ilk ve son terimi, ikinci ve sondan bir önceki terimi eşleştirebiliriz:
$$1+n=n+1,\qquad 2+(n-1)=n+1,\qquad 3+(n-2)=n+1.$$
Her eşleşme \(n+1\) verdiği için klasik üçgensel sayı formülü çıkar:
$$S_n=\frac{n(n+1)}{2}.$$
Uygulamaların kullandığı ilk kimlik budur.
\(Q_n\) için en kısa türetimlerden biri şu teleskopik özdeşliği kullanır:
$$(k+1)^3-k^3=3k^2+3k+1.$$
\(k=1\)'den \(n\)'e toplandığında sol taraf çöker ve
$$(n+1)^3-1=3\sum_{k=1}^{n} k^2+3\sum_{k=1}^{n} k+n$$
kalır. \(Q_n\) ve \(S_n\) ile yazarsak
$$(n+1)^3-1=3Q_n+3S_n+n.$$
\(S_n=\frac{n(n+1)}{2}\) yerine konursa
$$3Q_n=(n+1)^3-1-\frac{3n(n+1)}{2}-n=\frac{n(n+1)(2n+1)}{2}$$
olur; dolayısıyla
$$Q_n=\frac{n(n+1)(2n+1)}{6}.$$
İki kapalı formu \(D_n=S_n^2-Q_n\) içine yerleştirince
$$D_n=\left(\frac{n(n+1)}{2}\right)^2-\frac{n(n+1)(2n+1)}{6}$$
elde edilir. Ortak çarpanlar ayrılırsa daha sıkı bir polinom görünür:
$$D_n=\frac{n(n+1)(3n^2-n-2)}{12}=\frac{n(n-1)(n+1)(3n+2)}{12}.$$
Uygulamalar doğrudan ilk çıkarma biçimini kullanır, fakat bu çarpanlara ayrılmış form problemin bütünüyle \(n\)'nin kapalı bir ifadesine indirildiğini açıkça gösterir.
\(n=10\) için
$$S_{10}=55,\qquad Q_{10}=385,\qquad D_{10}=55^2-385=2640.$$
Bu, uygulamalardaki kontrol değeridir. Gerçek Euler girdisi olan \(n=100\) için ise
$$S_{100}=5050,\qquad Q_{100}=338350,\qquad D_{100}=5050^2-338350=25164150.$$
C++, Python ve Java uygulamalarının hepsi aynı yolu izler: önce üçgensel toplamı hesaplar, sonra kareler toplamı formülünü değerlendirir, ilk değeri karesini alır, ikinciyi çıkarır ve sonucu yazdırır. \(1,2,\dots,n\) üzerinde dönen bir döngü yoktur.
Önce
$$\frac{n(n+1)}{2}$$
ve
$$\frac{n(n+1)(2n+1)}{6}$$
hesaplanır. Sonrasında tek gereken işlem bir çıkarmadır. Her dildeki uygulama ayrıca bilinen \(n=10\mapsto2640\) örneğini doğrulayıp ardından varsayılan \(n=100\) sonucunu verir.
Derlenen uygulamalar 64-bit tamsayı aritmetiği kullanır; Python tarafında da doğal olarak tamsayı aritmetiği kullanılır. Bu problem boyutunda ara değerler güvenli aralıktadır ve \(2\) ile \(6\)'ya bölmeler tamdır; çünkü kapalı formüller her pozitif tam sayı \(n\) için yine tam sayı üretir.
Doğrudan toplama yapan bir yaklaşım bile yalnızca \(O(n)\) zaman alırdı; ancak kapalı form türetimi yinelemeyi tamamen ortadan kaldırır. Bu yüzden çalışma süresi \(O(1)\)'dir.
Bellek kullanımı da \(O(1)\)'dir; yalnızca sabit sayıda tamsayı tutulur. Tablo, özyineleme veya yardımcı dizi yoktur.
Para los primeros \(n\) enteros positivos se comparan dos cantidades:
$$A_n=\left(\sum_{k=1}^{n} k\right)^2,\qquad B_n=\sum_{k=1}^{n} k^2.$$
El objetivo es
$$D_n=A_n-B_n.$$
En la versión de Project Euler se toma \(n=100\). El enunciado también da el control pequeño \(n=10\), cuyo valor es \(2640\).
Las implementaciones reducen todo a dos fórmulas cerradas clásicas. Los objetos matemáticos que realmente aparecen son la suma ordinaria
$$S_n=\sum_{k=1}^{n} k,$$
la suma de cuadrados
$$Q_n=\sum_{k=1}^{n} k^2,$$
y la diferencia \(D_n=S_n^2-Q_n\).
La frase “cuadrado de la suma menos suma de los cuadrados” oculta una identidad muy clara. Al expandir el cuadrado,
$$\left(\sum_{k=1}^{n} k\right)^2=\sum_{k=1}^{n} k^2+2\sum_{1\le i<j\le n} ij.$$
Por tanto,
$$D_n=2\sum_{1\le i<j\le n} ij.$$
Así, la respuesta es la suma total de todos los términos cruzados entre números distintos. La invariante clave es que cada par no ordenado \(\{i,j\}\) con \(i<j\) aparece exactamente dos veces en la expansión, una como \(ij\) y otra como \(ji\).
Para calcular \(S_n\), se empareja el primer término con el último, el segundo con el penúltimo, y así sucesivamente:
$$1+n=n+1,\qquad 2+(n-1)=n+1,\qquad 3+(n-2)=n+1.$$
Cada par aporta \(n+1\). De ahí sale la fórmula clásica del número triangular:
$$S_n=\frac{n(n+1)}{2}.$$
Esta es la primera identidad usada por las implementaciones.
Para \(Q_n\), una derivación compacta usa la identidad telescópica
$$(k+1)^3-k^3=3k^2+3k+1.$$
Al sumar desde \(k=1\) hasta \(n\), el lado izquierdo colapsa:
$$(n+1)^3-1=3\sum_{k=1}^{n} k^2+3\sum_{k=1}^{n} k+n.$$
En términos de \(Q_n\) y \(S_n\),
$$(n+1)^3-1=3Q_n+3S_n+n.$$
Sustituyendo \(S_n=\frac{n(n+1)}{2}\), se obtiene
$$3Q_n=(n+1)^3-1-\frac{3n(n+1)}{2}-n=\frac{n(n+1)(2n+1)}{2},$$
y por tanto
$$Q_n=\frac{n(n+1)(2n+1)}{6}.$$
Al sustituir ambas fórmulas en \(D_n=S_n^2-Q_n\), aparece
$$D_n=\left(\frac{n(n+1)}{2}\right)^2-\frac{n(n+1)(2n+1)}{6}.$$
Extrayendo factores comunes, queda una expresión polinómica compacta:
$$D_n=\frac{n(n+1)(3n^2-n-2)}{12}=\frac{n(n-1)(n+1)(3n+2)}{12}.$$
Las implementaciones usan directamente la primera forma por resta, pero esta factorización deja claro que todo el problema ya quedó colapsado a una expresión cerrada en \(n\).
Para \(n=10\),
$$S_{10}=55,\qquad Q_{10}=385,\qquad D_{10}=55^2-385=2640.$$
Ese es el control incorporado en las implementaciones. Para el caso real de Euler con \(n=100\),
$$S_{100}=5050,\qquad Q_{100}=338350,\qquad D_{100}=5050^2-338350=25164150.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma receta: calculan la suma triangular, calculan la fórmula de la suma de cuadrados, elevan al cuadrado la primera cantidad, restan la segunda e imprimen el resultado. No hace falta iterar sobre \(1,2,\dots,n\).
Primero se forman
$$\frac{n(n+1)}{2}$$
y
$$\frac{n(n+1)(2n+1)}{6}.$$
Después solo queda una resta. Cada versión también comprueba el caso conocido \(n=10\mapsto2640\) antes de informar el caso por defecto \(n=100\).
Las implementaciones compiladas usan enteros de 64 bits, mientras que Python trabaja naturalmente con enteros. Para este tamaño de problema los valores intermedios caben con holgura, y las divisiones por \(2\) y \(6\) son exactas porque las fórmulas cerradas siempre producen enteros.
Un enfoque de suma directa ya tendría coste \(O(n)\), pero la reducción algebraica elimina toda iteración. Por eso el tiempo total es \(O(1)\).
El espacio también es \(O(1)\), ya que solo se guardan unas pocas cantidades enteras. No hay tablas, recursión ni arreglos auxiliares.
对前 \(n\) 个正整数，比较下面两个量：
$$A_n=\left(\sum_{k=1}^{n} k\right)^2,\qquad B_n=\sum_{k=1}^{n} k^2.$$
题目要求计算
$$D_n=A_n-B_n.$$
在 Project Euler 的具体题目里，\(n=100\)。题面还给出了一个较小的校验例子：当 \(n=10\) 时，答案是 \(2640\)。
实现并没有逐项累加，而是把问题压缩成两个经典闭式。真正出现的数学对象是普通和
$$S_n=\sum_{k=1}^{n} k,$$
平方和
$$Q_n=\sum_{k=1}^{n} k^2,$$
以及差值 \(D_n=S_n^2-Q_n\)。
“和的平方减去平方和” 这个说法看似简单，但展开以后会露出核心结构：
$$\left(\sum_{k=1}^{n} k\right)^2=\sum_{k=1}^{n} k^2+2\sum_{1\le i<j\le n} ij.$$
因此
$$D_n=2\sum_{1\le i<j\le n} ij.$$
这说明题目本质上在计算所有不同数对之间的交叉项总和。关键不变量是：每个满足 \(i<j\) 的无序数对 \(\{i,j\}\)，在平方展开中都会恰好出现两次，一次来自 \(ij\)，一次来自 \(ji\)。
为了求 \(S_n\)，把首项和末项、第二项和倒数第二项依次配对：
$$1+n=n+1,\qquad 2+(n-1)=n+1,\qquad 3+(n-2)=n+1.$$
每一对都等于 \(n+1\)，于是得到经典的三角数公式：
$$S_n=\frac{n(n+1)}{2}.$$
这是实现中使用的第一条公式。
对于 \(Q_n\)，可以利用一个非常紧凑的望远镜恒等式：
$$(k+1)^3-k^3=3k^2+3k+1.$$
把它从 \(k=1\) 加到 \(n\)，左边会望远镜消去，得到
$$(n+1)^3-1=3\sum_{k=1}^{n} k^2+3\sum_{k=1}^{n} k+n.$$
用 \(Q_n\) 和 \(S_n\) 记号改写，就是
$$(n+1)^3-1=3Q_n+3S_n+n.$$
再代入 \(S_n=\frac{n(n+1)}{2}\)，可得
$$3Q_n=(n+1)^3-1-\frac{3n(n+1)}{2}-n=\frac{n(n+1)(2n+1)}{2},$$
因此
$$Q_n=\frac{n(n+1)(2n+1)}{6}.$$
将两个闭式代回 \(D_n=S_n^2-Q_n\)，就得到
$$D_n=\left(\frac{n(n+1)}{2}\right)^2-\frac{n(n+1)(2n+1)}{6}.$$
把公因子提出后，还可以写成更紧凑的多项式形式：
$$D_n=\frac{n(n+1)(3n^2-n-2)}{12}=\frac{n(n-1)(n+1)(3n+2)}{12}.$$
实现实际使用的是“先算两个经典和，再相减”的形式，但这个因式分解说明：整个问题已经完全塌缩成 \(n\) 的一个闭式表达式。
当 \(n=10\) 时，
$$S_{10}=55,\qquad Q_{10}=385,\qquad D_{10}=55^2-385=2640.$$
这正是实现里用来校验公式是否写对的测试值。对题目真正需要的 \(n=100\)，
$$S_{100}=5050,\qquad Q_{100}=338350,\qquad D_{100}=5050^2-338350=25164150.$$
C++、Python 和 Java 实现采用完全相同的思路：先计算三角数公式，再计算平方和公式，把前者平方后减去后者，最后输出结果。整个过程中不需要对 \(1,2,\dots,n\) 做显式循环。
实现先得到
$$\frac{n(n+1)}{2}$$
和
$$\frac{n(n+1)(2n+1)}{6}.$$
随后只需做一次减法。各语言版本还都会检查已知样例 \(n=10\mapsto2640\)，然后再给出默认的 \(n=100\) 结果。
编译型实现使用 64 位整数，Python 则天然使用整数运算。对本题规模而言，中间结果远未接近上限；而除以 \(2\) 与除以 \(6\) 也都是精确的，因为这些闭式对每个正整数 \(n\) 都给出整数值。
如果直接累加，时间复杂度也不过是 \(O(n)\)。但在代数化简之后，连这层循环都被消掉了，因此运行时间是 \(O(1)\)。
空间复杂度同样是 \(O(1)\)，因为只保存少量整数。这里没有表、没有递归，也没有额外数组。
Для первых \(n\) положительных целых чисел сравниваются две величины:
$$A_n=\left(\sum_{k=1}^{n} k\right)^2,\qquad B_n=\sum_{k=1}^{n} k^2.$$
Требуется найти
$$D_n=A_n-B_n.$$
В задаче Project Euler берётся \(n=100\). В условии также дан меньший контрольный пример: при \(n=10\) ответ равен \(2640\).
Реализации сводят задачу к двум классическим замкнутым формулам. Настоящие математические объекты здесь таковы: обычная сумма
$$S_n=\sum_{k=1}^{n} k,$$
сумма квадратов
$$Q_n=\sum_{k=1}^{n} k^2,$$
и разность \(D_n=S_n^2-Q_n\).
Фраза «квадрат суммы минус сумма квадратов» скрывает простую структуру. После раскрытия квадрата имеем
$$\left(\sum_{k=1}^{n} k\right)^2=\sum_{k=1}^{n} k^2+2\sum_{1\le i<j\le n} ij.$$
Следовательно,
$$D_n=2\sum_{1\le i<j\le n} ij.$$
Итак, искомая величина равна сумме всех попарных перекрёстных членов между различными числами. Главная инварианта такова: каждая неупорядоченная пара \(\{i,j\}\) при \(i<j\) появляется в раскрытии ровно дважды, один раз как \(ij\) и один раз как \(ji\).
Чтобы вычислить \(S_n\), попарно складывают первый и последний член, второй и предпоследний и так далее:
$$1+n=n+1,\qquad 2+(n-1)=n+1,\qquad 3+(n-2)=n+1.$$
Каждая пара даёт \(n+1\), откуда получается классическая формула треугольных чисел:
$$S_n=\frac{n(n+1)}{2}.$$
Это первая формула, которую используют реализации.
Для \(Q_n\) удобно воспользоваться телескопическим тождеством
$$(k+1)^3-k^3=3k^2+3k+1.$$
Если просуммировать его по \(k\) от \(1\) до \(n\), левая часть схлопнется:
$$(n+1)^3-1=3\sum_{k=1}^{n} k^2+3\sum_{k=1}^{n} k+n.$$
В обозначениях \(Q_n\) и \(S_n\) это записывается так:
$$(n+1)^3-1=3Q_n+3S_n+n.$$
Подставляя \(S_n=\frac{n(n+1)}{2}\), получаем
$$3Q_n=(n+1)^3-1-\frac{3n(n+1)}{2}-n=\frac{n(n+1)(2n+1)}{2},$$
а значит
$$Q_n=\frac{n(n+1)(2n+1)}{6}.$$
Подставляя обе формулы в \(D_n=S_n^2-Q_n\), имеем
$$D_n=\left(\frac{n(n+1)}{2}\right)^2-\frac{n(n+1)(2n+1)}{6}.$$
После вынесения общих множителей получается компактная полиномиальная форма:
$$D_n=\frac{n(n+1)(3n^2-n-2)}{12}=\frac{n(n-1)(n+1)(3n+2)}{12}.$$
Реализации используют непосредственно форму с вычитанием двух классических сумм, но эта факторизация наглядно показывает, что задача целиком сведена к замкнутому выражению по \(n\).
Для \(n=10\)
$$S_{10}=55,\qquad Q_{10}=385,\qquad D_{10}=55^2-385=2640.$$
Именно это значение используется как контрольное. Для настоящего входа Euler, где \(n=100\), получаем
$$S_{100}=5050,\qquad Q_{100}=338350,\qquad D_{100}=5050^2-338350=25164150.$$
Реализации на C++, Python и Java действуют одинаково: сначала вычисляют треугольную сумму, затем формулу для суммы квадратов, потом возводят первую величину в квадрат, вычитают вторую и печатают ответ. Никакого прохода по \(1,2,\dots,n\) не требуется.
Сначала формируются значения
$$\frac{n(n+1)}{2}$$
и
$$\frac{n(n+1)(2n+1)}{6}.$$
После этого остаётся одна операция вычитания. Во всех версиях также проверяется известный случай \(n=10\mapsto2640\), а затем выводится результат для стандартного \(n=100\).
Компилируемые реализации используют 64-битные целые числа, а Python естественно работает с целочисленной арифметикой. Для данного размера задачи промежуточные значения малы, а деления на \(2\) и \(6\) точны, потому что замкнутые формулы всегда дают целое число.
Даже прямое суммирование имело бы сложность всего \(O(n)\), но алгебраическое сведение убирает и эту итерацию. Поэтому итоговое время работы равно \(O(1)\).
Память также имеет порядок \(O(1)\), поскольку хранятся лишь несколько целых значений. Нет ни таблиц, ни рекурсии, ни вспомогательных массивов.
لأول \(n\) من الأعداد الصحيحة الموجبة نقارن بين كميتين:
$$A_n=\left(\sum_{k=1}^{n} k\right)^2,\qquad B_n=\sum_{k=1}^{n} k^2.$$
والمطلوب هو
$$D_n=A_n-B_n.$$
في مسألة Project Euler تكون القيمة \(n=100\). كما يذكر نص المسألة مثالاً تحققياً أصغر هو \(n=10\) حيث تكون النتيجة \(2640\).
البرامج لا تجمع الحدود واحداً واحداً، بل تختزل المسألة إلى صيغتين مغلقتين معروفتين. الكائنات الرياضية الفعلية هنا هي المجموع العادي
$$S_n=\sum_{k=1}^{n} k,$$
ومجموع المربعات
$$Q_n=\sum_{k=1}^{n} k^2,$$
والفرق \(D_n=S_n^2-Q_n\).
عبارة «مربع المجموع ناقص مجموع المربعات» تخفي بنية واضحة جداً. عند التوسيع نحصل على
$$\left(\sum_{k=1}^{n} k\right)^2=\sum_{k=1}^{n} k^2+2\sum_{1\le i<j\le n} ij.$$
ومن ثم
$$D_n=2\sum_{1\le i<j\le n} ij.$$
أي أن الجواب هو مجموع جميع الحدود المتقاطعة بين الأعداد المختلفة. والثابت المهم هنا أن كل زوج غير مرتب \(\{i,j\}\) مع \(i<j\) يظهر مرتين بالضبط في توسعة المربع: مرة على صورة \(ij\) ومرة على صورة \(ji\).
لحساب \(S_n\)، نزاوج بين الحد الأول والأخير، ثم الثاني وما قبل الأخير، وهكذا:
$$1+n=n+1,\qquad 2+(n-1)=n+1,\qquad 3+(n-2)=n+1.$$
كل زوج يعطي القيمة \(n+1\)، ومن هنا تخرج الصيغة الكلاسيكية للعدد المثلثي:
$$S_n=\frac{n(n+1)}{2}.$$
وهذه هي الهوية الأولى التي تعتمد عليها التطبيقات.
أما \(Q_n\)، فيمكن اشتقاقه بسرعة من الهوية التلسكوبية
$$(k+1)^3-k^3=3k^2+3k+1.$$
عند جمعها من \(k=1\) إلى \(n\) ينهار الطرف الأيسر إلى
$$(n+1)^3-1=3\sum_{k=1}^{n} k^2+3\sum_{k=1}^{n} k+n.$$
وبترميز \(Q_n\) و\(S_n\) يصبح ذلك
$$(n+1)^3-1=3Q_n+3S_n+n.$$
ثم نعوض \(S_n=\frac{n(n+1)}{2}\) فنحصل على
$$3Q_n=(n+1)^3-1-\frac{3n(n+1)}{2}-n=\frac{n(n+1)(2n+1)}{2},$$
وبالتالي
$$Q_n=\frac{n(n+1)(2n+1)}{6}.$$
بعد التعويض في \(D_n=S_n^2-Q_n\) نحصل على
$$D_n=\left(\frac{n(n+1)}{2}\right)^2-\frac{n(n+1)(2n+1)}{6}.$$
وباستخراج العوامل المشتركة يمكن كتابة الجواب على صورة أكثر تكثيفاً:
$$D_n=\frac{n(n+1)(3n^2-n-2)}{12}=\frac{n(n-1)(n+1)(3n+2)}{12}.$$
التنفيذات تستخدم مباشرة صيغة «احسب مجموعين ثم اطرح»، لكن هذا التحليل يبين أن المسألة كلها انضغطت إلى تعبير مغلق في \(n\).
عندما \(n=10\)،
$$S_{10}=55,\qquad Q_{10}=385,\qquad D_{10}=55^2-385=2640.$$
وهذه هي قيمة التحقق المستخدمة داخل التطبيقات. أما للحالة الفعلية في Euler حيث \(n=100\)، فنحصل على
$$S_{100}=5050,\qquad Q_{100}=338350,\qquad D_{100}=5050^2-338350=25164150.$$
تنفذ تطبيقات C++ وPython وJava الخطة نفسها تماماً: تحسب أولاً مجموع الأعداد على صيغة عدد مثلثي، ثم تحسب صيغة مجموع المربعات، ثم تربع القيمة الأولى وتطرح الثانية وتطبع الناتج. لا توجد حلقة تمر على \(1,2,\dots,n\) صراحة.
يبدأ التنفيذ بحساب
$$\frac{n(n+1)}{2}$$
ثم
$$\frac{n(n+1)(2n+1)}{6}.$$
بعد ذلك تبقى عملية طرح واحدة فقط. كما تتحقق جميع النسخ من الحالة المعروفة \(n=10\mapsto2640\) قبل إخراج النتيجة الافتراضية عند \(n=100\).
النسخ المترجمة تستخدم أعداداً صحيحة بعرض 64-بت، أما Python فيتعامل مع الأعداد الصحيحة مباشرة. في هذا الحجم من المسألة تكون القيم الوسيطة صغيرة بما يكفي، كما أن القسمة على \(2\) و\(6\) قسمة تامة لأن الصيغ المغلقة تعطي عدداً صحيحاً لكل \(n\) صحيح موجب.
حتى الحل الذي يجمع مباشرة سيكون زمنه \(O(n)\)، لكن الاختزال الجبري يزيل التكرار كله. لذلك يكون الزمن النهائي \(O(1)\).
أما الذاكرة فهي أيضاً \(O(1)\)، لأن الحساب لا يحتاج إلا إلى عدد ثابت من القيم الصحيحة. لا توجد جداول ولا عودية ولا مصفوفات مساعدة.