Project Euler

Project Euler Problem 64

steloflute 2012. 10. 7. 23:21

http://projecteuler.net/problem=64


Problem 64

27 February 2004

All square roots are periodic when written as continued fractions and can be written in the form:

√N = a0 +
1
  a1 +
1
    a2 +
1
      a3 + ...

For example, let us consider √23:

√23 = 4 + √23 — 4 = 4 + 
1
 = 4 + 
1
 
1
√23—4
  1 + 
√23 – 3
7

If we continue we would get the following expansion:

√23 = 4 +
1
  1 +
1
    3 +
1
      1 +
1
        8 + ...

The process can be summarised as follows:

a0 = 4,  
1
√23—4
 = 
√23+4
7
 = 1 + 
√23—3
7
a1 = 1,  
7
√23—3
 = 
7(√23+3)
14
 = 3 + 
√23—3
2
a2 = 3,  
2
√23—3
 = 
2(√23+3)
14
 = 1 + 
√23—4
7
a3 = 1,  
7
√23—4
 = 
7(√23+4)
7
 = 8 +  √23—4
a4 = 8,  
1
√23—4
 = 
√23+4
7
 = 1 + 
√23—3
7
a5 = 1,  
7
√23—3
 = 
7(√23+3)
14
 = 3 + 
√23—3
2
a6 = 3,  
2
√23—3
 = 
2(√23+3)
14
 = 1 + 
√23—4
7
a7 = 1,  
7
√23—4
 = 
7(√23+4)
7
 = 8 +  √23—4

It can be seen that the sequence is repeating. For conciseness, we use the notation √23 = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.

The first ten continued fraction representations of (irrational) square roots are:

√2=[1;(2)], period=1
√3=[1;(1,2)], period=2
√5=[2;(4)], period=1
√6=[2;(2,4)], period=2
√7=[2;(1,1,1,4)], period=4
√8=[2;(1,4)], period=2
√10=[3;(6)], period=1
√11=[3;(3,6)], period=2
√12= [3;(2,6)], period=2
√13=[3;(1,1,1,1,6)], period=5

Exactly four continued fractions, for N ≤ 13, have an odd period.

How many continued fractions for N ≤ 10000 have an odd period?


Answer:
1322



* Racket


#lang racket
(define (period-root n)
  (define limit (floor (sqrt n)))
  (if (= n (sqr limit))
      0
      (let ([period 0]
            [d 1]
            [m 0]
            [a limit])
        (let loop ()         
          (set! m (- (* d a) m))
          (set! d (quotient (- n (sqr m)) d))
          (set! a (quotient (+ limit m) d))
          (set! period (add1 period))
          (unless (= a (* 2 limit)) (loop)))
        period)))

(for/sum ([n (in-range 2 10001)])
  (modulo (period-root n) 2))



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

Project Euler Solutions in Racket  (0) 2012.10.17
Project Euler Problem 65  (0) 2012.10.11
Project Euler Problem 63  (0) 2012.10.05
Project Euler Problem 62  (0) 2012.10.05
Project Euler Problem 61  (0) 2012.10.04