notes.html

problem 65 · 24 lines

<article>
<h3>Problem Analysis</h3>
<p>
A <a class="reference-source" href="https://en.wikipedia.org/wiki/Continued_fraction" rel="noopener noreferrer" target="_blank">continued fraction</a> represents a number as a nested expression <code>a0 + 1/(a1 + 1/(a2 + ...))</code>, where the integers <code>a_k</code> are the partial quotients. If you truncate the expansion after <code>k</code> levels you get a rational number called the k-th <em>convergent</em>; these are provably the best rational approximations to the underlying real number for their denominator size. For the constant <a class="reference-source" href="https://en.wikipedia.org/wiki/E_(mathematical_constant)" rel="noopener noreferrer" target="_blank">e</a> the partial quotients follow a clean rule: <code>[2; 1, 2, 1, 1, 4, 1, 1, 6, ...]</code>, where every third quotient is an even number <code>2k</code> and all the others are <code>1</code>. The task asks for the numerator of the 100th <a class="reference-source" href="https://en.wikipedia.org/wiki/Continued_fraction" rel="noopener noreferrer" target="_blank">continued fraction</a> convergent of <a class="reference-source" href="https://en.wikipedia.org/wiki/E_(mathematical_constant)" rel="noopener noreferrer" target="_blank">e</a>, then the sum of that numerator's decimal digits.
</p>
<p>
The key observation is that I never need to evaluate the nested fraction by hand. The numerators <code>h(k)</code> and denominators of successive convergents obey the standard three-term <a class="reference-source" href="https://en.wikipedia.org/wiki/Continued_fraction#Some_useful_theorems" rel="noopener noreferrer" target="_blank">convergent recurrence</a> <code>h(k) = a(k)*h(k-1) + h(k-2)</code>, seeded with <code>h(0) = 1</code> and <code>h(1) = a(1)</code>. This turns an awkward nested division into a plain linear iteration. The one complication is magnitude: the numerator grows roughly like <code>e^n</code>, so by <code>n = 100</code> it has about 40 decimal digits - already past the range of a 64-bit integer - and by <code>n = 10000</code> it spans thousands of digits. Since each multiply-add touches all <code>O(n)</code> digits of the running value, the whole computation costs <code>O(n^2)</code> digit-operations: quadratic, but easily fast enough.
</p>
<h3>Solution Approach</h3>
<h4>Three-Term Convergent Recurrence (Python and C)</h4>
<p>
Both files compute the same quantity via the same <a class="reference-source" href="https://en.wikipedia.org/wiki/Continued_fraction#Some_useful_theorems" rel="noopener noreferrer" target="_blank">convergent recurrence</a>; they differ only in how they manage the large numerator. Each starts with a small helper, <code>e_denominator(n)</code>, that encodes the partial-quotient pattern directly: it returns <code>2</code> for <code>n == 1</code>, <code>2*(n/3)</code> when <code>3</code> divides <code>n</code>, and <code>1</code> otherwise. I chose to express the rule as a tiny function rather than a precomputed table, because the function is trivially correct for any <code>n</code> and generalises immediately without resizing anything.
</p>
<p>
The C solution iterates the recurrence directly. It seeds <code>h_prev2 = 1</code> (the artificial <code>h(0)</code> that makes the first multiply-add come out right) and <code>h_prev1 = 2</code> (which is <code>a(1)</code>). For each <code>k</code> from 2 to <code>n</code> it computes <code>h_curr = a(k)*h_prev1 + h_prev2</code> and rotates the three buffers so only the two most recent numerators survive. After the loop, <code>h_prev1</code> is the numerator of the n-th convergent, and a digit-sum pass produces the answer.
</p>
<p>
The Python solution expresses the same mathematics recursively. <code>nth_convergent_of_e</code> descends to depth <code>n</code> and then unwinds, repeatedly forming <code>a + 1/sub-result</code> using <a class="reference-source" href="https://docs.python.org/3/library/fractions.html" rel="noopener noreferrer" target="_blank"><code>fractions.Fraction</code></a> for exact rational arithmetic. This is a literal transcription of the definition of a <a class="reference-source" href="https://en.wikipedia.org/wiki/Continued_fraction" rel="noopener noreferrer" target="_blank">continued fraction</a>, so it is very easy to verify by inspection. Its cost is that it carries both numerator and denominator through every level and recurses to depth <code>n</code> - which is why it raises <code>sys.setrecursionlimit</code> - making it slower than the pure-numerator iteration at large <code>n</code>. The digit sum falls out of <code>sum_digits</code>, a repeated mod-10 / divide-10 loop.
</p>
<p>
The C version has no built-in big integers, so it supplies its own. It stores a number as an array of <code>unsigned long long</code> limbs in base <code>10^9</code> (the <code>BigInt</code> type). The workhorse is <code>bigint_mul_add(dst, a, scalar, b)</code>, which computes <code>a*scalar + b</code> in a single pass: at each limb position it forms <code>av*scalar + bv + carry</code>, stores <code>val % BASE</code>, and propagates <code>val / BASE</code>. I deliberately picked base <code>10^9</code> for two reasons. First, the product of a limb (under <code>10^9</code>) and a small scalar (at most about <code>6667</code> at <code>n = 10000</code>), plus a carry, stays comfortably within 64 bits, so no overflow can occur. Second, because the base is a power of ten, each limb is itself a block of decimal digits, so the final digit sum is a free byproduct rather than requiring a base conversion.
</p>
</article>