Problem 64 » 履歴 » リビジョン 2
リビジョン 1 (Noppi, 2024/01/28 12:19) → リビジョン 2/4 (Noppi, 2024/01/28 12:33)
[ホーム](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$ a0 + 1 / ($a_1$ (a1 + 1 / ($a_2$ (a2 + 1 / ($a_3$ (a3 + ...)))
例えば, √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$ a0 = 4, 1/(√23-4) = (√23+4)/7 = 1 + (√23-3)/7
* $a_1$ a1 = 1, 7/(√23-3) = 7(√23+3)/14 = 3 + (√23-3)/2
* $a_2$ a2 = 3, 2/(√23-3) = 2(√23+3)/14 = 1 + (√23-4)/7
* $a_3$ a3 = 1, 7/(√23-4) = 7(√23+4)/7 = 8 + (√23-4)
* $a_4$ a4 = 8, 1/(√23-4) = (√23+4)/7 = 1 + (√23-3)/7
* $a_5$ a5 = 1, 7/(√23-3) = 7(√23+3)/14 = 3 + (√23-3)/2
* $a_6$ a6 = 3, 2/(√23-3) = 2(√23+3)/14 = 1 + (√23-4)/7
* $a_7$ a7 = 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
```