###
# Square root convergents
# Problem 57
#
# It is possible to show that the square root of two can be expressed as an infinite
# continued fraction.
# $\sqrt 2 =1+ \frac 1 {2+ \frac 1 {2 +\frac 1 {2+ \dots}}}$
# By expanding this for the first four iterations, we get:
# $1 + \frac 1 2 = \frac  32 = 1.5$
# $1 + \frac 1 {2 + \frac 1 2} = \frac 7 5 = 1.4$
# $1 + \frac 1 {2 + \frac 1 {2+\frac 1 2}} = \frac {17}{12} = 1.41666 \dots$
# $1 + \frac 1 {2 + \frac 1 {2+\frac 1 {2+\frac 1 2}}} = \frac {41}{29} = 1.41379 \dots$
# The next three expansions are $\frac {99}{70}$, $\frac {239}{169}$, and $\frac
# {577}{408}$, but the eighth expansion, $\frac {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?
###


cache = Dict()

# julia automaticly convert the result to a Rational{BigInt} when we add the return type
# no need to add big()
function two_approx(n)::Rational{BigInt}
    if haskey(cache, n)
        return cache[n]
    end
    if n == 1
        return 1 + 1 // 2
    end
    cache[n] = 1 + 1 // (1 + two_approx(n - 1))
    return cache[n]
end

result = count(
    q -> length(string(numerator(q))) > length(string(denominator(q))),
    two_approx(n) for n in 1:1000
)

println(result)