http://projecteuler.net/index.php?section=problems&id=138 (b / 2, h, L)でピタゴラス数で、hが偶数だとhとbの差が偶数になってしまうので、 h = m2 - n2 b = 4mn L = m2 + n2 m2 - n2 - 4mn = ±1 (m - 2n)2 - 5n2 = ±1 これもペル方程式です。

http://projecteuler.net/index.php?section=problems&id=137 Fk = Fk-1 + Fk-2 を利用すれば簡単です。 AF(x) + xAF(x) = xF1 + x2(F2 + F1) + x3(F3 + F2) + ... = xF2 + x2F3 + ... = (AF(x) - x) / x AF(x) = x / (1 - x - x2) これがnだとすると、 n x2…

http://projecteuler.net/index.php?section=problems&id=136 前問と同じ方法では時間がかかりすぎます。前問では全体を同時に計算しましたが、これで遅いときは逆に個々に計算するとよいことがあります。ここでは解の個数が1になる条件を考えます。 n = (3d…

http://projecteuler.net/index.php?section=problems&id=135 初項をa、公差をdとすると、 n = (a + 2d)2 - (a + d)2 - a2 = (3d - a)(d + a) となります。 dを固定してaを変えましょう。dが小さいとき、1 ≤ a ≤ 3d - 1となりますが、dが大きいときにa = dを…

http://projecteuler.net/index.php?section=problems&id=134 p1 = 19、p2 = 23とすると、 100x + p1 = p2y という不定方程式を解くだけです。 Pythonにはteeという関数があるのですね。 from itertools import tee def gen(): for n in xrange(10): print n…

http://projecteuler.net/index.php?section=problems&id=133 素数pでR(10n)が割り切れるということは、A(p)でR(10n)が割り切れるということです。そのようなnが存在するということは、A(p)は2か5以外の因子を含まないということです。

http://projecteuler.net/index.php?section=problems&id=132 この問題は、素直に10のべき乗の素数による剰余を計算すればよいでしょう。

http://projecteuler.net/index.php?section=problems&id=131 n3 + n2p = r3 と書けます。 まず、nが因子pをe個含むとしましょう。 n = pe m n3 + p n2 = p2e+1(pe-1m + 1)m2 最初の項以外はpを含まないので2e+1は3で割り切れます。そうすると、e-1も3で割り…

http://projecteuler.net/index.php?section=problems&id=130 前回の方法でも十分速く答えが出ますが、もっと速い方法があります。前回は小さい長さのrepunitから一つずつ順に割り切れるかどうか調べました。しかし実際には全てを調べる必要はありません。 …

http://projecteuler.net/index.php?section=problems&id=129 1が続く数は、1からはじまって10倍して1を足すを繰り返します。そのnの剰余を計算するとき、最初に1が続く数を作るととてつもなく大きな数になってしまいます。そこで10倍して1を足してからnの剰…

http://projecteuler.net/index.php?section=problems&id=128 素直に回って座標を出します。ここでは、1を原点、2を(1, 0)、3を(0, 1)とする空間（平面）で考えます。今考えている座標より1層多く計算している素数の個数を計算できるので、1層分早いのと2つ…

http://projecteuler.net/index.php?section=problems&id=127 a = 1の場合は簡単です。その他の場合を考えましょう。 例えばcが16とすると、c / rad(c) = 8となります。だから、rad(a) * rad(b) aとbはそれぞれ2以外の因子を持たなければなりません。2以外で…

http://projecteuler.net/index.php?section=problems&id=126 まず、a × b × cでm層目の立方体の数は、詳しくは書きませんが、サイドとそれ以外を分けて考えると易しいです。 P ≡ a + b + c Q ≡ b c + c a + a b とすると、 Am = 4(m-1)(P+m-2) + 2Q となり…

http://projecteuler.net/index.php?section=problems&id=125 2乗和の公式を使えば、 m2 + … + n2 = n(n+1)(2n+1) / 6 - (m-1)m(2m-1) / 6 あとは回文数の判定をするだけです。

http://projecteuler.net/index.php?section=problems&id=124 10万より小さい自然数を素因数分解し、radを計算してソートするだけです。 もう少し速い方法はないでしょうか。まず、べき乗を含まない自然数を出します。10までなら2,3,5,6,7,10です。例えばrad…

http://projecteuler.net/index.php?section=problems&id=123 (pn-1)n + (pn+1)n = 2n pn (n : 奇数) (pn-1)n + (pn+1)n = 2 (n : 偶数) なので、あとは素数を小さいものから順に出すだけです。上限が決まっていないので、エラトステネスのふるいを少しずつ…

http://projecteuler.net/index.php?section=problems&id=122 べき乗の計算はいわゆるバイナリ法を使うと速いですが、実はバイナリ法より乗算の回数が少ない方法があるという話です。 例えば5乗なら、 a -> a2 -> a4 -> a5 a -> a2 -> a3 -> a5 a -> a2 -> a…

http://projecteuler.net/index.php?section=problems&id=121 4回の場合、全体の場合の数は2*3*4*5、4勝する場合の数は1*1*1*1、3勝する場合の数は1回目に負ける場合の数は1*1*1*1、2回目なら1*2*1*1、3回目1*1*3*1、4回目1*1*1*4なので、勝つ確率は11/120と…

http://projecteuler.net/index.php?section=problems&id=120 (a-1)n + (a+1)nのa2の剰余は、nが奇数なら 2an 偶数なら 2 だから、nが奇数なら rmax = a(a-1) 偶数なら rmax = a(a - 2) となります。

http://projecteuler.net/index.php?section=problems&id=119 調べる範囲を狭めることができます。例えば2乗のとき、3桁の2乗は6桁以下だから各桁を足しても54以下です。2桁なら2乗して4桁以下で各桁を足して36以下だから、底が36より大きいことはありません…

http://projecteuler.net/index.php?section=problems&id=118 これも再帰に持ち込めます。[1,2,3,4,5,6,7,8,9]を用意して、ここから数字をいくつか取り出します。重複を避けるために最も左の数字は必ず選びます。例えば1と3を選んだとき、13も31素数なので、…

http://projecteuler.net/index.php?section=problems&id=117 漸化式にすれば一発です。この問題が最も単純でした。

http://projecteuler.net/index.php?section=problems&id=116 これもProblem 114と同じですね。最後に全て1を除く処理をしています。

http://projecteuler.net/index.php?section=problems&id=299 今回の図形の問題も計算量が膨大だ。 でも、2時間経ったらシンプルになった。 100すら全然合わない。 なんでこれ奇数になってんの？ でかけている時に非常にプリミティブなコードを組んだら、今…

http://projecteuler.net/index.php?section=problems&id=115 前問とほとんど変わりません。

http://projecteuler.net/index.php?section=problems&id=114 この手の問題は、再帰で書いてメモ化ですね。 def num_ways(n): if n <= 2: return 1 else: if memo[n] != 0: return memo[n] m = 1 + sum(num_ways(k) for k in range(n - 3) + [ n - 1 ]) memo…

http://projecteuler.net/index.php?section=problems&id=113 これは単なる重複組合せですね。 N桁までとすると増加数は、 9H1 + … + 9HN = 9C8 + … + N-8C8 減少数は0も使えるから数が0になる場合だけ除いて、 10H1 + … + 10HN - N = 10C9 + … N+9C9 あと、…

http://projecteuler.net/index.php?section=problems&id=112 増加数と減少数を昇順に生成するのは簡単です。これを合成して非バウンド数を昇順に生成します。それと自然数を同時に生成すると、例えば90%のとき、 … 2176 2177 2178 2179 2180 … … 21100 2111…

http://projecteuler.net/index.php?section=problems&id=111 単純に、対象となる整数を生成して素数判定します。生成は、例えば4桁で1を3つ使うとすると、残りの1つの桁をまず決めて、そこに1以外の数字をあてはめます。素数判定は、単純に素数で割っていき…

http://projecteuler.net/index.php?section=problems&id=110 例えば解の個数が100より大きい最小の自然数を考えるとすると、重複を入れて201個以上が必要です。最も大きな素数を使う場合を考えると、各指数が1なので、35 = 243だから、 21・31・51・71・111…