"""
Problem 57: https://projecteuler.net/problem=57

It is possible to show that the square root of two can be expressed as an infinite
continued fraction.

sqrt(2) = 1 + 1 / (2 + 1 / (2 + 1 / (2 + ...)))

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 the denominator?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/18
'''




import math
def solution(limit: int = 10000) -> int:
    '''
    a1 = 1 + 1 / 2 = 3 / 2 = 1.5
    a2 = 1 + 1 / (2 + 1 / 2} = 7 / 5 = 1.4
    a3 = 1 + 1 / (2 + 1 / (2 + 1 / 2)) = 17 / 12 = 1.41666...
    ...
    a(k+1) = 1 + 1 / (ak + 1)    k>=1
           = (y + 2*x)/(y + x)   if ak = y/x

    >>> assert solution(8)==1
    >>> assert solution(7)==0
    '''

    count = 0

    times = 1
    ak = (3, 2)  # k = 1
    while times < limit:
        y, x = ak
        y1, x1 = y + 2*x, y + x
        g = math.gcd(y1, x1)
        y1, x1 = y1//g, x1//g

        ak = (y1, x1)
        # print(ak)
        if len(str(y1)) > len(str(x1)):

            count += 1

        times += 1

    return count


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 1508