Problem 6 — Sum Square Difference

Problem Analysis

This problem contrasts two quantities computed over the first n natural numbers: the square of the sum, written as (1 + 2 + ... + n)², and the sum of the squares, written as 1² + 2² + ... + n². The naive approach iterates over all n numbers, accumulating both totals, which costs O(n) time - the running time grows linearly with n. The key insight is that both of these quantities are polynomial functions of n with classical closed-form expressions, so we can compute the answer in a fixed number of arithmetic operations regardless of the size of n. This is described as constant time, or O(1) complexity.

The sum of the first n natural numbers is the n-th triangular number, given by S(n) = n(n+1)/2. Squaring this yields the square of the sum. The sum of the squares has its own identity, the square pyramidal number formula, SS(n) = n(n+1)(2n+1)/6. Both identities can be proved by mathematical induction or by telescoping differences. The answer we want is simply S(n)² - SS(n). Because each formula involves only a handful of multiplications and one division, the entire computation is independent of n: it takes the same time for n = 100 as for n = 10⁹. Recognising that a loop is really computing a polynomial in disguise is the central skill this problem teaches.

Solution Approach

Closed-Form Arithmetic (Python and C)

The Python file p0006_s0.py and the C file p0006_s0.c implement the same algorithm, differing only in syntax and integer types. The logic is three steps:

First, I compute the sum of the first n natural numbers with n*(n+1)/2 and square it to obtain the square of the sum. Second, I compute the sum of the squares directly with (2*n+1)*(n+1)*n/6. Third, I subtract the second from the first and return the result. In Python this collapses into a single expression: (n * (n + 1) // 2) ** 2 - (2 * n + 1) * (n + 1) * n // 6. In C I broke the same arithmetic into named intermediate variables (sum, square_of_sum, sum_of_squares) purely for readability.

I deliberately wrote the sum-of-squares term as (2*n+1)*(n+1)*n/6 with the multiplications happening before the division. This matters because the division by 6 must be exact in integer arithmetic. Among the three factors n, n+1, and 2n+1, one of the two consecutive integers n and n+1 is always even (so the product is divisible by 2), and exactly one of n, n+1, 2n+1 is always divisible by 3. Together these guarantee divisibility by 6, so the integer division never loses a remainder and I never need floating-point arithmetic - which would risk rounding error.

The one genuine language-specific concern is overflow. In C, ordinary int arithmetic silently wraps around when intermediate values exceed the 32-bit range. I declared n and all intermediate values as long long (a 64-bit signed type) so the products never overflow for any realistic input. Python integers have arbitrary precision built in, so no such precaution is required - the interpreter grows the integer transparently. Python's // floor-division operator plays the same role as C's integer division here, since I have already proven the division is exact.