月: 2008年5月

クリスチャン・ゴールドバッハは全ての奇数の合成数は素数と平方数の2倍の和 で表せると提唱しました。9 = 7 + 2 * 1 ^ 2, 15 = 7 + 2 * 2 ^ 2, 21 = 3 + 2 x 3 ^ 2, 25 = 7 + 2 * 3 ^ 2, 27 = 19 + 2 * 2 ^ 2, 33 = 31 + 2 * 1 ^ 2

しかしこの予想は間違いでした。

奇数の合成数で素数と平方数の2倍の和で表せない最小のものを求めよ。

奇数のなかで素数でないものをfilterで選ぶことで奇数の合成数を求める。次 にgoldbach関数で予想を満たさないものをfilterし、headで最小の要素が求ま る。

goldbach関数では対象となる値より小さい素数を引いたリストを求め、その差 が平方数の2倍のリストの中にあれば条件を満たすというのをintersectを用い て求めている。

euler046 = head $ filter goldbach $ filter (not . isPrime) [3,5..]
    where squares2 = map (* 2) squares
          goldbach n = intersect (map (n -) ps) ss == []
              where ps = takeWhile (< n) primes
                    ss = takeWhile (< n) squares2

三角数、五角数、六角数はそれぞれ次の式で求められる。 三角数、Tn = n (n + 1) / 2、1, 3, 6, 10, 15, … 五角数、Pn = n (3n – 1) / 2、1, 5, 12, 22, 35, … 六角数、Hn = n (2n – 1)、1, 6, 15, 28, 45, …

ここでT285 = P165 = H143 = 40755ということがわかる。

次に三角数かつ五角数かつ六角数となる値を求めよ。

三角数、五角数については以前に定義したものを使う。六角数は以下のように 無限リストで定義する。

三角数について、関数alsoでその値が五角数および六角数に含まれているかを filterし、求まったリストの2番目で解が求まる。

hexagonals = 1 : zipWith (+) hexagonals diffs
    where diffs = [5,9..]

euler045 = (filter also triangles) !! 2
    where also n = (n == (last $ takeWhile (<= n) pentagonals))
                   && (n == (last $ takeWhile (<= n) hexagonals))

五角数はPn = n (3n – 1) / 2という式で生成できる。五角数の最初の10項は次 の通りである。1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …

P4 + P7 = 22 + 70 = 92 = P8 であることがわかる。しかし、その差 70 – 22 = 48は五角数ではない。

二つの五角数PjとPkで、その和と差が五角数であるものうち、差が最小になる ときのその差を求めよ。

まず五角数を以下のように定義する。問題文では各項を求める式で定義してあ るが、五角数の無限リストを定義する場合には、以下のように差が3n+1になる ような数列として定義することもできる。

次に、リストの内包表記を用いて、二つの五角数で、その和も差も五角数であ るものの差のリストを求め、そのリストの最小値を求める。ここでは計算時間 の都合上、5000項目までを計算しているが、解が存在しなければ対象とする範 囲を大きくする必要がある。

pentagonals = 1 : zipWith (+) pentagonals diffs
    where diffs = [4,7..]

euler044 = minimum [k - j | j <- ps, k <- ps, j < k,
                    elem (j + k) ps, elem (k - j) ps]
    where ps = take 5000 pentagonals

1406357289は0から9までの数字を1回ずつ使った数で、その一部を取り出したと きに以下のような面白い特性がある。

d1を1桁目の数字、d2を2桁目の数字としたときに、 d2d3d4 = 406は2で割り切れる、 d3d4d5 = 063は3で割り切れる、 d4d5d6 = 635は5で割り切れる、 d5d6d7 = 357は7で割り切れる、 d6d7d8 = 572は11で割り切れる、 d7d8d9 = 728は13で割り切れる、 d8d9d10 = 289は17で割り切れる。

この特性を持った全ての数の和を求めよ。

まず0から9のpermutationを求め、その中で問題の割り算の特性を持ったものだ けをfilterで取り出し、その和を求めることにする。ただしpermutationは各桁 の数字のリストなのでsumを適用する前にmapでlistToIntを適用する。

割り算の特性が成り立っているかどうかは関数divisibleで判別する。それぞれ の位置から3桁とりだし、割る数（素数を小さいほうから順番に並べたもの）で 割ったあまりのリストを求め、それが全て0のときに条件を満たす。

euler043 = sum $ map listToInt $ filter divisible $ permutation [0..9]
    where divisible ns = all (== 0) [(listToInt $ take 3 $ drop (i - 1) ns)
                                     `mod` (primes !! (i - 2))
                                     | i <- [2..8]]

三角数の第n項は1/2n(n+1)で求まる。したがって、三角数の最初の10項は次のようになる。1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

単語に含まれる文字をそのアルファベットの位置に応じて数値に変化して足し たものをその単語の値とする。例えば、SKYの単語の値は19 + 11 + 25 = 55で あり、三角数の第10項である。単語の値が三角数であるものを三角語と呼ぶこ とにする。

words.txtに含まれている約2000個の単語の中で三角語の数を求めよ。

words.txtの内容はダブルクオートされた単語のリストであるが、最初と最後に []を付け加えるとHaskellで容易に読み込めるので、問題22と同様にエディタで 編集を行うことにする。ここではデータファイルの名前をeuler042.datとする。

問題22と同様の関数scoreで単語の数値を計算し、それが三角数のリストに含ま れているかどうかで判別して数を求める。三角数としては問題12で定義した trianglesと使う。単語の値は1文字あたり最大でも26なので、三角数のリスト としては1000より小さい範囲で判別する。

euler042 = do x <- readFile "euler042.dat"
              return $ length $ filter isTriangle $ map score $ read x
    where score s = sum $ map (\x -> ord x - 64) s
          isTriangle n = elem n $ takeWhile (< 1000) triangles

n桁の数が1からnまでの数字を1回ずつ含むときにpandigitalと呼ぶことにする。 例えば、2143は4桁のpandigitalであり素数である。

もっとも大きなpandigitalな素数を求めよ

問題27で定義した素数判定関数は何度も計算を繰り返さない代わりにその数以 下の素数のリストを全て計算するので大きな数を判定するときに非常に低速で ある。ここでは判定のたびに計算するが大きな数で判定で多少高速な isPrimeを定義する。

次に問題の定義に従って2桁から9桁までの全てのpandigitalな数のリストを生 成し、その中で素数のものを取り出し最大値を求める。

isPrime n = all (\x -> n `mod` x /= 0)
            $ takeWhile (\x -> x * x <= n) primes

euler041 = maximum $ filter isPrime
           $ map listToInt $ concat [permutation [1..n] | n <- [2..9]]

小数点以下に整数を連結させていくことで、0.1234567891011121314…という 無理数を定義できる。

この少数の小数点以下12桁目の数は1である。

dnを小数点以下n桁目の数としたときに、次の式の値を求めよ。 d1 x d10 x d100 x d1000 x d10000 x d100000 x d1000000

無理数irrationalを問題の定義通りリストの連結で表す。そこで問題の桁数の 値を求め積を計算する。

euler040 = product [irrational !! (10 ^ n) | n <- [0..6]]
    where irrational = concat $ map intToList [0..]

pを辺の長さが整数{a,b,c}の直角三角形の周囲の長さとしたとき、p = 120には ちょうど3つの解が存在し、{20,48,52},{24,45,51},{30,40,50}である。

p<1000でもっとも解の数が多くなるものを求めよ。

周囲の長さとそのときの三辺の長さの組み合わせのtupleを対象として最大値を 求める。三辺の組み合わせはリストの内包表記を用いて全て求める。

euler039 = fst $ maximumBy cmpSnd [(n, length $ sols n) | n <- [3..999]]
    where sols n = [(i, j, n - i - j)
                    |i <- [1..n - 2], j <- [i..(n - i) `div` 2],
                    i ^ 2 + j ^ 2 == (n - i - j) ^ 2]