Y箱

最近、Herokuでのアプリ作りで苦闘していたり、仕事が忙しかったりして、更新してなかったけど、久しぶりにPEを解いた。


数を素数で分割する問題です。







普通に組み合わせで解こうとするとできないのは目に見えている。
前の問題で、数を自然数で分割する問題は解いたので、これを利用できないかなと考えた。
で、そのときの漸化式はこれですが、

• p(k, n) = 0 if k  > n

• p(k, n) = 1 if k = n

• p(k, n) = p(k+1, n) + p(k, n − k) otherwise.

これ、結局、問題を分割していくわけで、そのとき、キーになるのが k です。 ここでは k を1から順に1ずつ増やしながら調べていくわけですが、数えられるのは、k と n が同じ値になったときであって、それを1通りと数えているわけです。

だから、k を素数に限定してしまえば素数で分割したものが得られるわけ。

うーん。今一つ説明がうまくできない。まあ、こういう式を作りました。

• p(k, n) = 0 if k  > n

• p(k, n) = 1 if k = n

• p(k, n) = p(kの次の素数, n) + p(k, n − k) otherwise.

これだけ。



・ next-prime
 その名の通り、xの次の素数を返します。


・ partition-num-prime
 上の漸化式を表現したもの。 76の (inc k) を (next-prime k) に変えただけ。


・ pe76
 1から順に計算していって、n以下のものを捨てて、最初の1つを取ります。