Problem 64 » 履歴 » リビジョン 3
リビジョン 2 (Noppi, 2024/01/28 12:33) → リビジョン 3/4 (Noppi, 2024/01/29 09:34)
[ホーム](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* ([temp-frac (/ d
(- b
(* c c)))]
[q (denominator temp-frac)]
[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)
```