Project Euler Problem 57
0.1 Mathematical Recurrence
Notice that every expansion after 1 has the form:
\[\text{Expansion}_n = 1 + \frac{1}{D_n}\]
where \(D_n\) is the recursive nested denominator fraction:
\(D_1 = 2\)
\(D_n = 2 + \frac{1}{D_{n-1}}\)
If we compute \(D_n\) as a fraction \(\frac{a_n}{b_n}\), then:
\[D_n = 2 + \frac{b_{n-1}}{a_{n-1}} = \frac{2 a_{n-1} + b_{n-1}}{a_{n-1}}\]
Thus, the overall expansion \(\text{Expansion}_n = 1 + \frac{1}{D_n} = 1 + \frac{b_n}{a_n} = \frac{a_n + b_n}{a_n}\).
0.2 Naive Recursive Implementation (Python)
Because Python automatically handles arbitrarily large integers, you don’t have to worry about integer overflow as the numerators and denominators grow beyond 1,000 digits.
import sys
# Increase recursion depth limit to accommodate 1000 recursive calls
sys.setrecursionlimit(2000)
def get_nested_denominator(n):
"""
Returns the n-th nested denominator D_n as a tuple (numerator, denominator).
D_1 = 2 / 1
D_n = 2 + 1 / D_{n-1}
"""
if n == 1:
return (2, 1)
# Recurse to get D_{n-1} = prev_num / prev_den
prev_num, prev_den = get_nested_denominator(n - 1)
# D_n = 2 + (prev_den / prev_num) = (2 * prev_num + prev_den) / prev_num
new_num = 2 * prev_num + prev_den
new_den = prev_num
return (new_num, new_den)
def get_expansion(n):
"""
Returns the n-th total expansion as a tuple (numerator, denominator).
Expansion_n = 1 + 1 / D_n = (D_num + D_den) / D_num
"""
d_num, d_den = get_nested_denominator(n)
return (d_num + d_den, d_num)
def solve(limit=1000):
count = 0
for i in range(1, limit + 1):
num, den = get_expansion(i)
# Check if length of numerator digits exceeds denominator digits
if len(str(num)) > len(str(den)):
count += 1
return count
print("Result:", solve(1000))0.3 Direct Numerator/Denominator Recurrence (More Efficient Recursion)
The naive recursive approach above recomputes subproblems redundantly if you call get_expansion(i) in a loop, taking \(O(N^2)\) time.
If you express the numerator \(N_k\) and denominator \(D_k\) of the full expansion directly, they follow simple linear recurrences:
\(N_k = N_{k-1} + 2 D_{k-1}\)
\(D_k = N_{k-1} + D_{k-1}\)
With base case \(N_1 = 3, D_1 = 2\).
You can pass the current numerator, denominator, step count, and accumulator recursively in a single linear pass (\(O(N)\) time):
import sys
sys.setrecursionlimit(2000)
def count_expansions_rec(num, den, step, limit, count):
if step > limit:
return count
# Check digit condition for current step
if len(str(num)) > len(str(den)):
count += 1
# Recurrence relation for next step
next_num = num + 2 * den
next_den = num + den
return count_expansions_rec(next_num, next_den, step + 1, limit, count)
# Base case: step 1 is 3/2
result = count_expansions_rec(3, 2, 1, 1000, 0)
print("Result:", result)0.4 1. Continued Fractions & Linear Recurrences
Structure of Convergents: The continued fraction expansions for \(\sqrt{2}\) are the convergents of \(\sqrt{2}\).
State Reduction: Rather than evaluating deeply nested fractions from the inside out every time (which is \(O(N^2)\)), you can extract direct recurrence relations for the numerator \(N_k\) and denominator \(D_k\):
\[N_k = N_{k-1} + 2 D_{k-1}\]
\[D_k = N_{k-1} + D_{k-1}\]
This collapses nested fraction evaluation into simple integer arithmetic operating in \(O(N)\) time.
0.5 2. Best Rational Approximations (Pell’s Equation)
The fraction \(\frac{N_k}{D_k}\) isn’t just a random sequence of approximations; it yields integer solutions to Pell’s Equation:
\[N_k^2 - 2 D_k^2 = \pm 1\]
Because \(N_k^2 \approx 2 D_k^2\), taking square roots gives:
\[\frac{N_k}{D_k} \approx \sqrt{2} \approx 1.41421356\dots\]
The convergents generated by continued fractions produce the mathematically “best” rational approximations to irrational numbers for a given denominator size.
0.6 3. Logarithmic Digit Growth & The Digit Inequality
Constant Ratio: As \(k \to \infty\), both numerator and denominator grow exponentially by a constant factor equal to the silver ratio \(\delta_S = 1 + \sqrt{2} \approx 2.41421356\):
\[N_k \approx C \cdot (1 + \sqrt{2})^k\]
Digit Condition: The number of digits in an integer \(x\) is given by \(\lfloor \log_{10}(x) \rfloor + 1\).
The numerator exceeds the denominator in digits precisely when:
\[\log_{10}(N_k) - \log_{10}(D_k) \ge 1 - \{\log_{10}(D_k)\}\]
Since \(N_k / D_k \approx \sqrt{2}\), we have:
\[\log_{10}(N_k) - \log_{10}(D_k) = \log_{10}\left(\frac{N_k}{D_k}\right) \approx \log_{10}(\sqrt{2}) \approx 0.150514\]
Therefore, the numerator gains an extra digit whenever the fractional part \(\{\log_{10}(D_k)\}\) falls in the narrow window between \(1 - \log_{10}(\sqrt{2}) \approx 0.849485\) and \(1.0\).
0.7 4. Computational Efficiency (Tail Recursion vs. Loop)
Stack Depth Limits: Naive recursion risks overflowing the call stack for large \(N\) (e.g., Python’s default limit is 1,000).
Tail Call Optimizations / Iteration: Moving from top-down subproblem evaluation to bottom-up state propagation demonstrates why stateful loops (or tail recursion) are standard for linear recurrence problems.