http://projecteuler.net/index.php?section=problems&id=87 28 = 22 + 23 + 24 であり、素数の2乗、3乗、4乗の和として表すことができる。 このような数は五千万未満でいくつあるか求める。 色々な素数について2乗、3乗、4乗の和を求め、重複するものを除い…

http://projecteuler.net/index.php?section=problems&id=88 2以上の自然数 k に対して、N = a1 + a2 + ... + ak = a1 × a2 × ... × ak を満たす最小の数を考える。例えば k=3 のとき、6 = 1 + 2 + 3 = 1 × 2 × 3 が最小となる。2≦k≦12 に対してこのような数…

http://projecteuler.net/index.php?section=problems&id=85 3 × 2 の長方形は 18 個の長方形を含んでいる。二百万に最も近い数の長方形を含む長方形の面積を求める。 a × b の長方形が含む長方形の個数は ab(a+1)(b+1)/4 となるので、(a, b) = (1, 2000) か…

http://projecteuler.net/index.php?section=problems&id=86 6 × 5 × 3 の部屋を隅から反対の隅まで壁伝いに移動するとき、最短距離は 10 で整数となる。m × m × m 以下の大きさの部屋について、最短距離が整数となる部屋の数を考えると、M=100 のとき 2060 …

http://projecteuler.net/index.php?section=problems&id=84 モノポリーには 40 のマスがあるが、それぞれのマスで停まる確率を求め、TOP3を答える。 Project Euler では問題文が長いのは嫌われる傾向にあるみたいですが（５４問目とか）、この問題は色々な…

http://projecteuler.net/index.php?section=problems&id=82 80 × 80 の行列を左辺から右辺まで、右か上か下に移動しながら辿るとき、各点の値の合計の最小値を求める。 行列をタテヨコ変換して、後は最小値を求めていくだけです。 import Data.List main = …

http://projecteuler.net/index.php?section=problems&id=83 80 × 80 の行列を左上から右下まで、上下左右に移動しながら辿るとき、各点の値の合計の最小値を求める。 次に進むべき点が分からないので、これまで通った点の近傍を進むべき点の候補としてリス…

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も外側。あとは並べ替えながら最大…

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/…

裏でこそこそ解き進めているのですが、ようやく１００問を超えました。道半ば。 いつまで続けられるか見ものです。 この企画はあくまでも趣味としてやってますが、そうすっきりと割り切れるものでもなくて、仕事でHaskell使えないかとか欲張り始めている自分…

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つの組合せについて、その和の最小…