-
Notifications
You must be signed in to change notification settings - Fork 0
/
p057.py
37 lines (27 loc) · 893 Bytes
/
p057.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 5 13:09:57 2020
@author: zhixia liu
"""
"""
Project Euler 57: Square root convergents
It is possible to show that the square root of two can be expressed as an infinite continued fraction.
2–√=1+12+12+12+…
By expanding this for the first four iterations, we get:
1+12=32=1.5
1+12+12=75=1.4
1+12+12+12=1712=1.41666…
1+12+12+12+12=4129=1.41379…
The next three expansions are 9970, 239169, and 577408, but the eighth expansion, 1393985, 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 the denominator?
"""
#%% naive bf
results=[]
x=1
y=1
for i in range(1001):
x=x+2*y
y=x-y
if len(str(x))>len(str(y)):
results.append((x,y))
print(len(results))