2020-04-01から1ヶ月間の記事一覧
10進法でも2進法でも回文となる数のうち、1,000,000以下のものの和を求める。 今回は自信作である。解説する力量が自分にはないかも知れないが、最初のコードが20秒近い計算時間を要したものが、Data.Mapを使うことで0.2秒まで劇的に早くなった。 まず10進法…
197は素数だが、その循環である971, 719 もまた素数である。1,000,000までの中に、そのような循環素数はいくつあるか。 素数を探索しなければならない時点で、速さはある程度諦めざるを得ない。色々と考えたが、やっぱり素数探索は簡単には早くならない。 循…
145 は 階乗(!)を用いて 1! + 4! + 5! = 145 となる数である。このような数を全て求めてその和を計算する。 似たような計算の繰り返しになるので、連想リストを使ったら早くなるのではと思って試したが、結果から言えばどストレートに計算するのが一番早かっ…
49/98はその値が1/2に等しいが、分子分母に共通する数字"9"を除いた4/8もまた1/2に等しい。このように分子分母から共通の数字を取り除いても値が変わらない（2桁）/（2桁）の分数が、自明な物（10/40 = 1/4 のように分子分母が10の倍数のもの）を除いて4つあ…
39 × 186 = 7254は1から9までの全ての数字が1回ずつ出てくる。このように積の形で書ける数（この例では7254）を1から9のPandigitalと呼ぶ。全ての1から9のPandigitalな数の和を求めよ。 素直に問題をコードに書き下すだけで答えが出る。計算が重たいので、効…
英国の通貨（1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p) ：pはペンス）を使って£2 (200p)を両替する方法は何通りあるか いわゆる両替問題である。普通に漸化式をhaskellに書き下しても解けることは解ける。例えば100円を50円玉、10円玉、5円玉、1…
1634 = 14 + 64 + 34 + 44 は4乗の和だが、このように各桁の5乗の和が元の数と等しくなる数を全て足すといくつになるか。 設定をコードにするのは比較的簡単である。問題は検索範囲、つまりどこまでの数を調べれば良いかというところだろうか。しかしこれも…
ab ; 2 ≦ a, b ≦100 の範囲で異なる値となるものはいくつあるか この手の設定は計算効率さえ気にしなければHaskellの得意とするところなのではないか。問題文をそのままコードにするだけである。そして今回は計算効率を気にする必要がない。素直に書くだけで…
右回りに数字を配置していき正方形を作ったときの対角線の和を求める。 うーん…。これはハッキリ言って手計算で答えが出ちゃうんだよな…。数字を規則的に並べて和を取るのだから、何らかの公式が作れそうだと考えるべきで、実際簡単に公式が導出できる。なの…
n2 + an +b に n = 0,1,2,...と順に代入したときに、連続して素数を生成する式を作りたい。|a| <= 1000, |b| < 1000の範囲で、最も連続して素数を生成する組み合わせ (a,b)を探しだし、その積 ab を求める。 注意：a,bは負の数でも良い。 まず、n=0において…
1000以下の自然数の逆数で、循環少数の周期が一番長い数を求める。 はじめは与えられたdに対して、循環少数の表記を返す関数を考えたが、なんとなくしっくりこないものしか作れなかった。1/14のように、途中から周期的になる数の扱いが煩雑になりそうなので…
1,1,2…で始まるフィボナッチ数列でFnが始めて1000桁を超えるn。 桁数を数えるのにData.Char.digitToIntを使用。これはProject Euler あるあるかも知れない。あとは普通。 フィボナッチ☆
0123456789の順列を昇順に並べたときに、1000番目に来る並びを求める。 順列をどのように実装するかというのが出題者の意図なのかもしれないなー…と思いつつも、面倒なので、ありがたくData.List.permutationsを使わせていただく。 先人に感謝☆
約数の和が自分自身より大きな数をabundant numberと呼ぶ。28123より大きな数は全て2つのabundant numberの和として表せるが、28123以下の数では必ずしもそうではない。2つのabundant numberの和で表せない全ての数の和を求める。 abundant number はリスト…
名前に対して所定の計算方法で点数をつける。与えられたリストにある名前の点数の合計を求める。 これはストレートに処理するだけ。当然名前をリスト形式 [String] にしないと処理がややこしいが、与えられたテキストファイルの名前を普通に読み込んでも [St…
10,000未満の友愛数を全て足すといくつになるか 友愛数とは数のペアで、自分自身を除く約数の和がお互いに等しいものをいう。 まずは何も考えずにスタンダードに攻めてみる。 これで任意の数の約数の和が求められるので、あとは [1..10000] をfilter [友愛数…
100! の各桁を数の合計を求める またしても僕らのIntegerの恩恵を受ける問題である。むしろそのために全く面白みのない問題となってしまったと言えるだろう。唯一のトピックスは、Data.Char.digitToIntの出番ということだろうか。 秒殺☆
20世紀（1901.1.1 - 2000.12.31）において、1日が日曜日となる月は何回あるか うるう年は4年に1回と思いがちだが、実際は400年に99回という壮大かつ半端な周期である。僕達はミレニアムのうるう年を過ごしたが、実は400年に1度の貴重な「400で割れる年」だっ…
頂点から下へ降りていく中で通った数の和が最大となるときの和はいくつか。 自画自賛も甚だしいが、自分でもよくこの解法を思いついたというくらい、解けて嬉しかった問題。元々はいかに上手にデータ構造を作れば効率よくルート検索できるだろうか…と考えて…
21000の各桁の和を求める。 例） 215 = 32768 → 3+2+7+6+8 = 26 21000ともなるとかなり巨大な数になることが予想されるが、全く問題ない。だって僕達にはIntegerがあるんだから。 数字を桁ごとに分ける操作 breakToDigits がちょっとした小技かも知れない。…
20☓20の格子を左上から右下まで辿る経路の総数を求める 高校で数学を習った日本人なら秒殺の問題がたまに出るのもProject Euler。階乗の計算も教科書通り。こういう時、Integerで何も考えずに巨大な数を扱えるHaskellは大変心強い。 これは簡単☆
100万までの数の中で、最も長いコラッツ列を生成する数を求める コラッツ列： cn が偶数なら cn+1 = cn/2, 奇数ならcn+1 = 3*cn+1 ... と続く数列 まずは素直に書いてみる。 これで答えは出る。ただし時間が掛かる。私のデスクトップで、答えが出るまで3分ち…
下の20☓20の数字列からタテ・ヨコ・ナナメいずれかに4つ並んだ数字の積を取ったときの最大値を求める。 2020/04/11追記: なんとData.Listに標準でtranspose関数があることが判明。しかもそちらの方が優秀で、それを使えばナナメ成分を拾うのが格段に簡単にな…
以下の50桁の数を100個足した答えのはじめの10桁を求める （50桁の数：省略） …？ なんの工夫もいらない。唯一の注意点は "Use Integer!" である。 あとは、10桁を取る際に、Stringにしてtake10する方法と、Integer のままで10桁になるまで10で割り続ける方…
三角数列で約数の数が500を超える最初の数を求める まず思いつく方針は、与えられた数nに対して約数のリストを返す関数fを作り、それを三角数列のリストに対してmap (length.f)してやるというもの。ただしこれは時間が掛かる。ハッキリ言って一晩計算を回し…
下の20☓20の数字列からタテ・ヨコ・ナナメいずれかに4つ並んだ数字の積を取ったときの最大値を求める。 2020/04/11追記: なんとData.Listに標準でtranspose関数があることが判明。しかもそちらの方が優秀で、それを使えばナナメ成分を拾うのが格段に簡単にな…
2,000,000以下の全ての素数の和を求める 素数列の生成は problem 7 で用いたものを使う。 mitstream.hatenablog.jp あとは足すだけ…だよね？すごく時間が掛かるんですけど、原理的に高速化する方法がないように思えます。何かあるんでしょうか？どこかに無駄…
a < b < c a2 + b2 = c2 a + b + c = 1000 を満たす唯一の整数の組 (a,b,c) を見つけ、その積 abc を求める これはリスト内包表記のもとにズバッと一刀両断で終了。 ズバッ…っと ズバッ…と？ 計算が終わらない。落ち着いて考えたらこれだとO(n3)あるのではな…
次の1000個の数字の中からひと続きの13個の数字の積を取る。積の最大値はいくらか。 非プログラマーの自分としては、 IO アクションにはどうも苦手意識がある。do構文も苦手である。だからこの問題は1000桁の数字をコピペして最初から[Int]型として扱うこと…
10001番目の素数を求める まずは伝統的なアレを使ってまっすぐやってみる。当然これで解決するが、思いの外計算が重い。素数列の生成に関しては速いパッケージが存在するので、それを使えばいいじゃないかという（内なる）声もあるが、人のふんどしでパズル…
