今日は80まで。このところ、数学を使う問題が沢山で面白いですね。 ピタゴラス数とブロコット木 Problem75 簡単には 1,500,000以下のLで a^2 + b^2 = c^2 かつ a + b + c = L を満たす自然数a,b,cの組がちょうど一組となるようなLの個数を求めよ という問題…

久々にProject Eulerやりました。まだrowlは使える段階にないので、Rubyつかってます。 このあたりから数論の問題がいろいろ出てきて面白かったです。 ぺル方程式(Problem 66) 簡単には Dが平方数でない整数の時 x^2 - Dy^2 = 1 の整数解を求めよ という問題…

50問目まで解きました。数学を使って工夫すると速く解けたりするようなものについてだけ自分の解答を書きます。 Problem 15 20x20のグリッドの左上から右下までの最短経路数を求めよ これは２項係数、 の値を計算すれば良いです。２項係数の値はパスカルの三…

8問ときました。 Problem 3 600851475143の最大素因数を求めよ 「素因数分解せよ」ではなく「最大素因数だけ求めよ」ですから素数のテーブルは作りたくないので、反復により求める事を考えます。 整数Nを素因数分解してみると となりますが、これの最小の素…

これはかなりの良門ではないでしょうか。 約数の数が500以上になる最初の三角数を求めよ三角数とは以下の式で書けるものです。 Nの素因数分解が下のようになる時 約数の個数は となります。また、互いに素な2数は指数が重複しないですから、 nが奇数なら で…

Project Euler解き始めました。自分の数学の勉強も兼ねて、できるだけプログラムでの力技の計算は避けようと思っています。どうしてもプログラミングが必要なやつは、あとでrowlで書こうと思ってます。 Problem 1 1000未満の3または5の倍数の和を求めよ 集合…

n個の対応する括弧のパターンの数を母関数を使って求めてみました。 これはid:nobsunさんが指摘なさっているようにカタラン数という数になるんですが、そういう前提知識なしで機械的に解きたいような場合に使えます。 いろんな教科書があると思いますが、私…