黄昏より暗きもの、血の流れより赤きもの

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

10001番目の素数はなあに?数学関連の問題解答サイト「Project Euler」の Ploblem 7を解いてみた

2月のこの時期と言えば受験シーズン。高校受験では公立高校の入試、大学入試は国立大学前期試験の季節ですね。調べてみた所東京大学では2月25日〜2月26日に行なわれる模様です。

自分は東大の赤門なんてとてもとてもでした。そんな自分の大学受験時代と言えば好きな数学の問題を色々やっていたものです。趣味が高じて今こうしてブログの記事にしている訳ですね。さて、今日は日本の受験の世界で言うの整数問題(整数論)を、コンピューターや手計算で解く事が目的のWebサイト「Project Euler」の問題を紹介します。とその前に今回の記事は趣味で数学をやっている方向けに、色々な情報を盛り込んでみました。是非とも見てみて下さい。

第一章:Project Eulerに飾られているレオンハルトオイラーについて

Project Eulerのサイトに入ると有名な数学者のレオンハルトオイラーの写真が飾られています。まずは彼の功績について語ります。

URL:https://projecteuler.net/about


f:id:program_study:20150207211942p:plain

数学系の方なら、彼と言えば微分積分e^{i\theta}=cos\theta+isin\theta(オイラーの公式)
*1を思い浮かべる方も多いでしょう。そしてこれを導入する事で今まで解き明かせなかった事が解き明かせるようなりました。オイラーの公式は、音楽制作で「何Hzの音の成分がどれだけの強さか?」と言うのをコンピューターの画面上するのに必要なフーリエ変換*2にも持ちいられています。

彼の功績はこれだけにとどまらず、中学校の範囲(初等幾何)では「三角形の外心を0・重心をG・垂心をHとするとき、O,G,Hは一直線上に並び、OG:GH=1:2となる(オイラー線)*3もこの範囲を深く知る上で重要ですね。もっと一般的な所では、「このような状況の時、一筆書きができる」と一筆書きに関する規則性*4(オイラー閉路)を発見したりしています。

もちろん整数の範囲でも「1 から n までの自然数のうち n と互いに素*5なものの個数を φ(n)(オイラー関数)」と言う物を打ち立て、整数論の発展に寄与したようです。

第2章:素数について知っておいた方が良い事

1:素数と合成数について

素数とは1と自分自身以外で割り切れない整数の事を言います。例えば2,3,5,7は1と自分自身でしか割れないので素数ですね。特に2より大きい偶数は全て2で割り切れるので、偶数の素数は2のみとなりますよね。これに対し合成数とは、N=a×b(1≦a≦b≦N)と2つの整数の積で表せる数の事を言います。例えば15=3×5で表せるので合成数となります。

2:双子素数

素数の中には3と5、11と13と言うように差が2である2組の素数も存在します。こうした素数の事を双子素数と言います。また双子素数は無数に存在するか?と言う事に関しては、未だ解決されておらず未解決問題となっているようです。ご存知の方もいると思いますが、素数は無数に存在します。素数が有限個あると仮定して、矛盾を示す事で証明できます*6。自信のある方は証明してみて下さい。

3:メルセンヌ素数

いきなり話変わるんですがコンピュータと言うのは0と1ですね。こうして0と1で数を表したものを2進数といい、0〜9の10種類で数を表したものを10進数といいます。さて、素数の中にもこの2進数と関係の深いものがあり、2進数に直すとn桁全てが1になる素数、要は2^n-1の型をした素数の事をメルセンヌ素数と言う物があります。例えば、n=2,n=3,n=7の場合を表にしてみました。このとき


n 10進数の値 2進数の値
2 3(=2^2-1) 11
3 7(=2^3-1) 111
7 7(=2^7-1) 1111111

素数を生成する際にコンピューターに繰り返し処理させて発見させる事がよくあります。今回の問題解決にもこうした手法の1つを用います。尚、メルセンヌ素数はGIMPSと言って、プロジェクトの各参加者のコンピューターの処理能力の一部を借りて分散して処理させることで、現在48個のメルセンヌ素数が発見*7されているようです。そんなこんなで雑談はここまでにして、早速10001番目の素数を発見していきましょう。

第3章:「エラトステネスのふるい」を使って問題7(Problem 7)を解く

Project Euler「Ploblems」をクリックすると、問題の一覧が表示されます。解きたい問題をクリックすると解答欄が出て来て、そこに答えを打ち込んで行く流れとなります。今回はPloblem 7の問題と行きます。


問題と意訳

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.What is the 10001st prime number?

自分なりに解釈すると「2,3,5,7,11,13は素数で、6番目の素数は13である。このとき10001番目の素数を求めよ」と言う具合になります。

解き方:エラトステネスのふるいを使う

素数の求め方は様々ありますが、今回使うのはエラトステネスのふるいです。この方法は以下のように100以下の整数の場合、

  1. 1から100の整数のうち、2の倍数の物を全て消す(図の赤)
  2. 1から100の整数のうち、3の倍数の物を全て消す(図の緑)
  3. 1から100の整数のうち、5の倍数の物を全て消す(図の青)
  4. 1から100の整数のうち、7の倍数の物を全て消す(図の紫)


f:id:program_study:20150205221209p:plain

2から小さい素数から順に消して行き、最終的に生き残ったものを素数と断定する方法です。メリットは整数N以下の素数を全て見つける事に強い点です。先ほども言った通り、素数は無数に存在しますので、Nが限りなく大きいと処理が終わらなくなる点に気をつけて使わなくてはなりません。

高校受験や大学受験の整数問題にこんな総当たりなやり方は通用しませんが、如何せん繰り返し処理の得意なコンピューター様には関係ありません。素数の出現には具体的な規則性が発見されていない*8ので、コンピューターで総当たりで探す流れになりそうです。この辺が一般の数学の問題とProject Eulerとは違う所ですね。

尚、エラトステネスのふるいのプログラムに関しては「C言語-エラトステネスの篩:Please Comment on My Code」から借り、少し改良しました。

C言語プログラム

元のプログラムより8行目、9行目、15行目、32行目、33行目にそれぞれ追記や変更を加え、現在の素数が何番目かを見る事ができるように改良しました。

プログラムを実行すると、10001番目の素数104743である事が分かりました。これをフォームに入力したら、214206番目の正解者だったようです。


f:id:program_study:20150205221258p:plain

ネタ切れの為数学ネタを書きました。数学に興味がある人がどれだけ共感してくれたか?雰囲気だけでも味わって帰って下さい!と言うのが正直な所です。流石に難しい事を書き過ぎたので、次回の2月28日(土曜日)ではiPhoneのゲームアプリの紹介を致します。「私もやってるよ!」と言う声をお待ちしています(笑)

*1:オイラーの公式の証明について:オイラーの公式(wikipedia)より。テイラー展開を用いて左辺と右辺の比較を行なうことで証明できる

*2:フーリエ変換(連続)を参照。代表的なアルゴリズムにFast Fourier Transformがある

*3:オイラー線の証明について:初等幾何・座標・三角関数・ベクトルの各手法で証明可能。詳細は:http://mathtrain.jp/euler_lineまで

*4:グラフ理論においてグラフGの全ての辺の次数が偶数のとき、Gはオイラーグラフとなり、一筆書きが可能となる

*5:互いに素:2つの整数a,bがあり、その最大公約数をGCD(a,b)と表すとき、GCD(a,b)=1となるもの

*6:素数が無数にあることの証明[答え]:背理法を使って素数が有限個p_1,p_2,.....,p_nあると仮定する。このときN=p_1*p_2*...*p_n+1を考えるとNはp_1〜p_nのどの整数でも割り切れずNは素数となる。この事は素数が有限個あることと矛盾する。以上より素数は無数に存在する q.e.d

*7:メルセンヌ数:http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E6%95%B0

*8:実はグリーン・タオの定理と言って、「k を任意の自然数とすると k 個の項からなる素数の等差数列が存在する」と素数の規則性に関する定理もあります。詳しくはhttp://www.geocities.jp/ikuro_kotaro/koramu/2251_yx.htm