« 「Scheme の do」 その後 | トップページ | アルゴリズムの重要性 Project Euler --- Problem 36 »

2009年2月26日 (木)

Project Euler --- Problem 27

問題文はこちらを参照してください。


Project Euler はちょっと数学的考察を加えると、探索範囲をかなり絞り込めることがあります。

この問題では、a, b ともに -999 〜 999 の範囲を探索することになっていますが、まともにすべてを計算したら、すごい計算量になってしまいます。私の持っているパソコンでは数時間かかるのではないでしょうか?

そこで、a, b の範囲についてちょっと考察してみます。

v = n² + an + b

とすると、n = 0 の時には v = b となり、v が素数になるためには当然 b も素数でなければなりません。しかも b = 2 の場合、n = 2 の時に v が偶数になってしまうので、結局 b は 1000 以下の奇素数 (167個) になります。いきなり、b の探索範囲が激減しましたね。


次に、a の範囲について考えてみましょう。

v = n(n + a) + b

と変形します。

a が偶数、n が奇数の時、v の値は「奇数×奇数+奇数=偶数」となってしまい、v は素数になりません。従って a は奇数でなければなりません。


ここから先はちょっとずるい考え方ですが……

n² + an + b > 0

を変形すると、

a > -b/n - n

となります。

例題としてあげてあるオイラーの二次式で既に n = 39 まで成功しているので、40 以上の n を探さないと問題自体が成立しません(笑)


まとめると b は 1000 未満の奇素数。a は -b/40 - 40 以上 1000未満の奇数を調べればいいことになります。

(試しにいくつか計算してみたところ、 絶対値が合成数の場合は a の候補から外せそうですが、数学的な根拠をまだ考えつかないので、この条件はまだ採用していません)

(define problem-027 (lambda () (let ([n-max 0] [a-max 0] [b-max 0]) (let loop-b ([b-lst (cdr (prime-list 1000))]) (if [null? b-lst] (printf "a:~d, b:~d, n:~d, a*b:~d~%" a-max b-max n-max (* a-max b-max)) (let* ([b (car b-lst)] [a (- (quotient (- b) 40) 40)]) (let loop-a ([a (if [odd? a] a (+ a 1))]) (if [> a 1000] (loop-b (cdr b-lst)) (let loop-n ([n 0]) (let ([v (+ (* n n) (* a n) b)]) (cond ([and (positive? v) (prime? v)]                (loop-n (+ n 1))) ([> (- n 1) n-max] (set! n-max (- n 1)) (set! a-max a) (set! b-max b) (loop-a (+ a 2))) (else (loop-a (+ a 2))))))))))))))

« 「Scheme の do」 その後 | トップページ | アルゴリズムの重要性 Project Euler --- Problem 36 »

Project Euler」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« 「Scheme の do」 その後 | トップページ | アルゴリズムの重要性 Project Euler --- Problem 36 »

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            
フォト

最近のトラックバック

無料ブログはココログ