- 数学の本 第87巻
198 ：１３２人目の素数さん[]：2019/12/03(火) 18:57:07.75 ID:b5QWSNPE - >>192
確かに性格が良さそうですよね。
一般人の頭にある数学者のイメージというと
■見た目・中身ともにオタクっぽい。
■陰険
■暗い性格
■執念深い
などといったイメージですよね。
|
- 高校数学の質問スレPart402
433 ：１３２人目の素数さん[]：2019/12/03(火) 21:03:10.46 ID:b5QWSNPE - (3 + Sqrt[5])^n の整数部分を 1000 で割った余りを Θ(log(n)) で計算するアルゴリズムを書け。
|
- 数学の本 第87巻
199 ：１３２人目の素数さん[]：2019/12/03(火) 21:04:30.89 ID:b5QWSNPE - プログラミングコンテストチャレンジブック第2版を読んでいます。
以下の問題があります。解ける人はいますか？
(3 + Sqrt[5])^n の整数部分を 1000 で割った余りを Θ(log(n)) で計算するアルゴリズムを書け。
|
- 数学の本 第87巻
203 ：１３２人目の素数さん[]：2019/12/03(火) 23:58:33.87 ID:b5QWSNPE - それでは正解を書きます。
|
- 数学の本 第87巻
204 ：１３２人目の素数さん[]：2019/12/03(火) 23:58:51.62 ID:b5QWSNPE - n ≧ 1 とする。
(3 + Sqrt[5])^n = a_n + b_n * Sqrt[5]
a_n, b_n ∈ {1, 2, …}
と書けます。
正の整数列 (a_n), (b_n) を↑で定義します。
a_1 = 3
b_0 = 1
です。
明らかに、
(3 - Sqrt[5])^n = a_n - b_n * Sqrt[5]
が成り立ちます。
(3 + Sqrt[5])^n + (3 - Sqrt[5])^n = 2*a_n
が成り立ちます。
5 < 3^2 より、 Sqrt[5] < 3
∴ 0 < 3 - Sqrt[5]
2 = Sqrt[4] < Sqrt[5]
∴ 3 - Sqrt[5] < 1
∴ 0 < 3 - Sqrt[5] < 1
∴ 0 < (3 - Sqrt[5])^n < 1
∴ 0 < 2*a_n - (3 + Sqrt[5])^n < 1
∴ 2*a_n - 1 < (3 + Sqrt[5])^n < 2*a_n
∴ (3 + Sqrt[5])^n の整数部分は 2*a_n - 1 である。
以上より、 a_n が計算できれば、 (3 + Sqrt[5])^n の整数部分を 1000 で割った余りは、
2*a_n - 1 mod 1000
で求まる。
|
- 数学の本 第87巻
205 ：１３２人目の素数さん[]：2019/12/03(火) 23:59:07.60 ID:b5QWSNPE - a_n + b_n*Sqrt[5] = (3 + Sqrt[5])^n = (3 + Sqrt[5])*(3 + Sqrt[5])^(n-1) = (3 + Sqrt[5])*(a_{n-1} + b_{n-1} * Sqrt[5])
=
(3*a_{n-1} + 5*b_{n-1}) + (a_{n-1} + 3*b_{n-1}) * Sqrt[5]
M := {{3, 5}, {1, 3}}
とおけば、
{a_n, b_n} = M * {a_{n-1}, b_{n-1}}
が成り立ちます。
{a_n, b_n} = M^(n-1) * {a_1, b_1}
M^(n-1) は繰り返し2乗法で計算すれば、 Θ(log(n)) で計算できる。
|
- 高校数学の質問スレPart402
435 ：１３２人目の素数さん[]：2019/12/03(火) 23:59:36.84 ID:b5QWSNPE - それでは正解を書きます。
|
- 高校数学の質問スレPart402
436 ：１３２人目の素数さん[]：2019/12/03(火) 23:59:53.05 ID:b5QWSNPE - n ≧ 1 とする。
(3 + Sqrt[5])^n = a_n + b_n * Sqrt[5]
a_n, b_n ∈ {1, 2, …}
と書けます。
正の整数列 (a_n), (b_n) を↑で定義します。
a_1 = 3
b_0 = 1
です。
明らかに、
(3 - Sqrt[5])^n = a_n - b_n * Sqrt[5]
が成り立ちます。
(3 + Sqrt[5])^n + (3 - Sqrt[5])^n = 2*a_n
が成り立ちます。
5 < 3^2 より、 Sqrt[5] < 3
∴ 0 < 3 - Sqrt[5]
2 = Sqrt[4] < Sqrt[5]
∴ 3 - Sqrt[5] < 1
∴ 0 < 3 - Sqrt[5] < 1
∴ 0 < (3 - Sqrt[5])^n < 1
∴ 0 < 2*a_n - (3 + Sqrt[5])^n < 1
∴ 2*a_n - 1 < (3 + Sqrt[5])^n < 2*a_n
∴ (3 + Sqrt[5])^n の整数部分は 2*a_n - 1 である。
以上より、 a_n が計算できれば、 (3 + Sqrt[5])^n の整数部分を 1000 で割った余りは、
2*a_n - 1 mod 1000
で求まる。
|