Project Euler で紹介されている問題27を解いてみました。素数を多く生成する2次多項式を求める問題を紹介します。
Project Euler 問題27（二次式の素数）
オイラーは、次の驚くべき二次式を発見した。
$$n^2 + n + 41$$
この式は、0 から連続する整数の値に対して40個の素数を生成することが分かった。しかし、$n = 40$ の場合、$40^2 + 40 + 41 = 40(40 + 1) + 41$ は$41$ で割り切れる。また$n = 41$の場合も $41^2 + 41 + 41$ は明らかに $41$ で割り切れる。
また、$n^2 -79n + 1601$ という信じられない式も発見された。この式は連続する $0 \leqq n \leqq 79$ に対して、80個の素数を生成する。
次の式を考える。
$$n^2 + an + n,\; |a| < 1000,\; |b| \leqq 1000$$
ここで、$|n|$ は、$n$ の絶対値を表す。
例 $|11| = 11$、$|-4| = 4$
0 から始まる連続した値に対して、生成する素数の数が最大となる二次式の係数 $a$ と$b$ の積を求めよ。
解答例
素数か判定する関数は道具箱から持ってきました。注意としては、素数は、2より大きな自然数であることが前提となっています。これは、素因数分解の一意性を保たつためです。例えば、1 や負の整数を素数に加えると
$$ 5 = 2 \times 3 = 1 \times 2 \times 3 = -2 \times -3 $$
など、同じ数に対して、複数の素因数分解ができてしまいます。これを避けるため、素数は 2 以上の自然数であることを前提としています。
係数 $a$ と $b$ でループして連続する素数の個数を求める素直な実装で問題を解くことができました。以下は、C のプログラム例です。
#include <stdio.h>
int is_prime(int n)
{
int answer = 1;
int i;
if (n == 1) {
answer = 0; /* 1 is not a prime number. */
}
for (i = 2; i * i <= n; ++i) {
if (n % i == 0) {
answer = 0;
break;
}
}
return answer;
}
int main(void)
{
int a, b, n;
int max_a, max_b, max_n;
int number;
max_a = 1;
max_b = 41;
max_n = 40;
for (a = -999; a <= 999; ++a) {
for (b = -1000; b <= 1000; ++b) {
n = 0;
number = n * n + a * n + b;
while ((number > 1)&&(is_prime(number) == 1)) {
++n;
number = n * n + a * n + b;
}
if (n > max_n) {
max_a = a;
max_b = b;
max_n = n;
}
}
}
printf("Problem027: %d\n", max_a * max_b);
printf("Problem027: n^2 + %d*n + %d (%d)\n", max_a, max_b, max_n);
return 0;
}実験
係数の条件を変更して、0 から連続する値に対して、最大個数の素数を生成する二次式を求めました。
| 条件 | 二次式 | 生成する素数の数 |
| $|a|,\,|b| < 50$ | $n^2 -5 n + 47$ | $43\; (n = 0 \dots 42)$ |
| $|a|,\,|b| < 100$ | $n^2 -15n + 97$ | $48\; (n = 0 \dots 47)$ |
| $|a|,\,|b| < 10000$ | $n^2 -79n + 1601$ | $80\; (n = 0 \dots 79)$ |
$|a|,\,|b| < 50$ の場合は、オイラーが発見した式（40個の素数を生成）がでてくると思いましたが、43個の素数を生成する式が見つかりました。一方、問題文でも紹介されている $n^2 -79n + 1601$ は、$|a|,\,|b| < 10000$ と条件を広げても、一番多い素数を生成する式になっていました。
最後に
素数を生成する式を求めることは興味深い問題と考えられていました。二次式という簡単な式で、多くの素数を生成する式を見つけることができました。
引き続き、Project Euler の問題を紹介していきます。
