notes.html

problem 6 · 63 lines

<article>
<h3>Problem Analysis</h3>
<p>
    This problem contrasts two quantities computed over the first n natural numbers: the
    <em>square of the sum</em>, written as (1 + 2 + ... + n)<sup>2</sup>, and the
    <em>sum of the squares</em>, written as 1<sup>2</sup> + 2<sup>2</sup> + ... + n<sup>2</sup>.
    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 <em>polynomial functions of n</em> 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
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Time_complexity#Constant_time" rel="noopener noreferrer" target="_blank">constant time</a>,
    or O(1) complexity.
  </p>
<p>
    The sum of the first n natural numbers is the n-th
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Triangular_number" rel="noopener noreferrer" target="_blank">triangular number</a>,
    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
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Square_pyramidal_number" rel="noopener noreferrer" target="_blank">square pyramidal number</a>
    formula, SS(n) = n(n+1)(2n+1)/6. Both identities can be proved by
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Mathematical_induction" rel="noopener noreferrer" target="_blank">mathematical induction</a>
    or by telescoping differences. The answer we want is simply S(n)<sup>2</sup> - 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<sup>9</sup>.
    Recognising that a loop is really computing a polynomial in disguise is the central skill this
    problem teaches.
  </p>
<h3>Solution Approach</h3>
<h4>Closed-Form Arithmetic (Python and C)</h4>
<p>
    The Python file <code>p0006_s0.py</code> and the C file <code>p0006_s0.c</code> implement the
    same algorithm, differing only in syntax and integer types. The logic is three steps:
  </p>
<p>
    First, I compute the sum of the first n natural numbers with <code>n*(n+1)/2</code> and square
    it to obtain the square of the sum. Second, I compute the sum of the squares directly with
    <code>(2*n+1)*(n+1)*n/6</code>. Third, I subtract the second from the first and return the
    result. In Python this collapses into a single expression:
    <code>(n * (n + 1) // 2) ** 2 - (2 * n + 1) * (n + 1) * n // 6</code>. In C I broke the same
    arithmetic into named intermediate variables (<code>sum</code>, <code>square_of_sum</code>,
    <code>sum_of_squares</code>) purely for readability.
  </p>
<p>
    I deliberately wrote the sum-of-squares term as <code>(2*n+1)*(n+1)*n/6</code> with the
    multiplications happening before the division. This matters because the division by 6 must be
    <em>exact</em> 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.
  </p>
<p>
    The one genuine language-specific concern is overflow. In C, ordinary <code>int</code>
    arithmetic silently wraps around when intermediate values exceed the 32-bit range. I declared
    n and all intermediate values as <code>long long</code> (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
    <code>//</code> floor-division operator plays the same role as C's integer division here, since
    I have already proven the division is exact.
  </p>
</article>