Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]

# [[Problem 64]]

## Odd Period Square Roots

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

$\displaystyle \quad \quad \sqrt{N}=a_0+\frac 1 {a_1+\frac 1 {a_2+ \frac 1 {a3+ \dots}}}$

For example, let us consider $\sqrt{23}:$

$\quad \quad \sqrt{23}=4+\sqrt{23}-4=4+\frac 1 {\frac 1 {\sqrt{23}-4}}=4+\frac 1  {1+\frac{\sqrt{23}-3}7}$

If we continue we would get the following expansion:

$\displaystyle \quad \quad \sqrt{23}=4+\frac 1 {1+\frac 1 {3+ \frac 1 {1+\frac 1 {8+ \dots}}}}$

The process can be summarised as follows:

$\quad \quad a_0=4, \frac 1 {\sqrt{23}-4}=\frac {\sqrt{23}+4} 7=1+\frac {\sqrt{23}-3} 7$

$\quad \quad a_1=1, \frac 7 {\sqrt{23}-3}=\frac {7(\sqrt{23}+3)} {14}=3+\frac {\sqrt{23}-3} 2$

$\quad \quad a_2=3, \frac 2 {\sqrt{23}-3}=\frac {2(\sqrt{23}+3)} {14}=1+\frac {\sqrt{23}-4} 7$

$\quad \quad a_3=1, \frac 7 {\sqrt{23}-4}=\frac {7(\sqrt{23}+4)} 7=8+\sqrt{23}-4$

$\quad \quad a_4=8, \frac 1 {\sqrt{23}-4}=\frac {\sqrt{23}+4} 7=1+\frac {\sqrt{23}-3} 7$

$\quad \quad a_5=1, \frac 7 {\sqrt{23}-3}=\frac {7 (\sqrt{23}+3)} {14}=3+\frac {\sqrt{23}-3} 2$

$\quad \quad a_6=3, \frac 2 {\sqrt{23}-3}=\frac {2(\sqrt{23}+3)} {14}=1+\frac {\sqrt{23}-4} 7$

$\quad \quad a_7=1, \frac 7 {\sqrt{23}-4}=\frac {7(\sqrt{23}+4)} {7}=8+\sqrt{23}-4$

It can be seen that the sequence is repeating. For conciseness, we use the notation $\sqrt{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:

$\quad \quad \sqrt{2}=[1;(2)]$, period=$1$

$\quad \quad \sqrt{3}=[1;(1,2)]$, period=$2$

$\quad \quad \sqrt{5}=[2;(4)]$, period=$1$

$\quad \quad \sqrt{6}=[2;(2,4)]$, period=$2$

$\quad \quad \sqrt{7}=[2;(1,1,1,4)]$, period=$4$

$\quad \quad \sqrt{8}=[2;(1,4)]$, period=$2$

$\quad \quad \sqrt{10}=[3;(6)]$, period=$1$

$\quad \quad \sqrt{11}=[3;(3,6)]$, period=$2$

$\quad \quad \sqrt{12}=[3;(2,6)]$, period=$2$

$\quad \quad \sqrt{13}=[3;(1,1,1,1,6)]$, period=$5$

Exactly four continued fractions, for $N \le 13$, have an odd period.

How many continued fractions for $N \le 10\,000$ have an odd period?

## 奇数周期の平方根

平方根は連分数の形で表したときに周期的であり, 以下の形で書ける:

√N = $a_0$ + 1 / ($a_1$ + 1 / ($a_2$ + 1 / ($a_3$ + ...)))

例えば, √23を考えよう.

√23 = 4 + √23 - 4 = 4 + 1 / (1 / (√23 - 4)) = 4 + 1 / (1 + (√23 - 3) / 7)

となる.

この操作を続けていくと,

√23 = 4 + 1 / (1 + 1 / (3 + 1 / (1 + 1 / (8 + ...))))

を得る.

操作を纏めると以下になる:

* $a_0$ = 4, 1/(√23-4) = (√23+4)/7 = 1 + (√23-3)/7

* $a_1$ = 1, 7/(√23-3) = 7(√23+3)/14 = 3 + (√23-3)/2

* $a_2$ = 3, 2/(√23-3) = 2(√23+3)/14 = 1 + (√23-4)/7

* $a_3$ = 1, 7/(√23-4) = 7(√23+4)/7 = 8 + (√23-4)

* $a_4$ = 8, 1/(√23-4) = (√23+4)/7 = 1 + (√23-3)/7

* $a_5$ = 1, 7/(√23-3) = 7(√23+3)/14 = 3 + (√23-3)/2

* $a_6$ = 3, 2/(√23-3) = 2(√23+3)/14 = 1 + (√23-4)/7

* $a_7$ = 1, 7/(√23-4) = 7(√23+4)/7 = 8 + (√23-4)

よって, この操作は繰り返しになることが分かる. 表記を簡潔にするために, √23 = [4;(1,3,1,8)]と表す. (1,3,1,8)のブロックは無限に繰り返される項を表している.

最初の10個の無理数である平方根を連分数で表すと以下になる.

* √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

N ≤ 13で奇数の周期をもつ平方根は丁度4つある.

N ≤ 10000 について奇数の周期をもつ平方根が何個あるか答えよ.

```scheme

(import (scheme base)

        (gauche base)

        (util match)

        (scheme inexact))

;;; a + (√b - c) / d → (a b c d)

;;;

;;; (√b - c) / d を有理化する →

;;; (d * (√b + c)) / (b - c^2)

;;;

;;; d / (b - c^2) を既約分数にして 1/q と置く →

;;; (√b + c) / q

(define (next-fraction lis)

  (assume (= (length lis) 4))

  (match-let1 (a b c d)

              lis

              (let-values ([(isqrt-b _) (exact-integer-sqrt b)])

                (if (<= d (- (sqrt b) c))

                  `(,(+ a (* d isqrt-b)) ,b ,(+ c isqrt-b) ,d)

                  (let* ([q (/ (- b (* c c))

                               d)]

                         [next-a (div (+ isqrt-b c)

                                      q)]

                         [next-b b]

                         [next-c (- (* q next-a) c)]

                         [next-d q])

                    `(,next-a ,next-b ,next-c ,next-d))))))

(define (continued-fraction-list num)

  (assume (exact-integer? num))

  (assume (<= 2 num))

  (let* ([first-fraction (next-fraction `(0 ,num 0 1))]

         [first-int (car first-fraction)]

         [end-fraction (next-fraction first-fraction)]

         [result `(,(car end-fraction) ,first-int)])

    (let loop ([current-fraction (next-fraction end-fraction)]

               [result result])

      (if (equal? current-fraction end-fraction)

        (reverse result)

        (loop (next-fraction current-fraction)

              (cons (car current-fraction) result))))))

(define (non-square-num-list num)

  (filter (^n

            (let-values ([(_ b) (exact-integer-sqrt n)])

              (not (zero? b))))

          (iota (- num 1) 2)))

(define answer-64

  (length

    (filter (^[lis]

              (even? (length lis)))

            (map (^n

                   (continued-fraction-list n))

                 (non-square-num-list 10000)))))

(format #t "64: ~d~%" answer-64)

```