2011-01-01から1年間の記事一覧
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角数を全て求めてネットワークを作ります。そうしたときに、ある点か…
例えばProblem 60のような条件を満たす最小の解を求る問題を考えます。この問題は条件を満たすような解を小さい順に列挙するのが難しいです。しかし、上限を決めてその範囲で解が存在するかを含めて解くのは比較的簡単です。このようなときは、適当に上限を…
http://projecteuler.net/index.php?section=problems&id=35624時間経ったが、いまだに立方根のところがわからない。というかできそうにない。方針が間違っているのだろうか。
Problem 60まず、素数列を用意します。これにどの向きに結合しても素数になるような素数を探します。例えば(3, 7)ですね。これを結合素数と呼ぶことにします。こうして2つの素数の組を列挙します。これにさらにもう一つ素数を加えて3つの素数による結合素数…
Problem 59シャーロックホームズに出てきたようにeが一番多いのだろうと思ったら違いました。
タイトルの意味がわかりにくいですが、 s = set([((2, 3), 1), ((2, 4), 2), ((2, 3), 3)]) print s set([((2, 4), 2), ((2, 3), 1), ((2, 3), 3)])となりますが、タプルの第2項は無視して第1項だけで同じ値か否かを判定したいときにこれでは困るという場合…
http://projecteuler.net/index.php?section=problems&id=355蟻本を見てみたら、マッチング問題というのに似ている。しかし、違う。もっと複雑な問題だ。とても解けそうな気がしない。 しかし、問題を縮小することは可能そうだ。100のときはできる。そこでど…
http://projecteuler.net/index.php?section=problems&id=355開始3分、まったく何も思いつかない。何かほかごとでもしながら考えるかな。 C(10)はあってるけど、C(30)があわない。考え直しだな。 そうか、そういうことか。 グラフの問題になったんだけど、こ…
http://projecteuler.net/index.php?section=problems&id=354やっと一般化できた。一般化というのは450だけじゃなくて別の数でも解けるようにしたということ。といっても18でしか試していない。しかも6の倍数でしかも6の奇数倍のみ。あと、2か所速くした。 …
エラトステネスのふるいです。ふつうに書いてみます。 def sieve1(N :Int) :List[Int] = { val a = new Array[Boolean](N + 1) for(n <- 2 to N) a(n) = true for(p <- Iterator.range(2, N + 1).takeWhile(p => p * p <= N) if a(p); k <- Iterator.range(p…
Pythonと同じことをします。 まずは試し割りから。 def is_prime1(n :Int) :Boolean = Iterator.from(2).takeWhile(p => p * p <= n).forall(p => n % p != 0) def make_primes(N :Int, is_prime :Int => Boolean) :List[Int] = Iterator.range(2, N + 1).fi…
http://projecteuler.net/index.php?section=problems&id=354やっとできた。45着。 64ビットでなんとかしようとしていたけどうまくいかなくて、そこをあきらめたらあっさりできた。51秒。 もうちょっと速くなって一般化ができたら上げようかな。