problem 57 in julia

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)