2011-11-01から1ヶ月間の記事一覧
http://projecteuler.net/index.php?section=problems&id=360ガウス整数を使ってまじめに組んだら、35分で答えが出た。やれやれ。 実質的な計算は14分で終わっていたはずだが、そこで答えが出ない。最初はガベコレが働いているのかと思ったが、そこから延々…
http://projecteuler.net/index.php?section=problems&id=360昨日の昼に問題を読み返してみて誤読に気が付いた。 1010に絶望していたが、今朝10を手計算してみたりしてだんだんわかってきた。しかし、雑に組んでみたら100時間くらいかかりそうだった。なかな…
http://projecteuler.net/index.php?section=problems&id=360これは数式の計算問題っぽいな。明日考えよう。
大規模で田舎といういかにも豊田なマラソン大会。 1km 5:22.66 5:23 2km 9:39.73 4:17 4km 18:29.32 4:25 6km 27:35.96 4:33 7km 32:14.28 4:38 8km 36:49.42 4:35 9km 41:02.69 4:13 10km 45:13.90 4:11けっこうひどい。
Problem 70この問題は、 Aを満たす数でBが最小のものを求めよ というパターンなので、 Bの昇順に並べてAを満たす最初の数を求めよ と読み替えればよいです。すなわち、n / φ(n)(以下、phi比と呼びます)の小さい順に並べればよいです。幸いこれはそんなに難…
Problem 70とりあえず、素直に解いてみましょう。ふるい的に素因数分解して、全ての対象の整数についてφを求め並べ替えになっているか調べ、n/φ(n)が最小のものを選びます。 これで10秒です。Pythonでは16倍くらい遅かったです。
Problem 69オイラーのφ関数は前に書いたように、 なので、 です。素数を昇順に掛けていくだけですね。
Pythonで何も考えずにエラトステネスのふるいのコードを書くとこんな感じでしょうか。 def sieve(max_n): a = [ True ] * L for p in takewhile(lambda n: n * n < L, (n for n in xrange(2, L) if a[n])): for k in xrange(p * 2, L, p): a[k] = False Bool…
Problem 68まず外の5つを決めます。その和をsext、内側の和をsintとします。 sext + sint = 55 です。1列の和をslineとします。全ての列の和を取ると、内側は2回ずつカウントするので、 5sline = sext + 2sint sint = 5(sline - 11) sintは5の倍数、sextも5…
http://projecteuler.net/index.php?section=problems&id=359寝坊。20分くらいして問題を見る。なかなか頭に入ってこない。今日の午前中はなにかと忙しい。ナイーブに書いて、なんとなくわかった。もう20kmジョグに行かないといけない時間だ。走りながら考え…
単語の補完が遅いことがたまにある。自動的に単語がツールチップで表示されるはずなのに、なかなか出てこない。昨日それに遭遇した。なぜそうなるのかずっとわからなかったが、昨日わかった。単語検索の対象に前の秀丸が含まれていて、それが100MB級のテキス…
Problem 67メモ化ですね。 3 7 4 2 4 6 8 5 9 3一番下はそのままにして、2番目の左端、2を考えます。2の下は8と5ですが、トータルで最大になるのは8を選んだ時です。それを2に加えます。 3 7 4 10 4 6 8 5 9 3この列を同じように処理すると、 3 7 4 10 13 15…
Problem 66Pell方程式の最小解と連分数には驚くべき関係があります。たとえば、Problem 64で例に挙げられた√23は、 √23 + 4 = [ 8; 1, 3, 1, 8, 1, 3, 1 ... ] ですが、1周期で打ち切ったとき、 [ 4; 1, 3, 1 ] = 24 / 5 で、この(24, 5)が 242 - 23 * 52 = …
Problem 66 x - Dy2 = 1 これをPell方程式と呼びます。これには必ず整数解があることが知られています。この整数解が大きくなると、 x/y√(1-x-2) = √D よりx/yは√Dの近づくことになります。√Dの連分数展開と同じですね。実際、Pell方程式の解は連分数展開を…
http://projecteuler.net/index.php?section=problems&id=358今朝電車の中で1/17の計算をして、それをじっと見ていたら気がついた。ああ、そういうことね。その通りに組んでみて、あと素数判定はやめて直接サイクル長がp - 1になるかを判定したら1msecになっ…
http://projecteuler.net/index.php?section=problems&id=358今朝問題を見たが、時間が無くて問題を把握できず。昼休みに考えて、これは連分数でやれば簡単だろ、と思ったがうまくいかない。前後を見なければならないんだな。その通りに夜になって書いたが、…
Problem 65連分数の最後に書いた漸化式を使うと簡単です。ただし、64ビットの範囲で解けないので多倍長整数が必要です。
Problem 64ループの長さが奇数になる数を具体的に並べてみましょう。 2, 5, 10, 13, 17, 26, 29, 37, 41, 50, 53, 58, 61, 65, 73, ... これらを素因数分解すると、因数は2か4で割って1余る素数になっています。 ただ、逆は違うようです。すなわち、すべて2…
Problem 64連分数です。連分数はペル方程式と関係が深く、この後の問題の前振りになっているかもしれません。 問題を解くには問題文に書かれた手順を実行すればよいです。 としてa, b, cの変化をチェックします。そしてループを検出します。(a, b, c)が以前…
http://projecteuler.net/index.php?section=problems&id=357すでに200人オーバー。全部やってもできそうだが、もうちょっと工夫して77秒。
アップミスで順番が逆になってしまいました。Problem 623乗して同じ桁になる数を用意して並び替えると同じになる数ごとに分類します。同じ数は、降順にでも並び替えればいいですね。8なら3乗して512を並び替えて521です。並び替えて同じになる数が5つあれば…
Problem 63この問題はふつうに解くと64ビットの範囲では解けません。多倍長整数を使ってもよいのですが、ここはlogを使いましょう。基数b、指数eに対して題意が成り立つには、 be ≥ 10e-1 logを取って、 e log b ≥ (e - 1)log 10 e log (b / 10) ≥ -log 10 e…
Problem 61これはグラフにすると比較的考えやすいです。例にあるように8128は三角数ですが、81という点と28という点が線で結ばれていて重みが3と考えます。ネットワークですね。4桁の3〜8角数を全て求めてネットワークを作ります。そうしたときに、ある点か…