diff options
| -rw-r--r-- | julia/057-square_root_convergents.jl | 41 |
1 files changed, 41 insertions, 0 deletions
diff --git a/julia/057-square_root_convergents.jl b/julia/057-square_root_convergents.jl new file mode 100644 index 0000000..de2ba1f --- /dev/null +++ b/julia/057-square_root_convergents.jl @@ -0,0 +1,41 @@ +### +# 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) |