notes.html

problem 57 · 24 lines

<article>
<h3>Problem Analysis</h3>
<p>
The number sqrt(2) admits a representation as an infinite <a class="reference-source" href="https://en.wikipedia.org/wiki/Continued_fraction" rel="noopener noreferrer" target="_blank">continued fraction</a> - an expression formed by repeatedly nesting a term of the shape 1/(2 + 1/(2 + ...)). Truncating that infinite nesting after a finite number of levels yields a rational approximation called a <a class="reference-source" href="https://en.wikipedia.org/wiki/Convergent_(continued_fraction)" rel="noopener noreferrer" target="_blank">convergent</a>. The task is to count, among the first thousand convergents, how many have a numerator whose number of decimal digits strictly exceeds that of the denominator.
</p>
<p>
The observation that makes this tractable is that consecutive convergents are linked by a clean two-variable <a class="reference-source" href="https://en.wikipedia.org/wiki/Recurrence_relation" rel="noopener noreferrer" target="_blank">recurrence relation</a>. If the current convergent is p/q, the next one is (p + 2q)/(p + q). This follows directly from the structure of the expansion: adding one more level wraps the previous fraction as 1 + 1/(1 + p/q), and that algebraic substitution sends the pair (p, q) to (p + 2q, p + q). The fractions in the problem - 3/2, 7/5, 17/12, 41/29, 99/70, ... - all satisfy this map exactly. Because the recurrence is built from nothing but addition, I can generate every convergent with exact integer arithmetic, never touching division or floating point. The price is growth: p and q grow by roughly a factor of 1 + sqrt(2) per step, so after n steps they carry on the order of n digits and require <a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision integers</a> ("bignums"). Each step is dominated by adding two D-digit numbers where D grows linearly with the index, so the total cost is the sum 1 + 2 + ... + n, giving overall complexity of O(n^2).
</p>
<h3>Solution Approach</h3>
<h4>Iterative Convergent Recurrence with Big Integers</h4>
<p>
Both the Python and C solutions implement the same algorithm: hold the current numerator and denominator as arbitrary-precision integers, apply the map (p, q) -&gt; (p + 2q, p + q) once per expansion, and increment a counter on every step where p has more decimal digits than q.
</p>
<p>
I seed both variables at 1. This represents the state just before the first expansion: applying the <a class="reference-source" href="https://en.wikipedia.org/wiki/Recurrence_relation" rel="noopener noreferrer" target="_blank">recurrence relation</a> once gives numerator 1 + 2*1 = 3 and denominator 1 + 1 = 2, that is, the fraction 3/2 - exactly the problem's first expansion. The critical subtlety is that the two updates must be simultaneous: the new numerator depends on the *old* denominator, and the new denominator depends on the *old* numerator. I must compute both new values before overwriting either, or I corrupt the second update with the first.
</p>
<p>
In Python, <a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision integers</a> are built into the language, so the loop body is a single tuple assignment <code>numerator, denominator = (numerator + 2 * denominator, numerator + denominator)</code>. To compare magnitudes I convert each integer to its decimal string and compare lengths. That is O(D) per comparison but trivially correct. I also guard the comparison against Python 3.11+'s cap on int-to-string conversion, lifting the limit with <code>sys.set_int_max_str_digits(0)</code> only if the <code>ValueError</code> actually fires.
</p>
<p>
In C there is no native bignum, so I built a small base-10^9 big-integer type: a fixed-size array of 32-bit limbs stored little-endian (least-significant limb at index 0), each limb holding up to nine decimal digits. Two helpers do the arithmetic - <code>bi_add_twice</code> computes b + 2c (the numerator update) and <code>bi_add</code> computes b + c (the denominator update), both propagating carries across limbs. The choice of base 10^9 pays off in <code>bi_decimal_digits</code>: every limb except the topmost contributes exactly nine digits, so the digit count is 9*(size - 1) plus a short loop over the most-significant limb. I preallocated <code>MAX_LIMBS = 512</code> slots - far more than the roughly 50 limbs needed even at 10000 expansions - so the hot loop performs no heap allocation.
</p>
</article>