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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
###
# Convergents of e
# Problem 65
#
# The square root of 2 can be written as an infinite continued fraction.
# $\sqrt{2} = 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + ...}}}}$
# The infinite continued fraction can be written, $\sqrt{2} = [1; (2)]$, $(2)$ indicates
# that 2 repeats ad infinitum. In a similar way, $\sqrt{23} = [4; (1, 3, 1, 8)]$.
# It turns out that the sequence of partial values of continued fractions for square roots
# provide the best rational approximations. Let us consider the convergents for $\sqrt{2}$.
# $
# 1 + \dfrac{1}{2} = \dfrac{3}{2}\\
# 1 + \dfrac{1}{2 + \dfrac{1}{2}} = \dfrac{7}{5}\\
# 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2}}} = \dfrac{17}{12}\\
# 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2}}}} = \dfrac{41}{29}
# $
# Hence the sequence of the first ten convergents for $\sqrt{2}$ are:
# $1, \dfrac{3}{2}, \dfrac{7}{5}, \dfrac{17}{12}, \dfrac{41}{29}, \dfrac{99}{70},
# \dfrac{239}{169}, \dfrac{577}{408}, \dfrac{1393}{985}, \dfrac{3363}{2378}, ...$
# What is most surprising is that the important mathematical constant,$e = [2; 1, 2, 1, 1,
# 4, 1, 1, 6, 1, ... , 1, 2k, 1, ...]$.
# The first ten terms in the sequence of convergents for e are:
# $2, 3, \dfrac{8}{3}, \dfrac{11}{4}, \dfrac{19}{7}, \dfrac{87}{32}, \dfrac{106}{39},
# \dfrac{193}{71}, \dfrac{1264}{465}, \dfrac{1457}{536}, ...$
# The sum of digits in the numerator of the 10th convergent is $1 + 4 + 5 + 7 = 17$.
# Find the sum of digits in the numerator of the 100th convergent of the continued fraction
# for $e$.
###
# blackpenredpen continuous fractions: https://www.youtube.com/watch?v=vw4eYXMWYEw
#
# the notation for continuous fraction is [start, (sequence)]:
#
# 1
# start + ---------------
# 1
# sequence[1] + ----------------
# sequence[2] + ...
using Base.Iterators
function converge(start, sequence, len)
function rec(sequence, len)::Rational{BigInt}
len == 1 && return 0
return 1 // (sequence[1] + rec(circshift(sequence, -1), len - 1))
end
return start + rec(sequence, len)
end
result = (
collect(flatten((1, 2k, 1) for k in 1:1000)) |>
x ->converge(2, x, 100) |>
numerator |>
digits |>
sum
)
println(result)
|
