記事の内容
今回の記事では、数学的にも、プログラミング的にも、とても興味深いテーマを紹介します。
2つの自然数が互いに素である確率、という問題です。
そして、その答えは、
\dfrac{6}{\pi ^{2}}
であるというものです。
自然数が絡む確率の話なのに、なぜか円周率が出てくるのです！！
不思議ですよね。
この記事では、数学的な話とプログラムを使った話で、この問題を解説します。
問題のイメージ
もう少し説明しましょう。
自然数は無限にあります。その中から無作為に一つの自然数を選びます。続けて、重複を許しつつもう一度、自然数を無作為に選びます。
このとき選ばれた2つの自然数が互いに素である確率を考えるのです。
この答えに円周率である $ \pi $ が登場することが不思議に見えます。
くわえて、無限は厄介です。無限があるせいでイメージしづらくなります。
例
具体的に考えてみましょう。
範囲を100までの自然数とします。
この範囲で自然数を一つ選ぶ。さらに、もう一回選ぶ。
5と19が選ばれたとします。このとき、この2つの自然数が互いに素になるかどうかを考えるのです。
5と19なら、互いに素です。
21と63なら、互いに素ではありません。
68と7なら、互いに素です。
このように試行を繰り返せば、そこには確率を考えることができます。
少しはイメージがわいてきたでしょうか？
引用元
この問題は、数学youtuberの鈴木貫太郎さんの動画から引用しています。
おそらく、もともと有名な問題なのではないでしょうか。
いったいどこから円周率が出てくるのか？
もう少し数学的な話に入っていきましょう。
どこから $ \pi$ が出てくるのか？
この謎の答えは、「自然数の平方の逆数の和」のせいです。
あの天才オイラーが解決した問題です。
オイラーは次の数式を導きました。
\dfrac{1}{1^{2}}+\dfrac{1}{2^{2}}+\dfrac{1}{3^{2}}+\dfrac{1}{4^{2}}+\ldots =\dfrac{\pi ^{2}}{6}
この数式を導く過程で、「自然数の平方の逆数の和」を考えるために、三角関数を使って近似しているのです。三角関数を利用しているのならば、円周率である$ \pi$が登場するのも自然です。
詳しい証明は、鈴木貫太郎さんの動画をご覧ください。どのように三角関数を利用しているのか、ぜひチェックを。
そして、2つの自然数が互いに素である確率を求めようとすると、「自然数の平方の逆数の和」が式に現れてくるのです。上記のオイラーの式と繋がります。
プログラム使えば実験できるのでは!!
ここで一つ思いついたことがあります。
確率の話なのだから、実際に繰り返し試してみればいい。
実験すれば、数式の結果を確かめられるはずです。
コンピュータに繰り返し試行させることで、実際に確率を求めてみましょう！
今回はpythonで実装してみました。
ポイントは互いに素であるかどうかの判定です。これは、互いに1以外の公約数を持たなければいいのです。
2つの数を与えると最大公約数を返してくれる関数を考えます。このとき最大公約数が1ならば、互いに素であると判定できます。最大公約数を求めるアルゴリズムといえば、ユークリッドの互除法です。
ユークリッドの互除法では、以下の手順で最大公約数を求めます。
import math # 円周率をつかうため
import random
def gcd(a, b):
"""
2つの整数 a, b の最大公約数 (GCD) をユークリッドの互除法で求める関数
:param a: 整数
:param b: 整数
:return: a と b の最大公約数
"""
while b != 0: # b が 0 になるまで繰り返す
a, b = b, a % b # a を b に、b を a を b で割った余りに更新する
return a # b が 0 になったときの a が最大公約数
s = 0
num = 1
while num <= 10000000:
a = random.randint(1,10000000)
b = random.randint(1,10000000)
if gcd(a,b) == 1: # 最大公約数が1のとき互いに素であると判定
s += 1
num += 1
print(s / num) # 実験値
print(6 / math.pi**2) # 理論値
今回は、1～10000000の中から自然数を選びます。
そして、10000000試行です。
その結果は、次のようになりました。
上が実験で求めた値、下が理論的に求めた値です。
かなり近い値になっていることがわかるとおもいます。この結果には驚きです。数学という理論の強さを目の当たりにした気分です。そして、プログラムをとおしてコンピュータを利用することの面白さも改めて確認できました。
0.607662239233776
0.6079271018540267
皆さんの環境でもぜひ試してみてください。