R-99 数学 - Prolog-99 Ruby版 日本語訳

R-99: 99 の Ruby の問題 - 2. 数学

• 訳注1:問題番号の後のアスタリスクはPrologで解くときの難易度の目安。

数学問題

2.01 (**) 指定された整数が素数であるかどうかを確認せよ

例)
is_prime(7) => true

2.02 (**) 与えられた正の整数の素因数を決定し、昇順に素因数を含む1次元配列を作成せよ

例)
prime_factors(315) => [3,3,5,7]

2.03 (**) 与えられた正の整数の素因数を決定せよ

素因数とその多重度を含むリストを作成します。

例)
prime_factors_mult(315) => [[3,2],[5,1],[7,1]]

ヒント: P1.10 の解答を参考にすることができる。

2.04 (*) 素数の配列を取得せよ。その下限と上限によって整数の範囲を与えると、 その範囲内のすべての素数のリストを表示するようにせよ

例)
get_prime(1,10) => [1,3,5,7,9]

2.05 (**) ゴールドバッハ予想: 2より大きいすべての正の偶数は2つの素数の和である

例)
28 = 5 + 23

これは、一般的なケースでは正しいことが証明されていなかった数論の中で最も有名な事実の一つです。 これは、数値的に(私たちはRubyで行うことができるよりもはるかに大きい)、非常に大きな数まで確認されています。 指定された偶数の整数に合計2つの素数を見つけるために、引数を入力します。

例)
goldbach(28) => [5,23]

2.06 (**) ゴールドバッハ数の配列

その下限と上限によって整数の範囲を与える。このとき、すべての偶数と そのゴールドバッハ数のリストを表示せよ。

例)
goldbach_list(9,20).
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17

偶数の2つの素数の和として書かれている場合、ほとんどのケースでは、そのうちの一つは非常に小さい。 ごくまれに、両方の素数が 50 よりも大きいことがある。範囲 2〜3000 で、このようなケースがあることを 調べよ。

例: 最大 50 個出力する)
goldbach_list(1,2000,50).
992 = 73 + 919
1382 = 61 + 1321
1856 = 67 + 1789
1928 = 61 + 1867

2.07 (**) 2つの正の整数の最大公約数を表示せよ

ユークリッドのアルゴリズムを使用せよ。

訳注: ユークリッドのアルゴリズム(ユークリッドの互除法)とは、 「2つの自然数 a, b (a≥b) について、r = a % bとすると、a と b との最大公約数は b と r との最大公約数に等しいことから、r2 = b % r、r3 = r % r2...と続けて 剰余が 0 になったとき(r[n]==0)のr[n-1]が最大公約数となる。」という手法。

例)
gcd(36,63) => 9

2.08 (*) 2つの正の整数が互いに素かどうかを判定せよ

二つの数字の最大公約数が 1 のとき、互いに素であるという。

例)
coprime(35,64) => true

2.09 (**) オイラーのトーシェント関数φ(m)を計算せよ

オイラーのトーシェント関数φとは、正の整数 (1≤r<m) が互いに素であると定義される。

例)
m = 10 のとき、r = 1,3,7,9 となる。
phi(m) => 4

totient_phi(10) => 4

参考: 特殊な場合に注意すること。( phi(1) == 1 )

mが素数であれば φ(m) の値があるかを調べる。 オイラーのトーシェント関数は、最も広く使用されている公開鍵暗号方式(RSA)において 重要な役割を果たしている。 この演習では、この関数を計算するために、最も原始的な方法を使用する必要がある。 この問を解くために 2.10 で使用しなければならない、よりスマートな方法がある。

2.10 (**) オイラーのトーシェント関数φ(m)を計算せよ　その2

オイラーのトーシェント関数の定義については、2.09 を参照せよ。 数 m の素因数のリストは、2.03 関数 φ(m) の形で知られている場合、 次のように効率的に計算することができる。 [[p1,m1],[2,m2],[p3,m3],...] 指定された数 m の素因数(およびその多重)の配列です。次に、&phi(m) は、 以下を用いて計算することができる。

関数:

phi(m) = (p1 - 1) * p1**(m1 - 1) * (2 - 1) * 2**(m2 - 1) * (p3 - 1) * p3**(m3 - 1) * ...

訳注: 関数 phi(m) を上記の式を使うように改修せよ。

参考: 「a**b」とは、「a の b 乗」を表す。

2.11 (*) オイラーのトーシェント関数を計算する2つのメソッドを比較せよ

アルゴリズムを比較するために、2.09 と 2.10 の解答を使用せよ。 効率の尺度として関数の実行時間を取る。例として phi(10090) を計算させ、 それぞれの回答の実行時間を確認せよ。