#mitori_clj Project Euler Problem 12

problem_12.clj

(ns tnoda.projecteuler.problem-12
  (:use [org.clojars.tnoda.math.prime :only [sieve* prime-factors *prime-array*]]
        clojure.test))

(defn- solver*
  "Returns the value of the first triangle number to have over x divisors."
  [x]
  (binding [*prime-array* (sieve*)]
    (let [triangle-numbers (reductions + (range))
          nd (fn number-of-divisors
               [x]
               (->> (prime-factors x)
                    vals
                    (map inc)
                    (apply *)))]
      (->> triangle-numbers
           (drop-while #(>= x (nd %)))
           first))))

(def solver (partial solver* 500))

(is (= 28 (solver* 5)))

• http://www.zusaar.com/event/455057
• http://projecteuler.net/problem=12

解説

約数の数が 500 を越える最小の三角数を求めよという問題です．三角数の約数の数を小さい順に調べていき，500 を越えた最初の数を返すという力技で解きます．

Wikipedia の約数のページ によると，ある自然数 n の約数の数は，n を素因数分解できれば求められるようです．素因数分解は面倒なのですが，org.clojars.tnoda/math.prime ライブラリに prime-factors という関数があるので，それを使います．この prime-factors 関数は，素因数分解した結果 Πp^a を {p a, ...} の map で返します．たとえば，252 を素因数分解した結果は，

user> (prime-factors 252)
{2 2, 3 2, 7 1}

と得られます．

org.clojars.tnoda/math.prime

Leiningen の project.clj の :dependencies に

[org.clojars.tnoda/math.prime "0.1.0"]

を追加して使います．

(binding [*prime-array* (sieve*)] ...)

prime-factors 関数は高速に素因数分解するために素数列を利用するのですが，デフォルトの動作ではこの素数列を求めるのにエラトステネスの篩を実行します．このため，prime-factors 関数を複数回走らせる場合，その回数だけエラトステネスの篩を実行することになります．素数列は一回求めておけば使い回しが効くので，これはかなりの無駄です．そこで，prime-factors 関数は *prime-array* 変数に素数列があれば，自前で篩わずにその素数列を利用するようになっています．名前から類推できるように，*prime-array* には素数の配列を格納します．

sieve*

org.clojars.tnoda/math.prime はエラトステネスの篩を実行する関数として sieve を用意しています．sieve は高速で，10^7 未満のすべての素数を調べるのに，手元の環境では 400ms かかりません．

user> (time (binding [*sieve-size* 10000000] (sieve)))
"Elapsed time: 358.439 msecs"
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 ...)

sieve* は sieve の配列版で，sieve が seq を返すのに対して sieve* は配列を返します．どちらも実行速度に差はありません．

Disclaimer

org.clojars.tnoda/math.prime は Project Euler 用に私が作ったライブラリです．

このライブラリに関するコメントもお待ちしています．たとえば，

• 変数 (*prime-array*) の使い方は適切か？
  • 素数列を引数で渡すほうがよいかもしれない．
  • with-primes のようなマクロを用意したほうがよいかもしれない．
• 名前のつけ方は適切か？
  • * 接尾辞の使い方．

などなど．不具合がありましたら issues か pull requests を投げてもらえると嬉しいです．

素数列と素因数分解については, 別途ということで. (tnoda/math.prime 👍)

• 「約数の個数は素因数分解した指数にそれぞれ 1を足したものの総積である.」ということを利用しないとかなりはまりそうですね.
  「問題にとりかかる場合は, 部分問題についての既知の解法についてよく検索しましょう」ということでしょうか.
• 三角数の列が (reductions + (range)) で良いというのは目から鱗です. 気がつきませんでした.
  reductions 万歳.
• number-of-divisors のところ. 再帰で使う訳ではなくても, 無名関数に明確な機能があるなら名前として書いておくというのは, コードの可読性が上がって良いかもしれません.
  今度まねします.

連投失礼.

nd (fn number-of-divisors   ; 約数の個数は
     [x]
     (->> (prime-factors x) ; 素因数分解した
       vals                 ; 指数に
       (map inc)            ; それぞれ 1 を足したものの
       (apply *)))          ; 総積である.

->> マクロは日本人向きかもしれませんね.

reductions 万歳.

reductions 万歳．reductions って reduce とまぎらわしいし，使いどころがよくわからなかったのですが，今回の (reductions + (range)) でコツをつかめるような気がします．

->> マクロは日本人向きかもしれませんね.

その発想は無かったですが，言われてみればなるほどです．自然と日本語で読み下せますね．

「問題にとりかかる場合は, 部分問題についての既知の解法についてよく検索しましょう」ということでしょうか.

Project Euler始めてからWikipediaのお世話になることが多くなって、おかげで整数論？関係の知識が増えました。で、感謝の印に、毎年Wikipediaに寄付(ちょっとですが)するようになりました。

org.clojars.tnoda/math.prime

拝見しました。 いいですね。

変数 (prime-array) の使い方は適切か？

dynamic変数にしてあるのは、なぜとは言えませんが、変な感じがします。

直感的には、素数列というのは、πなど と同様の定数としてだれかが提供してくれるべきものだと思いますので、Math/Primes みたいに使えるのがいいと思います。 ですが、実際のことを考えると、動的に生成すにしても、いらなくなったらメモリの無駄なので、消えてほしいわけです。

ということで、 僕は、素数列をストーリームとしてしまって、 with-openが使えるようにするの がいいと思います。

でも、with-openするたびに素数列を作ることになるので、非効率だよとかいう場面も多いと思いますので、素数の使われかたによるという結論ではないでしょうか。

実運用だったら、DBに突っこんでおくという、元も子もない解決策になりそうですね。

駄文失礼。

直感的には、素数列というのは、πなど と同様の定数としてだれかが提供してくれるべきものだと思いますので、Math/Primes みたいに使えるのがいいと思います。 [...]

同じ意見です．理想的には言語組込みの素数列シーケンスがあってもいいかもしれないのですが，それをどのようにして提供するのかというのが，使われかたにもよるので，一つに決めきれないのが難しいところです．

ということで、 僕は、素数列をストーリームとしてしまって、 with-openが使えるようにするの がいいと思います。

with-primes というマクロを作って，その中では，最初の一回だけ sieve して，その素数列を使い回すようにするというのを考えているのですが，どうでしょうか．（with-primes マクロの実体は (binding [*prime-array* (sieve*)] ...) なんですけどね．）

私も解いてみて、約数の個数を求めるのを (count (filter #(zero? (mod n %)) (range 1 (inc n)))) のnaive実装でいつまでたっても実行が終わらずに、@kohyama さんの指摘どおりしばらくハマっていました。
少しかんがえて素因数分解に落ち着いて、最終的には @tnoda さんのコードとほぼ同じになりました。

tnoda/math/prime.clj 書き方や語彙が参考になります。
別の問題で作っていた素因数分解結果をシーケンスにする関数を、この問題向けにmapにするように書きなおしていたのですが、実はfrequenciesでいいのですね。覚えます。

reductions、こういう関数ないかなあと少し探してはみたのですが、見つけられませんでした。
語彙がもっとほしいです。もしくはもっと上手く探せるようになりたいです。でも、こうやってちょっとずつ覚えていくの楽しいですね。