Project Euler

Project Euler Problem 65

steloflute 2012. 10. 11. 12:47
http://projecteuler.net/problem=65

Problem 65

12 March 2004

The square root of 2 can be written as an infinite continued fraction.

√2 = 1 +
1

  2 +
1

    2 +
1

      2 +
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 +
1

= 3/2
 
2
 
1 +
1

= 7/5
  2 +
1

   
2
 
1 +
1

= 17/12
  2 +
1

 
    2 +
1

 
     
2
 
1 +
1

= 41/29
  2 +
1

    2 +
1

 
      2 +
1

 
       
2
 

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.


Answer:
272



* Racket

#lang racket
; e
; (2;1,2,1,1,4,1,1,6,1)
; (+ 2 (/ (+ 1 (/ (+ 2 (/ 1))))))

(define (e digit)
  (let ([m (modulo digit 3)])
    (if (= m 1)
        (* 2 (add1 (quotient digit 3)))
        1)))

(define digits (map e (range 0 99)))

(define (calc digits)
  (if (null? digits)
      0
      (/ (+ (first digits) (calc (rest digits))))))

(define result (+ 2 (calc digits)))
result
(define numerator* (numerator result))
numerator*
(let loop ([n numerator*]
           [sum 0])
  (if (> n 0)
      (loop (quotient n 10) (+ sum (modulo n 10)))
      sum))





'Project Euler' 카테고리의 다른 글

Project Euler Problem 67  (0) 2013.09.02
Project Euler Solutions in Racket  (0) 2012.10.17
Project Euler Problem 64  (0) 2012.10.07
Project Euler Problem 63  (0) 2012.10.05
Project Euler Problem 62  (0) 2012.10.05