2012-09-01から1ヶ月間の記事一覧

Project Euler 396

http://projecteuler.net/index.php?section=problems&id=39629着。 手計算すればだいたいわかる。 G(8)以降は爆発して剰余の計算をしなければならないが、意外と簡単である。

Project Euler 361(2)

http://projecteuler.net/index.php?section=problems&id=361あれからいろいろ考えて、なんとかAnの計算量をO(log n)にしたかったのだが、結局断念した。 それでもだいぶ速くなった。1018まで 0.06s 1050まで 0.65s 10100まで 0.41s 10200まで3s 10400まで23s

Project Euler 395

http://projecteuler.net/index.php?section=problems&id=39525着。15ms。 ふつうに組んだら倍々ゲームになるので答えは出ない。PCを離れて考えてみたらすぐに思いついた。

ABC予想とProject Euler

数学の難問「ABC予想」、京大教授が解明かWikipediaを読んでもわからないと思う。ここのrという関数は、Project Euler Problem 127に書かれているradのことのようだ。この問題ではc 20まで求められているらしい。どうやって求めればよいのだろう。 [追記 …

Project Euler 394(2)

http://projecteuler.net/index.php?section=problems&id=394今朝考え直して、分割数Nとして計算量がO(N2)からO(N)になった。これでインチキしなくても20秒で収束した。

Project Euler 394

http://projecteuler.net/index.php?section=problems&id=394なかなか収束しないんだけど、加速法を2回使ったらなんか収束した。

Project Euler 289

未解決問題を解こうシリーズ第7弾。http://projecteuler.net/index.php?section=problems&id=289382着。 Problem 393とだいたい同じ。

Project Euler 393

http://projecteuler.net/index.php?section=problems&id=39371着。単なる実装ゲー。

Wilsonの定理の拡張

Problem 160に少し出てくるので考えてみました。Wilsonの定理は、 pが素数なら(p - 1) ! ≡ -1 です。これは、pを法とした既約剰余類群の元を全て掛け合わせると-1となる、とも言えます。その積をP(p)と書くことにします。例えばp = 7として P(7) = 1 * 2 * 3…

Project Euler 361

未解決問題を解こうシリーズ第6弾。http://projecteuler.net/index.php?section=problems&id=361123着。20ms程度。今まで最も解かれていない問題。現在正答者200人以下の問題は10問らしい。それだけ難解にしてかつ華麗な問題。なんとか再帰に持ち込む。しか…

Project Euler 392

http://projecteuler.net/index.php?section=problems&id=39274着。何を間違えているのかと思ったら、符号だった。簡単な問題なのに。