Edited at

等間隔に並ぶ素数を探そう


等間隔に並ぶ素数を探そう

どうもこんにちは。2018年10月入社の@wonda-tea-coffeeです。

本当はReactNativeで何か作る予定だったのですが、時間が足りず数学ネタに走ってしまいました。

というわけで(?)等間隔に並ぶ素数のお話を始めます。


等間隔に並ぶ素数とは?

素数とは、1と自分自身でしか割り切れない正の整数です。

また、等間隔に並ぶ、というのは等差数列を意味しています。

等差数列についても復習しましょう。例えば、

$$7, 13, 19$$

は初項が7、項差が6の素数のみから成る等差数列です。


今回のモチベーション

可能な限り長い等間隔に並ぶ素数を見つけたい。


探してみた


実装方針


  • 事前にエラトステネスの篩で指定範囲内の素数を洗い出す

  • 初項をずらしつつ、項差を30ずつ増やしていく

     探索イメージ)

     7は素数!

      項差30: 7, 37, 67, 97, 127, 157, 187(←素数じゃないので探索終わり!)

      項差60: 7, 67, 127, 187, 247(←素数じゃないので探索終わり!)

     ...

     9は素数じゃない!

     11は素数

      項差30: 11, 41, 71, 101, 131, 161(←素数じゃないので探索終わり!)

      項差60: 11, 71, 131, 191, 221(←素数じゃないので探索終わり!)


  • 目的の長さの数列が見つかったらDone!


コード@Java


import java.util.*;

public class Solve {

public static void main(String[] args) {
long s = System.currentTimeMillis();

final int LIM = 100000000;
boolean[] isPrime = sieve(LIM);

int target_length = 15;

// 探索開始位置のループ
main: for (int p = 7; p < LIM; p += 2) {
// 項差のループ
final int tl_minus_1 = target_length - 1;
for (int d = 30; p + d * tl_minus_1 < LIM; d += 30) {
int length = 0;
for (int m = p; m < LIM && isPrime[m]; m += d)
length++;

if (length >= target_length) {
System.out.print("長さ" + length + ": ");
disp_sequence(p, d, length);
break main;
}
}
}

long e = System.currentTimeMillis();
System.out.println("time: " + (e - s) + "ms");
}

// 初項、項差、長さを元に数列を表示
static void disp_sequence(int a, int d, int length) {
System.out.print(a);
for (int i = 1; i < length; i++)
System.out.print(", " + (a + d * i));
System.out.println();
}

// エラトステネスの篩を用いて与えられた数未満の素数を求める
static boolean[] sieve(int n) {
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);

// 0と1は素数でないため除外
isPrime[0] = isPrime[1] = false;

// 2より大きな偶数は素数でないため除外
for (int i = 4; i < n; i += 2)
isPrime[i] = false;

// 1より大きな奇数同士の積で表せるものは素数でないため除外
for (int i = 3; i * i <= n; i += 2) {
for (int j = i; i * j < n; j += 2)
isPrime[i * j] = false;
}

return isPrime;
}

}


今回見つけた等間隔に並ぶ素数たち

長さ3

$$3, 5, 7$$

長さ4

$$7, 19, 31, 43$$

長さ5

$$5, 11, 17, 23, 29$$

長さ6

$$7, 37, 67, 97, 127, 157$$

長さ7

$$7, 157, 307, 457, 607, 757, 907$$

長さ8

$$11, 1210241, 2420471, 3630701, 4840931, 6051161, 7261391, 8471621$$

長さ9

$$17, 6947, 13877, 20807, 27737, 34667, 41597, 48527, 55457$$

長さ10

$$37, 2040607, 4081177, 6121747, 8162317, 10202887, 12243457, 14284027, 16324597, 18365167$$

楽しいですね。


考えたこと・試したこと


  • 項差は3の倍数でなければならない

     →項差が3の倍数でない場合、数列の長さは2より長くなり得ない。

      ただし、数列に3を含まないものとする(これは読者への練習問題とする)。

  • 項差は10の倍数でなければならない

     →項差が10の倍数でない場合、数列の長さは5より長くなり得ない(こちらも読者への練習問題とする)

  • 求めた素数をHashSetに格納すればmainのループ先頭で素数判定をしなくて良い!と思いきやかえって遅くなった

     →containsが響いたかな・・・?


残る課題

・項差を30の倍数にしたとはいえ何の捻りもない全探索なのでLIMを増やすと極端に遅くなる

・ メモリ食い過ぎ


もっと長く

現在人類が見つけている等間隔に並ぶ素数の長さは26です。

では長さ27, 28, 29, ...の等間隔に並ぶ素数は存在するのでしょうか。

2004年、その問いにBen GreenとTerence Taoは解答を出しました。

彼らによれば、

素数の列は任意の長さの等差数列を含んでいる

そうなのです。

長さ100でも、1000でも、10000でも、存在すると言っているのです!

コンピュータの力を持ってしてもたったの長さ26の等間隔に並ぶ素数しか見つけられないにも関わらず!

数学ってすごいですよね・・・


本当に?

こちらのブログでGreen-Taoの定理の証明の日本語での(!)解説が見られます。

http://integers.hatenablog.com/archive/category/%E7%AD%89%E9%96%93%E9%9A%94%E3%81%AB%E4%B8%A6%E3%81%B6%E7%B4%A0%E6%95%B0%E3%82%92%E8%BF%BD%E3%81%84%E6%B1%82%E3%82%81%E3%81%A6

大学2年次程度の数学の知識があれば十分に理解できるそうです。


終わりに

いかがでしたでしょうか。

これを機に数学に少しでも興味を持っていただければ幸いです。

また、業務中にこんな趣味全開の記事が書けてとても満足しています。

明日は@yizknnさんで、

「RubyでRettyからランチ候補をオススメしてくれるSlackBotを作りました」

どうぞお楽しみに〜