« 2009年1月 | トップページ | 2009年3月 »

2009年2月

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))))))))))))))

2009年2月22日 (日)

「Scheme の do」 その後

以前このブログで、「Scheme の do の使い方が分かった気がする」と書いたことがありました。

ところが、その後もほとんど "do" を使っていません。

単純な繰り返しの場合 "do" は力を発揮しやすいのですが、自分の書いたコードを見てみると、繰り返しの中身のほとんどは "cond" を使って複数に分岐するものでした。こういった場合に "do" を使おうとすると、無理や無駄が多くなりそうなので、結局 "named let" に頼る日々が続いています。

リスト内包表記

以前から、 Haskell の「リスト内包表記」に憧れていました。Scheme でもあんな風に書けたら……と思っていました。

それでググってみたら、 "SRFI-42" に "Eager Comprehensions" というのがありました。まさに「内包表記」です。 Gauche でも普通に使用できるようです。Haskell との違いは先行的評価であることと、表記する要素の順番。

先行的評価に関しては、自分が使用するときに気をつければいいのであまり気にならないのですが、表記の順序はちょっと気になります。

数学で集合を表現する場合、

A = {x | F(x)}

のように、まず集合の要素の代表を提示してから、要素の条件を示します。 Haskell はまさにその通りの順序なんですが、"SRFI-42" は条件を先に書かなければなりません。これが僕にはしっくりこないんですね。

それで他にもいろいろ探してみたら、なんと、自分の持っている「プログラミング言語 SCHEME」という本のサンプルを集めた章に「集合の構築」という名前で、リスト内包表記を実現する方法が載っていました。

その部分の説明を引用しておきます。

set-of 式は以下の形式となります。

(set-of value exp ...)

exp ... によって設定したバインドによって表現された集合の要素が value となります。それぞれの式 expt ... は以下のいずれかの形式になります。

  1. (x in s) 形式の式は x を集合 s の各要素にバインドします。このバインドは残りの式 exp ... および式 value から参照できます。
  2. (x is e) 形式の式は xe にバインドします。このバインドは残りの式 exp ... および式 value から参照できます。この形式は基本的に (x in (list e)) の省略形です。
  3. その他の形式の式は述語として扱われます。

例えば

(set-of x (x in '(a b c))) ; => (a b c) (set-of x (x in '(1 2 3 4 5)) (even? x)) ; => (2 4) (set-of (cons x y) (x in '(1 2 3)) (y is (* x x))) ; => ((1 . 1) (2 . 4) (3 . 9)) (set-of (cons x y) (x in '(1 2 3)) (y in '(a b))) ; => ((1 . a) (1 . b) (2 . a) (2 . b) (3 . a) (3 . b)) (set-of (list a b) (a in '(1 2 3 4 5)) (b in '(2 4 6 8)) (> (+ a b) 10)) ; => ((3 8) (4 8) (5 6) (5 8))

となります。

この本の著者は、私の使用している "Chez Scheme" の主要開発者ということもあり、今後はこちらを使っていこうと思っています。

「プログラミング言語 SCHEME」の英語版を "Chez Scheme" のホームページで読むことができますので、ソースコードが知りたい方はそちらをご覧ください ("The Scheme Programming Language" の "Section 9.3. A Set Constructor")。

2009年2月14日 (土)

リファクタリング

Scheme ってリファクタリングしたくなっちゃうんですよね。

以前書いたコードでも、ちょっと思いついたこととかあると、結構書き換えて ます。

そのときには、自分の中の「ジレンマ」に揺れることが多いので、ちょっと困っ たこともありますけど…。

ちなみに、このブログに書いたコードも、ちょこちょこ手直ししてます。一回 見た記事でも、次に見たときにはコードが変わってるかもしれませんよ。

« 2009年1月 | トップページ | 2009年3月 »

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

最近のトラックバック

無料ブログはココログ