2の平方根は無限連分数として書くことができる。

$\displaystyle \sqrt{2} = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \dots}}}}$

この無限連分数を$\sqrt{2} = [1;(2)]$と表記することもできる。$(2)$は2が際限なく繰り返されることを示す。同様に$\sqrt{23} = [4;(1,3,1,8)]$である。

平方根の部分的な連分数の数列から良い有理近似が得られることが分かる.$\sqrt{2}$の近似分数について考えよう。

$\displaystyle 1 + \frac{1}{2} = \frac{3}{2}$

$\displaystyle 1 + \frac{1}{2 + \frac{1}{2}} = \frac{7}{5}$

$\displaystyle 1 + \frac{1}{2 + \frac{1}{2+\frac{1}{2}}} = \frac{17}{12}$

$\displaystyle 1 + \frac{1}{2 + \frac{1}{2+\frac{1}{2 + \frac{1}{2}}}} = \frac{41}{29}$

従って, $\sqrt{2}$の近似分数からなる数列の最初の10項は：

$\displaystyle 1, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \frac{239}{169}, \frac{577}{408}, \frac{1393}{985}, \frac{3363}{2378}, \dots$

もっとも驚くべきことに, 数学的に重要な定数$e$は次のように表せて、 $e = [2; 1,2,1, 1,4,1, 1,6,1 , \dots , 1,2k,1, \dots]$

$e$ の近似分数からなる数列の最初の10項は：

$\displaystyle 2, 3, \frac{8}{3}, \frac{11}{4}, \frac{19}{7}, \frac{87}{32}, \frac{106}{39}, \frac{193}{71}, \frac{1264}{465}, \frac{1457}{536}, \dots$

第10項の近似分数の分子の桁を合計すると$1+4+5+7=17$である。

$e$についての連分数である近似分数の第100項の分子の桁の合計を求めよ。

5桁の数 $16807 = 7^5$は自然数を5乗した数である. 同様に9桁の数 $134217728 = 8^9$も自然数を9乗した数である.

自然数を $n$ 乗して得られる $n$ 桁の正整数は何個あるか?

立方数 $41063625 \; (345^3)$は, 桁の順番を入れ替えると2つの立方数になる: $56623104 \; (384^3)$ と $66430125 \; (405^3)$ である. $41063625$は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.

立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.

次の形式の, 2次のディオファントス方程式を考えよう:

$x^2 - Dy^2 = 1$

たとえば$D=13$のとき, $x$ を最小にする解は$649^2 - 13×180^2 = 1$である.

$D$が平方数のとき, 正整数のなかに解は存在しないと考えられる.

$D = \{2, 3, 5, 6, 7\}$に対して$x$を最小にする解は次のようになる:

• $3^2 - 2×2^2 = 1$

• $2^2 - 3×1^2 = 1$

• $9^2 - 5×4^2 = 1$(9を強調したい)

• $5^2 - 6×2^2 = 1$

• $8^2 - 7×3^2 = 1$

したがって,$D ≤ 7$に対して$x$を最小にする解を考えると,$D=5$のとき$x$は最大である.

$D ≤ 1000$に対する$x$を最小にする解で,$x$が最大になるような$D$の値を見つけよ.

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

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

例えば, $\sqrt{23}$を考えよう.

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

となる.

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

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

を得る.

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

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

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

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

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

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

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

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

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

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

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

• $\sqrt{2}=[1;(2)]$, 周期 1

• $\sqrt{3}=[1;(1,2)]$, 周期 2

• $\sqrt{5}=[2;(4)]$, 周期 1

• $\sqrt{6}=[2;(2,4)]$, 周期 2

• $\sqrt{7}=[2;(1,1,1,4)]$, 周期 4

• $\sqrt{8}=[2;(1,4)]$, 周期 2

• $\sqrt{10}=[3;(6)]$, 周期 1

• $\sqrt{11}=[3;(3,6)]$, 周期 2

• $\sqrt{12}= [3;(2,6)]$, 周期 2

• $\sqrt{13}=[3;(1,1,1,1,6)]$, 周期 5

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

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

三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.

3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.

1. この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する

2. それぞれ多角数である: 三角数 ($P_{3,127}=8128$), 四角数 ($P_{4,91}=8281$), 五角数 ($P_{5,44}=2882$) がそれぞれ別の数字で集合に含まれている

3. 4桁の数の組で上の2つの性質を持つのはこの組だけである.

三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て現れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ.

下図の三角形の頂点から下まで移動するとき, その数値の合計の最大値は23になる。

(3,7,4,9を強調したい)

この例では 3 + 7 + 4 + 9 = 23

100行からなる三角形を持つ15Kのテキストファイル （右クリックして、『名前をつけてリンク先を保存』）の上から下までの最大合計を見つけよ。

注：これは のずっと難しいバージョンである。 全部で通りの組み合わせがあるので、この問題を解くのに全ての経路を試すことは不可能である！ 毎秒1兆()本の経路を調べることができたとしても、全てを調べるには200億年以上かかるだろう。 この問題を解く効率的なアルゴリズムがある ;o)

オイラーのトーティエント関数$φ(n)$(ファイ関数とも呼ばれる) とは,$n$未満の正の整数で$n$と互いに素なものの個数を表す. 例えば, 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので,$φ(9) = 6$となる. 1 は全ての正の整数と互いに素であるとみなされる. よって$φ(1) = 1$である.

面白いことに,$φ(87109)=79180$であり, $87109$は$79180$を置換したものとなっている.

$1 < n < 10^7$で$φ(n)$が$n$を置換したものになっているもののうち,$n/φ(n)$が最小となる$n$を求めよ.

下に示す図のようなものを"magic" 3-gon ringという. これは1～6の数字を当てはめて, 各列の数字の和が9となっている. これを例として説明する.

外側のノードのうち一番小さいものの付いた列(例では4,3,2)から時計回りに回ってそれぞれ列の数字を3つ連ねて説明する. 例えば例のものは4,3,2; 6,2,1; 5,1,3という組で説明することができる.

1～6の数字を当てはめて, 各列の数字の和が等しくなるものは次の8通りある.

この組の各数字を連結して, 9桁の数字で表すことができる. 例えば, 上の図のものは4,3,2; 6,2,1; 5,1,3であるので432621513である.

さて, 下の図に1～10の数字を当てはめ, 各列の数字の和が等しくなる"magic" 5-gon ringを作って, それを表す16桁または17桁の数字のうち, 16桁のものの最大の数字を答えよ.

(注, 3つの場合の例を見ても分かる通り, 列の始まりの数字を比べた時一番小さい数字で始まる列から時計回りに繋げるという条件のもとで文字列を生成する必要があります. この条件下で最大となる数字を答えてください. )

オイラーのトーティエント関数$φ(n)$(ファイ関数とも呼ばれる) とは,$n$未満の正の整数で$n$と互いに素なものの個数を表す. 例えば, 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので,$φ(9) = 6$となる.

$n ≤ 10$では$n/φ(n)$の最大値は$n=6$であることがわかる.

$n ≤ 1,000,000$で$n/φ(n)$が最大となる値を見つけよ.