Y箱

針金を曲げて直角三角形を作るとき、1種類しか作れないものを見つける問題です。

ピタゴラス数の問題ですね。


75個解いたので、Level 3になったよ。年内に100を目標にしてたんだけど、届かなかったな。

この記事は、Clojure Advent Calendar 2011の20日目の記事です。



[[2012/1/6 23:00 再修正]]
最新のswank-clojure (1,3.4)では、windowsのパス名の扱いの問題が解決していました。1.3.4以降のものを使えば、特に何もしないで使えます。



[[2011/12/26 23:00 修正]]

最初の投稿では、結局うまくいかなかったのですが、いろいろ調べたり方法を変えたりしてうまく行きました。


これまで、Project EulerとかCode Jamとかやるときには、ClojureBoxを使ってました。ClojureBoxは、立ちあげるとすぐにREPLが使えて便利なのですが、だいぶ前にメンテナンスが終了していて、1.3になる可能性がありません。
自分で1.3に入れ替えるのもそれほど難しくなさそうですけど、1.2ベースで作っちゃったものもあるし、ソースの管理という意味でも、leiningenを使った環境にするのがいいかなと思ったので、やってみました。

数を構成する数字を階乗したものの和で作る数列の長さを求める問題です。

3 -(3!)> 6 -(6!)> 720 -(7!+2!+0!)> 50402 -...

これをそのままやっては終らないので、別の方法を考えたのですけど、思いつかないし、改善方法は思いついたので、それで実装。
2分ちょいかかります。

これもファレイ数列の問題です。

数えるだけなので、他にいい方法もありそうですが、70の方法で正面から解いてます。

ところが、初めに作ったものは再帰で実装して作ったデータを全部持っていたため。OutOfMemoryになってしまった
で、今ちょうど読んでいる、Joy of Clojureで、遅延評価のクイックソートのことが出ていたので、それを使ったらできた。
ついでにJoCに出ていた、名前付き引数を使ってデータ定義をしなくてもいいようにしてみたけれど、あまりよくないかな。

これもファレイ数列の問題です。

なんか、もうちょっといい方法が見つかりそうだんだけれども断念。
まあ、1分弱で解けたからいいということにしよう。




ファレイ数列の個数は、






※wikipediaの画像を勝手に拝借してみた。

と表わせるとのとのこと。 ここにでてくるφ(m)は前に出てきた、オイラーのトーシェント関数。

このまま計算すると、1から1000000までの数を全部素因数分解する必要があって、ちょっと大変なんで、最初は20分近くかかってしまった。
でも、素因数分解の関数(factors)を前のやつからちょっと工夫してやったら、1分を切った。
factorsはもうちょっと高速化できるかもしれない。

百万までの素数を作るのに、5秒くらいかるので、それを入れたら1分を切れないねぇ。





- phi-n
 φ(n)を求める関数。





このとおり。
こういうふうに書けるところがClojure(ｌｉｓｐ）が好きな理由だね。


- pe-72
  ファレイ数列の式の通りの計算。
  でも、公式の場合、0と1を含んだ個数で、PEの問題は両端を含まないので、
  公式の結果から2を引いたものが答え。  ここちょっとはまった。

ファレイ数列の問題です。

Wikipediaの解説を見たら、解きかたは一瞬でわかります。





この数列でa/bとc/dが隣りあっている場合、その間に新しい分数が加わるとすると、それは2数の中間数 (a+c)/(b+d) であるとのこと。

ということは、問題の場合、2/5と3/8 について、
 - 中間数Mを求める。
 - 中間数Mの分母が1000000を超えたら、1つまえのものが答
 - そうでなければ、Mと3/8について同様のことを続ける。

この通りの実装でございます。

これもトーシェント関数の問題です。

普通に考えたら解けないのが分っているので、ちょっと考えます。





今回は、n/φ(n)を小さくするので、問題69で考えたことからすると、素因数の種類は少ないほうがいいということになります。
素因数を1つにするには、nは素数でなくてはならないのですが、nが素数のときのφ(n)は、n-1なので、これがpermutationになることはないでしょう。

ということで、素因数を2つとしてみます。少なくとも問題にある87109の素因数は2つなので、最悪、これが答になります。

さて、素因数が2つということは、

n=p1*p2

ということになります。 また、そのときのトーシェント関数の値は、

φ(n) = φ(p1)*φ(p2) = (p1-1)*(p2-1)

なので、掛けたときに10^7未満になる素数の組を作って、φ(n)とnがpermutationになるかどうか確認します。

20秒弱で解けましたけど、終了条件が分ればもっと速く解けるんじゃないかと思うんだけど、思いつかない。