読者です 読者をやめる 読者になる 読者になる

ウラムの螺旋が面白い件

数学

自然数を渦巻き状に並べ、素数である部分を黒く塗りつぶす。この図をウラムの螺旋と言う。

17 18 19 20 21
16 5 6 7 22
15 4 1 8 23
14 3 2 9 24
13 12 11 10 25

これを一万まで行うと以下の画像が出来上がる。



おお、何やら規則性がぼんやりと浮かび上がるではないか!何やら直線のようなものが見え隠れするので、これらの直線を表す式を出す。




結論から言うと以下の式が算出される。


f_1(x)=4x^2 - 6x + 3 + 40

f_2(x)=4x^2 - 6x + 3 + 106

f_3(x)=4x^2 - 10x + 7 + 40

f_4(x)=4x^2 - 10x + 7 + 106




するとこれらは f(1) から f(x) までの各値のうち、得られた値が素数である確率が高いことがわかる。f(1) から f(x) までの各値のうちの素数の割合を出す関数を g(x) と置くと、f1 から f4 は以下のようになる。

g(f_1(1000)) \approx 0.516

g(f_2(1000)) \approx 0.406

g(f_3(1000)) \approx 0.507

g(f_4(1000)) \approx 0.403

なんと関数から出力される値のうち、ほぼ半分が素数ではないか! f(x) = x の場合はでは x=1000 で 0.168, 10000で 0.123 なので上記関数は素数の割合がかなり高いと言える。(参考:素数定理)
関数によって当然 g(f(x)) が変わるわけだが、f(x) の値の大きさや増加率によっても関数の「使え具合」が大きく変わるはずだ。小さな素数より大きな素数を出力したほうが評価が高く、値の増加率が高ければ高いほど(次の素数が大きくなることを期待できるので)関数の評価も高くなるべきだ。では、評価関数はどのようにすべきか?

まとめると、評価関数に望むべき事は以下の3つだ。

  • 素数を出力する割合が高ければ高いほど評価が高い
  • \frac{f(x)}{x} が大きいほど評価が高い
  • \frac{f(x+1)}{f(x)} が大きいほど評価が高い

これを十分満たす関数 p(x) は素数探索や暗号の処理に使える可能性が高い。また、(関数の計算量がO(1)と仮定すると)素数判定にも使えるだろう。ただし厳密に関数を評価すると計算量が無限になってしまうので、ある程度のところで打ち切らなければならない。

具体的な評価関数は後で考えるとして、100万までのウラムの螺旋を貼っておこう。




さらに、独立した素数(どの素数とも隣接していない素数)を消去し、規則性を強調した版のウラムの螺旋画像。





明らかに直線が見えるなぁ。ウラムの螺旋はまだまだ楽しませてくれそうだ。続きはまた今度。