project-euler–problem 65

September 16, 2012
By

(This article was first published on YGC » R, and kindly contributed to R-bloggers)

The square root of 2 can be written as an infinite continued fraction.
\( \sqrt{2} = 1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+?}}}} \)

The infinite continued fraction can be written, √2 = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, √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 √2.

\( 1+\frac{1}{2} = 3/2 \)
\( 1+\frac{1}{2+\frac{1}{2}} = 7/5 \)
\( 1+\frac{1}{2+\frac{1}{2+\frac{1}{2}}} = 17/12 \)
\( 1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2}}}} = 41/29 \)

Hence the sequence of the first ten convergents for √2 are:
1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 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, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 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.

?View Code RSPLUS
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
e.expand <- function(n) {
    e0 <- 2
    e <- c(1,2,1)
    add <- c(0,2,0)
 
    len <- floor(n/3)-1
    x <- sapply(0:len, function(i) add * i) + e
    x <- as.vector(x)
    res <- c(e0, x)
    return(res)
}
 
get.fraction <- function(x) {
    ## 1/(x0 + a/x1)
    n <- length(x)
    x1 <- x[n-1] * x[n-2] + 1
    a <- x[n-2]
 
    for (i in (n-2):1) {
        old.x1 <- x1;
        x1 <- x[i] * x1 + a
        a <- old.x1
    }
    res <- list(numerator=x1, denumerator=a)
    return (res)
}
 
e <- e.expand(100)
res <- get.fraction(e)
numerator <- as.character(gmp::as.bigz(res$numerator))
s <- sum(as.numeric(unlist(strsplit(numerator, ""))))
print(s)

Related Posts

To leave a comment for the author, please follow the link and comment on his blog: YGC » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.