等差数列と素数の関係に関する問題。 Problem 49 - PukiWiki項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ。 3つの項はそれぞれ素数である。 各桁は他の項の置換で表される。 もう一個4桁の中に同じ性質を持つものがあるらしい。 作戦と…

五角数に関する問題。 Problem 44 - PukiWiki2つの五角数の和と差を取って、五角数になるものを見つける。 五角数チェックは前に書いたのでコピッペで。2つの和と差は五角数キャッシュを持っておいて、キャッシュと比較してく事にする。 (define (problem44)…

ガンガンいくよ。 Problem 47 - PukiWiki連続する3つの数がそれぞれ3つの異なる素因数を持つものは、こんなんで、 644 = 2^2 × 7 × 23 645 = 3 × 5 × 43 646 = 2 × 17 × 19 連続する4つの数がそれぞれ4つの異なる素因数を持つものを答える。 2^2と2は異なる…

日本人50位になりました。数学なんてちんぷんかんぷんだった僕がここまで来れるとは思ってなかったっす。数学おもろいっす。後は英語・・・。 Problem 43 - PukiWikiまたまたPandigital数。こちらはちときつい。 0〜9までの順列出して全アタック。先頭のゼロ…

後で読み返してみたら、案外簡単だったり。Problem 38 - PukiWiki組合せ数が多いかと思ってたけど、そうでもなかった。1のだけの組合せは無い。と書いてあったのでほっと一安心。回答が9876...になっちゃうのでありえないか。 安心したところで範囲を考える…

ぜぃぜい。やっと解けた。Problem 32 - PukiWiki39 × 186 = 7254のように1から9が一回づつ現われる積の組合せを見つける。 積の組合せは 1桁 * 4桁 = 4桁 2桁 * 3桁 = 4桁 しかない。ということで、 1〜9の中から、1桁or2桁の順列を求める。 差集合を取って…

オイラーと同時代の数学者Christian Goldbachに関する問題。 Problem 46 - PukiWiki奇合成数25は、25 = 7 + 2 * 3^2のように、素数 + 2 * 平方数で表せる。という予想を打ち破れ。という問題。 ゴールドバッハの予想 - Wikipediaとはちょっと違うみたい。 ま…

前に作った素数判定が火を噴きそうだ。 Problem 50 - PukiWiki100万未満の素数を連続する素数の和で表したときに最長になる素数を答える問題。 まずは篩。 (define (make-sieve-of-eratothenes n) (letrec ((sieve (make-vector (quotient (+ n 1) 2) #t)) (…

はじめての非離散系？ Problem 102 - PukiWiki2次元にマッピングされた三角形が原点を含むかどうか判定する。 原点,点A,点Bのz方向の外積を取ってみて、全て同じ方向を向いてたら、含んでる。 ベクトルの話なんか忘れちゃったよ。必死でフルスクラッチ本読ん…

結構面白い。 Problem 85 - PukiWikix * yの枠があって、その中に入る長方形の組合せの数を求める。 1 * 1から順に組合せ数を求めてみると面白いルールが浮かび上がってくる。ルールは内緒。 で、そこからがちと面倒で、2,000,000に一番近い解をどうやって求…

翻訳無いけどやってみる。Problem 65 - Project Euler √2の連分数は、√2 = [1;(2)]と表せて、eの連分数表記は、e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...]こんなんらしい。100項目の分子の数値の和を求める。 問題は長いけど、やることはシンプル。 …

なかなかうまく解けた。 Problem 62 - PukiWiki立方数の数字を入れ替えると、また立方数になっちゃう数を見つける。 41063625 (345^3)に対して、数字を入れ替えて探すと膨大な組合せが必要になってしまうので、ここは考え方を変えて、数字の占める数を保存し…

素数判定を使うことが多いProject Eulerなので、Problem 6,Problem 10の回答例を見ながら試し割りの高速化を図ります。 試し割り編 今までのアルゴリズムは、2以外の素数は奇数。というルールに基づき、3から3,5,7,9,11,13...と偶数で割ってみて√2まで割り切…

ハッカーのたのしみ読んでます。実はこの本、「解説が殆ど無い」。提示されているのは式のみ。後は自分で探るしかないのだ・・・メモメモ。 記号はCの演算子。=は等号。 & マスク。共通するビット以外をオフにする効果を持つ。 例:IPアドレス & サブネットマ…

こ・コレは・・・手に取った瞬間レジに向かってた。ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか作者: ジュニア,ヘンリー・S.ウォーレン,Jr.,Henry S. Warren,滝沢徹,玉井浩,鈴木貢,赤池英夫,葛毅,藤波順久出版社/メーカー: エスアイビーア…

連分数に関する問題。Problem 57 - PukiWiki連分数で√2を求めた時、分子と分母の桁数が違う時の数を数える。 連分数だけじゃ面白くないから、ちょっと変わった感じにしてるみたい。 分数の計算ではまった。 1回目 1 + 1/2 2回目 1 + 1/(2 + 1/2) = 1 + 2/5 3…

メモ化の威力に感動した。 Problem 76 - PukiWiki 100の和の組合せを求める。両替問題のヤバいバージョン。 ナイーブにやってみたら50で破綻した。 1だけの組合せになったら1種類と特殊化することで40秒で完了できるようになった。 同じ計算を何度もやってる…

久しぶりにキマッた。 Problem 69 - Project Euler翻訳無かったけど、オイラーの関数に関する問題。 オイラーの関数φ(n)は、nと互いに素な整数の個数を表す。例えば、φ(6) = {1,5} = 2 φ(10) = {1,3,7,9} = 4n/φ(n)とすれば、nのなかに互いに素な整数の割合…

もうちょいいこう。Problem 71 - PukiWiki100万以下の真既約分数を小さい順に並べて、3/7の左側に来る分数の分子を答える。 素直に並べたら、100万の2乗回はかかるのでムリっぽい。んじゃ、と思って3/7以下に絞ってみたけど、1000分割位で破綻。100万 * 40万…

落ち着いて範囲を考える。 Problem 63 - PukiWiki n乗してn桁になる数はいくつあるか。 ふむふむ。適当に計算してみる。 まず終端。10^1は2桁,10^2は3桁,10^3は4桁・・・となるので、10^nはn乗するとn+1桁。絶対に追いつかない。10以上は除外できる。 小さい…

回文数絡み。 Problem 55 - PukiWiki 349を反転させて足していくと349 + 943 = 1292,1292 + 2921 = 4213,4213 + 3124 = 7337回文数になるらしい。不思議だ。回文数にならないものをLychrel数と言うらしい。50回回しても回文数が見つからなければ、Lychrel数…

うほ。簡単。と思って取り組んでみたら罠が・・・。 Problem 99 - PukiWiki 指数の形で表される2つの数, 例えば 2^11 と 3^7, の大小を調べることは難しくはない. 電卓を使えば, 2^11 = 2048 しかし, 632382^518061 > 519432^525806 を確認することは非常に…

きました。最短経路。Problem 81 - PukiWiki 下記の5次の正方行列で、左上のセルから開始し右下のセルで終わる道を探索する。 ただし下方向と右方向にのみ移動できるものとする。一番小さなパスは下で赤で示されたものである。 このときの合計は2427になる。…

案外ムズイかと思って放置してた問題。Problem 40 - PukiWiki 正の整数を順に連結して得られる以下の10進の無理数を考える:0.123456789101112131415161718192021...小数点第12位は1である.dnで小数点第n位の数を表す. d1 × d10 × d100 × d1000 × d10000 × d1…

50問達成。Problem 41 - PukiWiki n桁の数がPandigitalであるとは, 1からnまでの数を各桁に1つずつもつことである. 例えば2143は4桁のPandigital数であり, かつ素数である.n桁のPandigitalな素数の中で最大の数を答えよ. ハイ。組合せ。しかも、スゲー大量の…

Problem 79(2) - グラフ理論へ - ボクノス の続きです。自分が作ったアルゴリズムがトポロジカルソートだと言う名前に気づいてなかったので・・・。 ところでトポロジカルソートって何者！？ 昨日、新宿でラーメン食った。 腹いっぱいになったので、渋谷のス…

マッチ箱の脳が面白そうだったので、マッチ箱で作るNNを作ってみた。 紹介されてるニューラルネットワークは、凄く単純な仕組みで、 判断が間違ってたら怒る。 情報を修正(学習)する。 繰り返せば正しい判断をするようになる。というもの。 ふむふむ。実装し…

楽しいMIL記号の時間です。 加算器 - Wikipediaみたいなシミュレータを作っていきます。 問題 3.28 オアゲートを作れ。という問題。 (define (logical-or a b) (cond ((or (and (= a 1) (= b 1)) (and (= a 0) (= b 1)) (and (= a 1) (= b 0))) 1) ((and (= …

最短経路の本が面白かったので引き続き。グラフ理論入門作者: R.J.ウィルソン,Robin J. Wilson,西関隆夫,西関裕子出版社/メーカー: 近代科学社発売日: 2001/10/01メディア: 単行本購入: 10人 クリック: 90回この商品を含むブログ (17件) を見る表紙にセンス…

はじめての暗号解読に挑んでみる。 Problem 59 - PukiWiki (訳者注: 文字コードの説明は適当です) 各文字はそれぞれ一意のコードに割り当てられている. よく使われる標準としてASCII (American Standard Code for Information Interchange) がある. ASCIIで…