notes.html
<article>
<h3>Problem Analysis</h3>
<p>
The <a class="reference-source" href="https://en.wikipedia.org/wiki/Fibonacci_sequence" rel="noopener noreferrer" target="_blank">Fibonacci sequence</a> is defined by the <a class="reference-source" href="https://en.wikipedia.org/wiki/Recurrence_relation" rel="noopener noreferrer" target="_blank">recurrence relation</a> F(n) = F(n-1) + F(n-2). Here the sequence is seeded with 1 and 2, and the task is to sum every even-valued term that does not exceed four million. The naive approach generates every <a class="reference-source" href="https://en.wikipedia.org/wiki/Fibonacci_sequence" rel="noopener noreferrer" target="_blank">Fibonacci number</a> and tests each for evenness, but a structural observation about <a class="reference-source" href="https://en.wikipedia.org/wiki/Parity_(mathematics)" rel="noopener noreferrer" target="_blank">parity</a> removes the test entirely. Writing out the <a class="reference-source" href="https://en.wikipedia.org/wiki/Parity_(mathematics)" rel="noopener noreferrer" target="_blank">parity</a> of the terms - 1 (odd), 2 (even), 3 (odd), 5 (odd), 8 (even), 13 (odd), 21 (odd), 34 (even) - shows that every third term is even. This follows directly from the addition rule on <a class="reference-source" href="https://en.wikipedia.org/wiki/Parity_(mathematics)" rel="noopener noreferrer" target="_blank">parity</a>: odd+even=odd, even+odd=odd, odd+odd=even, so the pattern repeats with period three forever.
</p>
<p>
Knowing the even terms recur every three steps, I can derive a <a class="reference-source" href="https://en.wikipedia.org/wiki/Recurrence_relation" rel="noopener noreferrer" target="_blank">recurrence</a> that steps directly from one even <a class="reference-source" href="https://en.wikipedia.org/wiki/Fibonacci_sequence" rel="noopener noreferrer" target="_blank">Fibonacci number</a> to the next, skipping the two odd ones between. If E(k) is the k-th even <a class="reference-source" href="https://en.wikipedia.org/wiki/Fibonacci_sequence" rel="noopener noreferrer" target="_blank">Fibonacci number</a>, then E(k+1) = 4*E(k) + E(k-1), which is verifiable by expanding the standard <a class="reference-source" href="https://en.wikipedia.org/wiki/Recurrence_relation" rel="noopener noreferrer" target="_blank">recurrence</a> three times. The payoff is that I need only two integer state variables and a single multiply-add per step, with no divisibility test. Because <a class="reference-source" href="https://en.wikipedia.org/wiki/Fibonacci_sequence" rel="noopener noreferrer" target="_blank">Fibonacci numbers</a> grow exponentially - each term is roughly 1.618 times the previous, the <a class="reference-source" href="https://en.wikipedia.org/wiki/Golden_ratio" rel="noopener noreferrer" target="_blank">golden ratio</a> - the count of terms below any limit L is O(log L). The algorithm therefore runs in <a class="reference-source" href="https://en.wikipedia.org/wiki/Time_complexity#Logarithmic_time" rel="noopener noreferrer" target="_blank">logarithmic time</a> and O(1) space, finishing in a handful of iterations even for a limit of four million.
</p>
<h3>Solution Approach</h3>
<h4>Direct Even-<a class="reference-source" href="https://en.wikipedia.org/wiki/Fibonacci_sequence" rel="noopener noreferrer" target="_blank">Fibonacci</a> <a class="reference-source" href="https://en.wikipedia.org/wiki/Recurrence_relation" rel="noopener noreferrer" target="_blank">Recurrence</a> (Python and C)</h4>
<p>
Both files implement the same algorithm. I keep two consecutive even <a class="reference-source" href="https://en.wikipedia.org/wiki/Fibonacci_sequence" rel="noopener noreferrer" target="_blank">Fibonacci numbers</a>, <code>even_fib_a</code> and <code>even_fib_b</code>, seeded with 2 and 8 - the first two even <a class="reference-source" href="https://en.wikipedia.org/wiki/Fibonacci_sequence" rel="noopener noreferrer" target="_blank">Fibonacci</a> terms. Each step accumulates <code>even_fib_a</code> into the running total, then advances the pair with <code>next = 4 * even_fib_b + even_fib_a</code>, shifting <code>even_fib_a = even_fib_b</code> and <code>even_fib_b = next</code>. The loop exits as soon as <code>even_fib_a</code> reaches or exceeds the limit, so the limit is never included - the "does not exceed" bound is applied strictly before accumulation.
</p>
<p>
I chose the seed (2, 8) rather than deriving it from first principles because both values are easy to confirm by inspection against the listed sequence, and a <a class="reference-source" href="https://en.wikipedia.org/wiki/Recurrence_relation" rel="noopener noreferrer" target="_blank">recurrence</a> is only as correct as its initial conditions. A wrong seed such as (0, 2) would silently corrupt every later term, since 0 is not part of the stated sequence.
</p>
<p>
The Python version wraps the iteration in a private <a class="reference-source" href="https://docs.python.org/3/glossary.html#term-generator" rel="noopener noreferrer" target="_blank">generator</a> <code>_even_fibonacci_numbers</code> and feeds it to <code>sum()</code>, cleanly separating sequence generation from aggregation. The C version is a plain <code>while</code> loop accumulating into a <code>long long</code> to guard against overflow. Both delegate argument parsing to the runner framework's <code>parse_int</code> helper, so the remaining difference is purely idiomatic: a lazy generator feeding <code>sum()</code> in Python versus an explicit accumulation loop in C. Both produce 4613732 for the four-million case; the recorded averages are about 0.42 microseconds in C and 1.6 microseconds in Python.
</p>
</article>