« Project Euler - Problem 26 | トップページ | 銀河英雄伝説 »

2009年7月 8日 (水)

Project Euler - Problem 27

問題はこちらをご覧ください。


総当たりで a と b を調べてもいいのですが、ちょっと考えると a と b の探索範囲をかなり絞り込めます。

以前 Scheme で解いた時の考察をここにも書きましたが、あの後さらに思いついたことがあったので、改めて考察をしていきたいと思います。


自分なりの考察を書いていく前に、まずは総当たりでどのくらい時間がかかるか試してみましょう。

require 'math_tool' max = [1, 41, 40] # max = [a, b, n], n : n² + an + b が合成数となる最小の数 -999.upto(999) do |a| -999.upto(999) do |b| n = 0 n = n + 1 while (n * n + a * n + b).prime? max = [a, b, n] if n > max[2] end end puts(max[0] * max[1])
real 0m5.732s user 0m5.580s sys 0m0.036s

と、いうことで Ruby 1.9 で約 5.7 秒かかりました。


では、a と b の探索範囲について考えてみましょう。

なお、ここから先は

v = n² + an + b … (1)

として考えていきます。


まずは b の探索範囲から考えてみます。

n = 0 の時、(1) の式は v = b となります。この時 v が素数となるためには、当然 b も素数でなければなりません。したがって b は 1000 以下の素数となります。

さらに、b が偶数の場合、n が偶数の時には v も偶数となるため、n は 2 以上の値を取ることができません。そこで b = 2 の場合は初めから考えなくても良さそうです。

まとめると、b は 1000 未満の奇素数ということになります。

いきなり b の探索範囲が大幅に減りました。(1998個 → 167個)


次に a について考えてみます。

(1) の式は v = n(n + a) + b と変形できます。

n と n + a がともに奇数の場合、b が奇素数のため v は偶数となり、v が素数となるのは v = 2 の場合のみになります。

したがって、より多くの素数を探すためには、n と n + a のどちらかは偶数である必要があります。ところが a が偶数の場合、n が奇数の時 n + a も奇数となってしまうため、この条件に反してしまいます。

以上のことから、a は奇数でなければなりません。

ということで a の探索範囲はここで半分になりました。


さらに、例題として n = 39 が成立する式が示されているので、n > 39 を満たす式を見つけないと、問題自体が成立しません。

そこで (1) の式に n = 40 を代入してみると、v = 40² + 40a + b となります。

v は素数ですので v > 0 とすることができます。したがって、40² + 40a + b > 0 となります。この式を変形すると、a > -40 - b/40 となります。

また、n = b の時、v = b² + ab + b = b(b + a + 1) となり、v は合成数となってしまいます。したがって n は b 以上になることはできません。

このことから、b を大きい方から調べていった場合、b がその時点での n の最大値より小さくなった場合、そこで探索を中止しても良いと考えられます。

以上のことを踏まえて書いたコードは次のようになりました。

require 'math_tool' max = [1, 41, 40] # max = [a, b, n], n : n² + an + b が合成数となる最小の数 prime_list(1000).reverse_each do |b| break if b < max[2] a_min = -40 - b.div(40) (a_min ... 1000).each do |a| next if a.even? n = 1 n = n + 1 while (n * n + a * n + b).prime? max = [a, b, n] if n > max[2] end end print("a * b = #{max[0] * max[1]}\n")

このコードを実行すると、

real 0m0.567s user 0m0.508s sys 0m0.012s

ということで、約 0.56 秒で答えが出ました。総当たりで調べたときの 1/10 の時間で答えが出ました。


コードを書く前にいろいろ考えて、アルゴリズムを吟味したり探索範囲を絞っていって、実際に実効速度が速くなるととてもうれしいものです。

一度解いた問題も、「もっといい解法はないか?」と考え直すことが多いので、ひとつの問題を解くのに結構時間がかかっています。

まあ、いろいろ考えるのが好きなので、Project Euler はじっくりと取り組んでいこうと思っていますけど……。

« Project Euler - Problem 26 | トップページ | 銀河英雄伝説 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/45576523

この記事へのトラックバック一覧です: Project Euler - Problem 27:

« Project Euler - Problem 26 | トップページ | 銀河英雄伝説 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ