プロジェクトオイラー27、29問目

29問目は「How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?」というもの。

(println 
 (count
  (distinct
   (for [a (range 2 101) b (range 2 101)]
     (Math/pow a b)))))

forマクロの使い方わかった。シーケンスを作るのね。多重ループの抽象化も簡単。distinctをuniqと名付けなかったのか。

27問目は、絶対値が1000未満のa、bについて「n^2 + an + b」という式の値がn=0,1,2,……について素数となるとき、最大の連続した素数列が出てくるa、bの組み合わせを求めよというもので、「n^2 - 79n + 1601」とか、なんとnが0から79まで80個も素数が連続するという、ちょっと驚くような式。

(defn make-func [a b]
  (fn [n] (+ (* n n) (* a n) b)))

(defn prime? [n]
  (cond
   (> 2 n) false
   (== 2 n) true
   (even? n) false
   (not-any? zero? (map #(rem n %) (range 3 (inc (Math/sqrt n))))) true
   :else false))

(def memo-prime? (memoize prime?))

(defn prime-seq-length [a b]
  (count
   (take-while memo-prime?
	      (map (make-func a b) (iterate inc 0)))))

(defn find-max [seq max]
  (let [s (first seq)]
    (if (zero? (count seq))
      max
      (recur (rest seq)
	     (if (> (first s) (first max))
		    s max)))))

(defn search-range [r res]
  (find-max
   (for [a r b (range 1000)]
     [(prime-seq-length a b) a b]) [0 0 0]))

(println
 (find-max
  (map #(search-range (range % (+ % 30)) [])
       (range -999 1000 30)) [0 0 0]))

Out of Memoryで落ちたので、細かく部分に分けて最大のところを求めているのと、さすがに素朴な素数判定のところはメモ化しようというので、無駄に行数が多い。find-maxも、もう少しいいやりかたがあるような気がする。

こういうコードを書くだけなら、RubyもClojureも大して変わらない気がするんだけど、何かRubyのスゴミみたいなものを改めて感じる。Rubyはよくやる処理について実装やシンタックス、メソッド名が本当によく考えられている感じがする。一方、ClojureはJVM資産の活用と並行処理の容易な記述がウリってことかしら。それはそれで非常に大きいような。あと、なんといっても副作用なしのスタイルを強要されて、そうか、関数ってこう書くのがいいんだと気付かされるようなところがある。