カテゴリー: Project Euler

三角数の第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]

192に1,2,3をかけると192 x 1 = 192, 192 x 2 = 384, 192 x 3 = 576となる。

これらを連結した数は192384576は1から9の数字を一つずつ含む数である。ここ で192384576を192と(1,2,3)の連結積と呼ぶことにする。

同様のことは9に1,2,3,4,5をかけることでも実現できる。918273645は9と (1,2,3,4,5)の連結積である。

整数と(1,2,…,n)の連結積で1から9の数字を一つずつ含むものの最大値を求め よ。ただし、n>1とする。

数は各桁の数のリストで扱う。1から9の数字を一つずつ使ったものかどうかの 判定は関数isPandigitalで行う。ここでは数をリストで表しているので、sort したものが1から9のリストになっているかで判定できる。数nに0からiまでかけ た積を連結したリストを求める関数をconcatProductsとする。再帰的にリスト を連結することで実現している。isPandigitalを満たすのはconcatProductsの 結果が9桁の場合のみであるが、そうなる場合を手でソース上に列挙して解を求 める。

euler038 = maximum $ map listToInt $ filter isPandigital
           ([concatProducts 2 n | n <- [5000..9999]]
            ++ [concatProducts 3 n | n <- [100..333]]
            ++ [concatProducts 4 n | n <- [25..33]]
            ++ [concatProducts 5 n | n <- [5..9]]
            ++ [concatProducts 6 n | n <- [3]])
    where isPandigital n = sort n == [1..9]
          concatProducts i n
              | i == 0    = []
              | otherwise = concatProducts (i - 1) n ++ intToList (n * i)

3797には面白い特徴がある。まずそれ自身が素数である。そして、左から右に 1桁ずつ数字を取り除いたときに、3797,797,97,7がそれぞれ素数である。右か ら左に取り除いた場合も3797,379,37,3が同様に素数である。

左右どちらからでも取り除く操作が可能な全ての11個の素数の和を求めよ。

注意：2,3,5,7は取り除くことが可能な数と考えない。

問題の条件の判定をする関数をtruncatableとして以下のように定義する。まず 対象の数を各桁のリストに分解し、そのリストをsplitAtで二つに分けたものの すべてが素数であるかどうかを調べる。この操作で左から取り除く場合と右か ら取り除く場合の両方を調べたことに相当する。そして10以上の素数の中でこ の条件を満たすものを11個取り出し和を求める。対象となる素数が11個である ことが問題文に与えられていることに依存している。

euler037 = sum $ take 11 $ filter truncatable $ dropWhile (<10) primes
    where truncatable n = all bothPrime [ splitAt i ns
                                          | i <- [1..(length ns - 1)]]
              where ns = intToList n
                    bothPrime (a, b) = (isPrime $ listToInt a)
                                       && (isPrime $ listToInt b)

10進数の585は2進数で1001001001であり、どちらも回文になっている。

1000000未満の数で10進表記でも2進表記でも回文になっているものの和を求め よ。

回文の判定には先頭の0は含めないことに注意せよ。

2進表記の場合、各桁の数は1か0しか存在しないので少なくとも1の位は1でない と回文にならないことがわかる。よって対象となる数は奇数のみである。そこ で100万未満の全ての奇数についてfilterで回文になるものを取り出し和を求め る。回文の判定はreverseしたリストが元のリストと同じものかで行う。2進数 への変換は問題34で定義したintToListと同じ要領で定義する。

intToBinary n = reverse $ i' n
    where i' n
              | n >= 2   = let (d, m) = divMod n 2
                           in m : i' d
              | otherwise = [n]

isPalindrome l = reverse l == l

euler036 = sum $ filter both [1,3..999999]
    where both n = (isPalindrome $ intToList n)
                   && (isPalindrome $ intToBinary n)

197の各桁を回転させた数、197,971,719は全て素数なので197を循環素数と呼ぶ ことにする。

100未満の数でそういう素数が13個あり、 2,3,5,7,11,13,17,31,37,71,73,79,97である。

1000000未満の循環素数の数を求めよ

問題10で定義した素数のリストから1000000未満の部分を取り出す。その中で循 環した数が素数になっているものをfilterで取り出しリストの長さを求める。 循環した数は素数になっているかはローカル関数circularでチェックする。こ こで2以外の偶数は素数ではないので、nが2か全ての桁の数が奇数であるかの条 件でチェックすることで多少高速化できる。次に対象の数を各桁の数に分解し たリストを回転させて、再び数に変換したものが全て素数であるかをチェック する。素数の判定は問題27で定義した関数を用いる。

euler035 = length $ filter circular $ takeWhile (< 1000000) primes
    where circular n = (n == 2 || (all odd ns))
                       && (all isPrime [listToInt $ rotate i ns
                                        | i <- [1..(length ns - 1)]])
              where ns = intToList n
                    rotate i ns = let (a, b) = splitAt i ns
                                  in b ++ a

145は1!+4!+5!=1+24+120=145となる面白い数である。

各桁の数の階乗の和が自分自身と等しくなるような全ての数の和を求めよ。

注意：1!=1と2!=2は和ではないので含めない。

問題30と同様に9!*7が7桁なので3000000以上の数に解がないことがわかる。ま た1や2は和じゃないので含まないと問題の注釈にあるので、3から3000000の数 のリストについて条件を満たすかを試すことにする。

まずは階乗のリストをfactorialsとして無限リストで定義する。ここでは scanl関数を使用する。scanl関数は与えられた関数と初期値でリストの要素を 順番に適用していく。次の要素に適用するときは初期値の変わりに前の結果を 使うので、例えば掛け算では階乗のような値を求めることができる。結果のリ ストには初期値も含まれるので、以下の定義で0からの階乗のリストとなる。こ の場合!!の操作で階乗の値を取り出せるので直感的である。

次に自然数を各桁ごとの数のリストに変換する関数intToListを定義する。ここ では10より小さくなるまで10で割り、そのあまりをリストにして最後に reverseで順番を整えている。この問題では実際には順番は関係ない。

factorials = scanl (*) 1 [1..]

intToList n = reverse $ i' n
    where i' n
              | n >= 10   = let (d, m) = divMod n 10
                            in m : i' d
              | otherwise = [n]

euler034 = sum $ filter curious [3..3000000]
    where curious n = (sum $ map (factorials !!) $ intToList n) == n

49/98は面白い分数である。経験の足りない数学家が間違ったやり方で簡約しよ うとして9を取り除いたとき、49/98=4/8となりこれは正しい。

30/50=3/5のようなものは自明な場合とする。

分子と分母が2桁で値が1より小さい分数で、自明ではないこのタイプの分数が ちょうど4つ存在する。

これらの4つの分数の積が規約分数で与えられたときの分母を求めよ。

Haskellには有理数が用意されているのでこれを用いることにする。import Ratioで使用可能になる。リストの内包表記で対象となる分数のリストを生成し、 productで積を求め、denominatorで分母が求まる。値は自動的に既約分数となる。 分数の値は%で生成できる。

ソースコード的な美しさは全くないが、分子の10の位をa、1の位をb、分母の 10の位をc、1の位をdとして、問題の条件を以下のようなコードにする。2桁の 数なので10の位に0はこない。また自明な場合は対象にならないので1の位も0は 含まない。ある数字を取り除く操作があるので、10の位と1の位は同じ値になら ない。分数の値は1より小さい。自明な場合意外ということで、分数の値をxと したときa==dでb/c=xの場合とb==cでa/d=xの場合がありえる。この条件で生成 された分数を最初に書いた処理をすれば答えが求まる。

euler033 = denominator $ product [(a * 10 + b) % (c * 10 + d)
                                  | a <- [1..9], b <- [1..9],
                                  c <- [1..9], d <- [1..9],
                                  curious a b c d]
    where curious a b c d = a /= b && c /= d && x < 1
                            && ((a == d && b % c == x)
                                || (b == c && a % d == x))
              where x = (a * 10 + b) % (c * 10 + d)