blob: de2ba1fc4ad8994c90106459d5165c9d7250c57b (
plain)
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
38
39
40
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)
|
