http://projecteuler.net/index.php?section=problems&id=81 80 × 80 の行列を左上から右下まで、右か下にだけ移動しながら辿るとき、各点の値の合計の最小値を求める。 行列を以下のように変形する関数を作って、その結果を６７問目と同じように処理しまし…

http://projecteuler.net/index.php?section=problems&id=80 2 の平方根 1.41421356237309504880... の最初の 100 桁の数字の和は 475 である。1 〜 100 の平方数で無い自然数について、最初の 100 桁の数字の総和を求める。 中学だか高校だかで習った開平法…

http://projecteuler.net/index.php?section=problems&id=79 パスコードに含まれる任意の3つの文字によって認証を行う方法がある。例えば 531278 というパスコードから 2, 3, 5 番目の文字を取り出すと 317 となる。逆に、認証を通った 3 文字の文字列 50 個…

http://projecteuler.net/index.php?section=problems&id=78 n 個のコインをいくつかの山に分けるときの場合の数を p(n) とおく。例えば 5 個のコインは 7 通りの方法で分けられるので p(5)=7 である。p(n) が百万の倍数となるような n のうち最も小さい値を…

http://projecteuler.net/index.php?section=problems&id=76 100 を 2 個以上に分割する方法は何通りあるか。 「2 個以上に分割」≡「99 以下の数で分割」です。 100 というそれほど大きくない数が相手なので、ここは List にメモして凌いでます。 main = pri…

http://projecteuler.net/index.php?section=problems&id=77 10 を素数の和として表す方法は 5 通りある。素数の和として 5000 より多い方法で表せる最初の数を求める。 まっすぐ計算。何も工夫してません。 main = print $ euler077 5000 euler077 :: Integ…

http://projecteuler.net/index.php?section=problems&id=74 ある数に対して、各桁の数字の階乗の和を求めていくとき、どんな数でも無限ループとなるが、繰り返し部分を除いた鎖の長さがちょうど 60 となるような数は百万未満でいくつあるか求める。 最初に…

http://projecteuler.net/index.php?section=problems&id=75 周の長さが 120 の直角三角形は (30,40,50), (20,48,52), (24,45,51) の3つを作ることができる。周の長さを L としたとき、直角三角形が1つだけ作れるような L は L ≦ 2000000 にいくつ存在するか…

http://projecteuler.net/index.php?section=problems&id=72 d ≦ 1,000,000 について、既約分数 n/d はいくつあるか求める。 dを分母とする既約分数の数はトーティエント関数φ(d)に一致するので、それを1000000まで足し合わせています。 import Data.List ma…

http://projecteuler.net/index.php?section=problems&id=73 1/2 と 1/3 の間に分母が10000以下の既約分数がいくつあるか求める。 律儀に数えてます。 import Data.List import Data.Ratio main = print $ euler073 3 2 10000 euler073 :: Int -> Int -> Int…

http://projecteuler.net/index.php?section=problems&id=71 分母が 1,000,000 以下の既約分数を値の小さいものから順に並べたとき、 3/7 の左に来るものの分子は何か求める。 1,000,000 以下の分母について、 3/7 "未満"で最大となるような分子を求めるので…

http://projecteuler.net/index.php?section=problems&id=69 n ≦ 1,000,000 について、オイラーのトーティエント関数 φ(n) を考えるとき、 n/φ(n) が最大になるような n を求める。 n の素因数の種類が多いほど φ(n) は小さくなるので、素数を小さいものから…

http://projecteuler.net/index.php?section=problems&id=70 1 7 で、かつ φ(n) が元の数の並べ替えになっているような n について、n/φ(n) が最小となるものを求める。 最初に書いたコードはこれです。brute force で素因数分解しながら、題意の条件を満た…

http://projecteuler.net/index.php?section=problems&id=67 三角形に配置された数字を頂点から反対側の辺まで辿るときに、数字の和が最大となるような経路を求める。 以前に解きました。

http://projecteuler.net/index.php?section=problems&id=68 この問題を図なしで説明できる自信はないので、リンク先を見てください。 求める文字列が16桁なので、10は外側にあります。最大の文字列を求めたいので、6から9も外側。あとは並べ替えながら最大…

メモ化について確認している中で、以前に解いた23問目のコードについて、メモ化したものと性能を比較してみたところ、気になることがありました。 オリジナルはこれ。 main = print $ euler023 5000 euler023 :: Int -> Int euler023 limit = sum $ filter (…

http://projecteuler.net/index.php?section=problems&id=66 不定方程式 x2 - Dy2 = 1 について、D=13 のとき x の最小値は 6492 - 13×1802 = 1 となる。Dが平方数のとき、自然数の範囲では解がないと想定されている。D ≦ 7 で平方数でないDに対してxの最小…

http://projecteuler.net/index.php?section=problems&id=65 √2 の連分数展開を [1; 2,2,2, ...] と表記するとき、自然対数の底 e は [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...] と表現できる。分数にすると 2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/…

http://projecteuler.net/index.php?section=problems&id=64 N ≤ 10000 に対して、Nの平方根を連分数展開したときに、循環部の長さが奇数になるものがいくつあるか求める。 漸化式を求めて無限リストを作った後は、２６問目と同じように「ウサギとカメ」のロ…

http://projecteuler.net/index.php?section=problems&id=62 立方数 41063625 (3453) の数字を並べ替えると、他に2つの立方数 56623104 (3843) と 66430125 (4053) ができる。同様に、並べ替えると全部で5つの立方数ができるような数のうち、最小のものを求…

http://projecteuler.net/index.php?section=problems&id=63 5桁の数 16807=75 は5乗であり、9桁の数 134217728=89 は9乗になっている。このようにn乗になるn桁の整数は全部でいくつあるか求める。 10乗以上だと桁と指数が一致するものが無いので、9乗まで。…

http://projecteuler.net/index.php?section=problems&id=61 8128, 2882, 8281 の3つの数の組合せは以下の特徴を持つ。 それぞれの数の最後の2つの数字が次の数の最初の2つの数字となっており、循環している。 8128は三角数、2882は四角数、8281は五角数で、…

http://projecteuler.net/index.php?section=problems&id=60 7 と 109 をつなげた数は 7109 も 1097 も素数となる。素数 3, 7, 109, 673 はどの2つをつなげても素数となる。同様にどの2つをつなげても素数となるような素数5つの組合せについて、その和の最小…

http://projecteuler.net/index.php?section=problems&id=59 XOR関数によって暗号化された文章がある。キーには英語の小文字3文字を繰り返した文字列を用いている。この文章を復号化し（元の文章は一般的な英単語から成っている）、そのASCIIコードの和を求…

http://projecteuler.net/index.php?section=problems&id=58 1から始まる数を時計回りにらせん状に配置していく。四隅の数のうち素数の占める割合が最初に10%未満になるのは、一辺の長さがいくつのときか求める。 若干遅いので、もう少し上手いやり方がある…

http://projecteuler.net/index.php?section=problems&id=56 a, b 自然数 ab の各桁の数字の和の最大値を求める。 問題文の通りです。 import Data.Char main = print $ euler056 99 99 euler056 :: Integer -> Integer -> Int euler056 ma mb = maximum $ m…

http://projecteuler.net/index.php?section=problems&id=57 √2は以下のように連分数展開できる。 1 + 1/2 = 3/2 = 1.5 1 + 1/(2 + 1/2) = 7/5 = 1.4 1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666... 1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379... …

http://projecteuler.net/index.php?section=problems&id=55 47は逆順にして足すと 47 + 74 = 121 で回文となる。349は 349 + 943 = 1292, 1292 + 2921 = 4213, 4213 + 3124 = 7337 と3回の操作で回文となる。196のように何度操作しても回文にならない数（Ly…

http://projecteuler.net/index.php?section=problems&id=53 1 ≤ n ≤ 100の n に対して、nCr が百万を超えるものがいくつあるか数える。 素直に求めます。 main = print $ euler053 100 euler053 :: Integer -> Int euler053 m = length $ filter (> 1000000…

http://projecteuler.net/index.php?section=problems&id=54 ポーカーの手を二人分千組含むファイルから、一人目のプレイヤーが勝つ組がいくつあるかを求める。 それぞれの手についてワンペアは1点、ロイヤルフラッシュは9点といった点数をつけ、その大小を…