針金を曲げて直角三角形を作るとき、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に入れ替えるのもそれほど難しく...
数を構成する数字を階乗したものの和で作る数列の長さを求める問題です。
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分を切れないねぇ。...
ファレイ数列の問題です。Wikipediaの解説を見たら、解きかたは一瞬でわかります。この数列でa/bとc/dが隣りあっている場合、その間に新しい分数が加わるとすると、それは2数の中間数 (a+c)/(b+d) であるとのこと。ということは、問題の場合、2/5と3/8 について、 - 中間数Mを求める。 - 中間数Mの分母が1000000を超えたら、1つまえのものが答 - そうでなければ、Mと3/8について同様のことを続ける。この通りの実装でございます。
This file contains bidirectional Unicode text that may be interpreted...
これもトーシェント関数の問題です。普通に考えたら解けないのが分っているので、ちょっと考えます。今回は、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秒弱で解けましたけど、終了条件が分ればもっと速く解けるんじゃないかと思うんだけど、思いつかない。...
オイラーのトーシェント関数φ(n)の問題です。まずは、普通に解いてみましがやっぱり15分もかかります。大きな数の素因数分解そのものに時間がかかるのが問題です。答が出たので、まあこれでもいいかな...と思っていたのですが、帰りの電車で考えていたら、ひらめきまして、やり直しました。※ 今回、OpenOfficeの数式エディタで数式を作ってみました。nの素因数分解がのようにあらわせるとき、φ(n)は、で得られます。問題の答は、n/φ(n)を求めます。最初のやりかたは、ここで、nを素因数分解して、この式をそのまま計算するものでした。このあと、この式を眺めていて別の方法を思いつきました。n/φ(n)の値はこういう値です。nが消えるところがポイントです。この式の値を大きくするということは、分母を小さくするということです。それには、掛け合わされているかっこの中を小さくすればすればよくて、かっこの中を小さくするには、pを小さくすればいいということがわかります。さらにその数が沢山あればなおいいですね。ということで、求めるnは、小さな素因数を沢山持つものであることになります。とはいっても、同じ素因数をいくら持っていても、pは増えませんので、これは、小さい素数から順に素因数として持つものということになります。ようするに、2、3、5...と、小さいほうから順に1000000を超えないように素数を掛けていくと答が出るということです。ただ、このやりかただと、重複している素因数がみつからないので、実際にもとめる数はこの数の倍数ということになります。...
この記事は、Clojure Advent Calendar 2011の5日目の記事です。
Clojure界隈では、というより他でもWeb系のいろいろが沢山なわけですが、仕事がそっち系でないのでそういう指向があまりないのです。
Clojureは今のところ趣味で、主にProject Eulerとか解くのに使っているわけですが、以前、デスクトップアプリ作ってみたのでその時のことを。
環境
---------------------------------------
- マシン
自宅ではLinux機メインでやってますけど、仕事ではWin機です。
- エディタ
いつもはエディタとしてxyzzyを使っているのですが、Clojureを使うには環境があまり整備されていないし(自分でなんとかしろ？ですよねぇ。)、ClojureBoxってのがあるようなので、入れちゃうことにしました。
でも、もうメンテされていないので、1.3.0にしたければ自分でやることになります。...
