Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
オイラーは以下の二次式を考案している:
n^2 + n + 41
この式は, $n$ を$0$から$39$までの連続する整数としたときに$40$個の素数を生成する. しかし, $n = 40$ のとき $402 + 40 + 41 = 40(40 + 1) + 41$ となり$41$で割り切れる. また, $n = 41$ のときは $412 + 41 + 41$ であり明らかに41で割り切れる.
計算機を用いて, 二次式 $n^2 - 79n + 1601$ という式が発見できた. これは $n = 0$ から $79$ の連続する整数で$80$個の素数を生成する. 係数の積は, $-79 × 1601$ で $-126479$である.
さて, $|a| < 1000, |b| ≤ 1000$ として以下の二次式を考える (ここで $|a|$ は絶対値): 例えば $|11| = 11,|-4| = 4$である.
n^2 + an + b
$n = 0$ から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数 $a, b$ の積を答えよ.
アプローチ
0.$f(n)=n^2+an+b$とおく。
1.$f(0)=b$である為、$b$は素数である。ゆえに$2≦b$
2.$m$を任意の自然数とすると、$f(2m)=4m^2+2am+b$
もし$b$が偶数$(=2)$であるならば、$f(2m)$が偶数になってしまう為、
$b$≠偶数すなわち、$b$=奇数である。
3.$f(2m-1)=(2m-1)^2+a(2m-1)+b$
$a$を偶数と仮定すると、$f(2m-1)$=奇数+偶数+奇数=偶数(=合成数)となってしまう。
よって、$a$は奇数である。
※上記は特に必要ではないが、処理時間を減らす為に考慮した。
解答
3秒ほどで実行できます。
seq 3 1000 |
factor |
awk 'NF==2' |
awk '{for(i=-499;i<=500;i++){v=2*i-1;if(2<=1+v+$2){print v,$2}}}' |
awk '{for(i=0;i<=100;i++){v=i^2+$1*i+$2;if(v<2){break};for(j=2;j<=int(sqrt(v))+1;j++){if(v%j==0){next}};print i,v,$1,$2}}' |
uniq -f2 -c |
sort -n |
tail -1 |
awk '{print $4*$5}'
-59231
真ん中の長いawkで素数じゃなくなったらやめる、という処理をやっている為実行速度が格段に速くなりました！！
やっぱりループは途中でやめるのが非常に大切だと感じました。
参考にさせて頂いたサイト様
Project Euler 27 _ 二次式素数 - PEをMathematicaで
xargsコマンドで覚えておきたい使い方・組み合わせ7個(+1個) _ 俺的備忘録 〜なんかいろいろ〜