Python Implementation of Problem 57
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 57
Problem:
It is possible to show that the square root of two can be expressed as an infinite continued fraction.
√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
By expanding this for the first four iterations, we get:
1 + 1/2 = 3/2 = 1.5 1 + 1/(2 + 1/2) = 7/5 = 1.4 1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666... 1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.
In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?
1"""
2Project Euler Problem 57
3
4Problem:
5
6It is possible to show that the square root of two can be expressed as an infinite continued fraction.
7
8√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
9
10By expanding this for the first four iterations, we get:
11
121 + 1/2 = 3/2 = 1.5
131 + 1/(2 + 1/2) = 7/5 = 1.4
141 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
151 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
16
17The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example
18where the number of digits in the numerator exceeds the number of digits in the denominator.
19
20In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?
21"""
22from fractions import Fraction
23from typing import MutableMapping
24
25from .lib.iters import digits
26
27
28def root_two_denominator(n: int, cache: MutableMapping[int, Fraction]) -> Fraction:
29 if n in cache:
30 return cache[n]
31 if n == 0:
32 result = Fraction(2, 1)
33 else:
34 result = 2 + Fraction(1, root_two_denominator(n - 1, cache))
35 cache[n] = result
36 return result
37
38
39def root_two_expansion(n: int, cache: MutableMapping[int, Fraction]) -> Fraction:
40 return 1 + Fraction(1, root_two_denominator(n, cache))
41
42
43def main() -> int:
44 answer = 0
45 cache: MutableMapping[int, Fraction] = {}
46 for x in range(1_000):
47 frac = root_two_expansion(x, cache)
48 if len([*digits(frac.numerator)]) > len([*digits(frac.denominator)]):
49 answer += 1
50 return answer