ウラムの螺旋が面白い件
自然数を渦巻き状に並べ、素数である部分を黒く塗りつぶす。この図をウラムの螺旋と言う。
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) から f(x) までの各値のうち、得られた値が素数である確率が高いことがわかる。f(1) から f(x) までの各値のうちの素数の割合を出す関数を g(x) と置くと、f1 から f4 は以下のようになる。
なんと関数から出力される値のうち、ほぼ半分が素数ではないか! f(x) = x の場合はでは x=1000 で 0.168, 10000で 0.123 なので上記関数は素数の割合がかなり高いと言える。(参考:素数定理)
関数によって当然 g(f(x)) が変わるわけだが、f(x) の値の大きさや増加率によっても関数の「使え具合」が大きく変わるはずだ。小さな素数より大きな素数を出力したほうが評価が高く、値の増加率が高ければ高いほど(次の素数が大きくなることを期待できるので)関数の評価も高くなるべきだ。では、評価関数はどのようにすべきか?
まとめると、評価関数に望むべき事は以下の3つだ。
- 素数を出力する割合が高ければ高いほど評価が高い
- が大きいほど評価が高い
- が大きいほど評価が高い
これを十分満たす関数 p(x) は素数探索や暗号の処理に使える可能性が高い。また、(関数の計算量がO(1)と仮定すると)素数判定にも使えるだろう。ただし厳密に関数を評価すると計算量が無限になってしまうので、ある程度のところで打ち切らなければならない。
具体的な評価関数は後で考えるとして、100万までのウラムの螺旋を貼っておこう。
さらに、独立した素数(どの素数とも隣接していない素数)を消去し、規則性を強調した版のウラムの螺旋画像。
明らかに直線が見えるなぁ。ウラムの螺旋はまだまだ楽しませてくれそうだ。続きはまた今度。
- 作者: 芹沢正三
- 出版社/メーカー: 講談社
- 発売日: 2013/11/08
- メディア: Kindle版
- この商品を含むブログを見る