月: 2008年5月

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)

7254は39×186=7254としたときに、かける数・かけられる数・積が1から9までの 数字が1回ずつ使われているという特徴がある。

かける数・かけられる数・積で1から9の数字が1回ずつ使われている全の積の和 を求めよ。

ヒント：いくつかの積は複数の方法で得られるが和には一度しか含めない。

式に使われている数字が順列だと考えて、全ての数の並びの組み合わせについ て、それぞれxと=が全ての組み合わせで考えたとき、掛け算の式として成り立 つかどうかを考える。

まず、数字の順列を生成する部分は問題24で定義した関数permutationを使う。 それにmapを用いてローカル関数checkを適用する。ここでは順列のリストを3つ に分割し、1番目の部分と2番目の部分の積が3番目の部分の値になっているかを チェックし、成り立っている場合はその積を返す。3つに分割する部分は、それ ぞれ少なくとも1つの数字を含んでいる必要があるので、1番目の部分の長さが 1から7、2番目の部分が1から8-1番目の長さとなる。ここでリストを数に変換す る関数listToIntを適用しそのtupleを返す。リストを数に変換する関数は foldl1を用いて定義する。foldl1はfoldlと同様にリストの要素を順番に関数に 適用するが、初期値としてリストの先頭の要素を用いる。

listToInt = foldl1 (\x y -> x * 10 + y)

euler032 = sum $ nub $ concat $ map check $ permutation [1..9]
    where check l = [z | (x, y, z) <- split, x * y == z]
              where split = [split' i j | i <- [1..7], j <- [1..8 - i]]
                        where split' i j =
                                  let (x, l2) = splitAt i l
                                      (y, z) = splitAt j l2
                                  in (listToInt x, listToInt y, listToInt z)

イギリスの通貨はポンドとペンスから成り立っており、 1,2,5,10,20,50,100,200ペンスの8種類の硬貨が一般に流通している。

以下のような組み合わせで200ペンスを作ることができる。 1×100+1×50+2×20+1×5+1×2+3×1

200ペンスを払うには何通りの硬貨の組み合わせ方があるかを求めよ

硬貨を大きい方から考えて再帰的に考えて、その硬貨を使うことが可能な全て の枚数について残りの硬貨の組み合わせを考えて行けばよい。硬貨の種類を大 きいほうから順にあらわしたリストをcoinsとし、ある金額を与えられた硬貨の リストで何通りにあらわせるかを再帰的に求める関数をwaysとする。ここで硬 貨が1種類しかないときは、1ペンス硬貨ということがわかっているので1通りと する。硬貨が複数種類あるときは先頭の硬貨を0枚から与えられた金額を超えな い枚数まで使った全ての場合についてmapで残りの金額を残りの硬貨であらわし た場合の組み合わせを求め、その和を返す。

euler031 = ways 200 coins
    where coins = [200, 100, 50, 20, 10, 5, 2, 1]
          ways n (c:[]) = 1
          ways n (c:cs) = sum $ map (\x -> ways (n - c * x) cs) [0..div n c]