Problem 58どうしても素数判定に時間がかかりますが、どうにかならないのでしょうか。素数判定を高速に行うといえばエラトステネスのふるいですが、ふるい的な手法は使えないでしょうか。実は使えます。 対角線上の数を分けて考えましょう。まず、右下は平方…

Project Eulerのフォーラムは一定数投稿があると新規投稿を受け付けていなかったが、リニューアルで投稿できるようになった。人よりよい解法を持っていると思ったら投稿していきたい。よい投稿があると称号が得られるらしい。 以下は備忘録として記しておく…

Problem 58解を概算してみましょう。 素数定理が使えそうです。素数定理で素数の密度がだいたいわかります。x付近で整数log x個に平均約1個素数があります。例えば、10000の前後だとlog10000 ≒ 9.2個に1個、1億だと18.4個に1個素数があることになります。 さ…

Problem 58Problem 28の対角線上を辿るコードをそのまま使えます。あとは適当に素数判定するだけです。 10%で3.4s、9%で26sでした。かなり遅い素数判定ですが。

Problem 57これも多倍長整数を使うだけですね。 x + 1 = 2 + 1 / (x + 1) x2 + 2x + 1 = 2x + 2 + 1 x2 = 2 で連分数が√2となることがわかります。 連分数の漸化式は計算で求まりますが、見ればわかりますよね。

Problem 56これも多倍長整数の問題です。乗算は加算より簡単です。

Problem 55再び多倍長整数の問題ですね。加算だけなので簡単です。1桁ずつリストに格納すると計算が楽になります。これを勝手にLongIntという型の名前にしています。加算のときに、繰上りを考慮して1桁余分に配列を確保しています。桁が増えなければtailで切…

フォーラムにアップした。基本的に、ScalaでProject Euler（57）の内容と同じ。英語はおかしいことは分かっているが勘弁してもらう。

どこが変わったのか、前に出ていた告知をざっと読んだだけであまり覚えていないけど、満杯だったフォーラムにも書き込めるようになったので、このブログの成果を少しずつ書き込んで行けたらなあと思う。英語書かなきゃいけないと思うと気が重いけど。 325問…

Problem 54まず手札を同じ数でまとめます。その際、ソートしておくとあとで便利です。枚数で比較して同じなら数で比較します。 5H 5C 6S 7S KD -> List((2, 5), (1, 13), (1, 7), (1, 6))次に同じ数系の役になっていないか調べます。Scalaならパターンマッチ…

Problem 53パスカルの三角形の下から計算します。まず、n = 100のときの最小のrを求めます。次にn = 99のときの最小のrを先ほどのrから始めて求めます。rが求まらなくなったらおしまいです。

http://projecteuler.net/index.php?section=problems&id=351問題見て、なんとか理解する。六角形、いやな感じがしてでかける。駅までダッシュして階段を降りたところから考え始める。乗り場についたときにはだいたいわかった。どう考えても楽勝問題だ。出社…

http://projecteuler.net/index.php?section=problems&id=344まったく手がかりがつかめなかった。8月下旬、Project Eulerの夏休みも終わるのでそろそろこの問題を解いておこうと思い、幸い固有名詞があるのでそれで検索した。そうすると英語のページがヒット…

Problem 52[1, 10/6)に10のべき乗を掛けたものが答えになりえますが、桁数が増えるごとに範囲を絞り込むことができます。例えば6桁でそれぞれ上2桁が10,20,30,40,50,60だとこれで7つ数字があるのでアウトです。11,22,33,44,55,66なら12個数字があるので、12…

Problem 526倍まで桁上りがあってはいけないので、[1, 10 / 6)を10のべき乗で掛けた数になります。あとは、各倍数の10進の数字をソートして比較するだけです。

http://projecteuler.net/index.php?section=problems&id=350問題見たときすでに22人正答者がいた。 最初全然わからなかったが、歩きながら考えているうちにわかってきた。コードは短い。本質的な部分は5行。実行時間は5秒。34着。

http://projecteuler.net/index.php?section=problems&id=349日曜日、Problem 348を上げてから問題文を読む。しかし英語がわからない。なんとか理解して風呂に入って考えるがさっぱりわからない。翌朝電車の中で考えるがやっぱり何も出てこない。ノートを取…

http://projecteuler.net/index.php?section=problems&id=348少し数学を使って素因数分解→約数というよくあるパターンにしたら25秒になった。まだ速くなりそうだが。

http://projecteuler.net/index.php?section=problems&id=348日曜の夜にProblem 349の答えをアップした後、まだ時間があるのでごく自然に回文数を昇順に生成してそれが題意を満たすか調べた。4つ目までは順調に求められたが、5つ目がなかなか出てこない。結…

http://projecteuler.net/index.php?section=problems&id=347おとといの昼、Problem 346を正答して、この問題を読んだ。素直に書けばいいだけのような。帰ってから素直に組んだら7秒だった。

http://projecteuler.net/index.php?section=problems&id=346昨日の朝Problem 345の答えを入力してまだ始業まで時間が少しあったので、問題を見た。パッと見わからなかったので、小さい方から見てみる。7は2進で111、それから？ああ、6進で11ってことか。っ…

http://projecteuler.net/index.php?section=problems&id=345今朝でかける前に出題されていることを思いだした。5問とももう40人以上正答者がいた。ウォーミングアップのつもりなのだろうか。慌ててこのProblem 345だけざっと見た。ふつうに考えるとO((N+1)!…

いわゆる分割数ではありません。分割して0も認めます。また順番が変わっただけの分割も別とみなします。すなわち、3を3分割なら、 3 = 3 + 0 + 0 = 2 + 1 + 0 = 2 + 0 + 1 = 1 + 2 + 0 = 1 + 1 + 1 = 1 + 0 + 2 = 0 + 3 + 0 = 0 + 2 + 1 = 0 + 1 + 2 = 0 + 0…