ホーム - 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 について奇数の周期をもつ平方根が何個あるか答えよ.

(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)