こんにちは。
今回は Project Euler の第1問から第10問まで Haskell で解いてみようと思います。
Project Euler は、時間制限なしの競技プログラミングのようなもので、過去に紹介しています。
そして、Haskell も最近始めました。
実は割と気に入っていて、何かしたいなと思っていたところ Project Euler の存在を思い出しました。
Python で解いていって記事を書いているのですが、Haskell でも練習がてら解いてみます。
(ここ1年くらい更新が止まっていますが…)
以下、ネタバレになる (かもしれない) ので、嫌だという方は先に解いてみてください。
目次
- Problem 1 -Multiples of 3 or 5-
- Problem 2 -Even Fibonacci Numbers-
- Problem 3 -Largest Prime Factor-
- Problem 4 -Largest Palindrome Product-
- Problem 5 -Smallest Multiple-
- Problem 6 -Sum Square Difference-
- Problem 7 -10001st Prime-
- Problem 8 -Largest Product in a Series-
- Problem 9 -Special Pythagorean Triplet-
- Problem 10 -Summation of Primes-
- まとめ
Problem 1 -Multiples of 3 or 5-
10 より小さい 3 または 5 の倍数を並べると 3 5 6 9 となり、これらの和は 23 である。
1000 より小さい 3 または 5 の倍数の和を求めよ。
main = print $ sum [x | x <- [0..999], x `mod` 3 == 0 || x `mod` 5 == 0]
以上です。簡単。
0 から 999 の中から条件を満たす数を選んでリストに入れていき、最後に各要素の和をとって出力すれば完了です。
答えは 233168 と出力され、正解でした。
ちなみに、sum は以下のように定義できます。
sum' [] = 0 sum' (x:xs) = x + sum' xs
引数で受け取ったリストの先頭を足して残りを sum' に、を繰り返していきます。
引数が空のリストになったら 0 を足して終了です。
Problem 2 -Even Fibonacci Numbers-
フィボナッチ数列のある項は、その前2つの数字を足すことで計算される。
1 2 から始めると、初めの10項は 1 2 3 5 8 13 21 34 55 89 となる。
400万を超えない範囲で考えたとき、偶数のフィボナッチ数を全て足すといくらになるか。
fib = 1 : 2 : zipWith (+) fib (tail fib) main = print $ sum [x | x <- takeWhile (< 4000000) fib, x `mod` 2 == 0]
フィボナッチ数列を出力するプログラムは、Haskell を紹介したときに書きました。
とりあえず zipWith を使ったものを選びました。
問題文から、リストの1, 2番目の要素は 1 2 になるように変更しています。
fib はリストになっているので、400万より小さい要素を取り出し、2 の倍数 (偶数) のものだけを選び、最後に和をとって完了です。
答えは 4613732 と出力され、正解でした。
ちなみに、takeWhile は以下のように定義できます。
takeWhile' c (x:xs) | c x = x : takeWhile' c xs | otherwise = []
c は条件式を指し、これをリストの先頭の要素に適用した c x が真のときは、その要素をリストにいれて残りの部分を再び takeWhile' に渡します。
偽のときは空のリストを返し、繰り返しが終わります。
また、ここで使っているのは | を行頭において条件を示す書き方で、数式を
$$ f(x) = \begin{cases} x & (x \geq 0) \\ -x & (x < 0) \end{cases} $$
のように書くときと似ています。
(条件と返り値の位置が逆ですが。)
Problem 3 -Largest Prime Factor-
13195 の素因数は 5 7 13 29 である。
600851475143 の素因数の中で最大のものは何か。
factorize 1 = [] factorize n = f : factorize (n `div` f) where f = [x | x <- [2..], n `mod` x == 0] !! 0 main = print $ factorize 600851475143
factorize は素因数分解をする関数です。
f は n の最小の約数 ([x | x <- [2..], n mod x == 0] !! 0) を受け取っています。
2以上の整数 x で n を割り、割り切れた場合 x は n の約数だとわかるので f に入れる、という感じです。
これは遅延評価の為せる技で、約数が1つでも見つかれば f に渡せるので無駄な計算が行われません。
f が求まったところで、それをリストにいれるとともに n div f を factorize に渡します。
あとは同じことが繰り返され、n div f が 1 になったところで終了です。
(「``」がはてなブログと干渉してしまったので、mod や div を囲う記号は説明文では省いてあります。)
素因数分解の結果、[71,839,1471,6857] が出力され、正解でした。
Problem 4 -Largest Palindrome Product-
回文数はどちらから読んでも同じである。
2桁の数の積として表せる最大の回文数は 9009 = 91 × 99 である。
3桁の数の積として表せる最大の回文数は何か。
main = print $ maximum [x | x <- [a * b | a <- [100..999], b <- [100..999]], show x == reverse (show x)]
[a * b | a <- [100..999], b <- [100..999]] で総当たりで積を計算し、show x == reverse (show x) で回文数かどうか判定します。
回文数になったものだけをリストにいれ、その中から最大のものを出力します。
答えとして 906609 が出力され、正解でした。
ここで、show は数値を文字列に変換する関数、reverse は順序を逆にする関数です。
(ちなみに、文字列を数値に変換するときは read 文字列 :: Int のようにします。)
reverse、maximum は以下のように定義できます。
reverse' [] = [] reverse' (x:xs) = reverse' xs ++ [x]
maximum' [] = [] maximum' (x:xs) = max' x (maximum' xs) where max' x y | x > y = x | otherwise = y
Problem 5 -Smallest Multiple-
2520 は 1 から 10 の数で割り切ることができる最小の数である。
1 から 20 の数で割り切ることができる自然数の中で最小のものは何か。
main = print $ foldr lcm 1 [1..20]
Python で解いたときにも書いていますが、1~20 で割り切れるということは $20!$ かというとそうではなく、最小公倍数を考える必要があります。
引数に渡した2つの数の最小公倍数を求める関数 lcm がありますので、それを利用します。
fn [] = 1 fn (x:xs) = lcm x (fn xs) main = print $ fn [1..20]
と書けば良いのですが、fn と似た機能を持った関数が既にあります。
それが foldr です。
foldr は以下のような定義ですので、f が lcm、v が 1 に対応していることになります。
foldr' f v [] = v foldr' f v (x:xs) = f x (foldr' f v xs)
プログラムを実行すると、答えとして 232792560 が出力され、正解でした。
ちなみに、lcm は以下のように定義できます。
gcd' x y | y == 0 = x | otherwise = gcd' y (x `mod` y) lcm' x y = x * y `div` gcd' x y
ここで gcd' は最大公約数を求める関数で、ユークリッドの互除法 (ユークリッドの互除法 - Wikipedia) を使っています。
定義をそのまま書いたような感じですがうまく動きました。
そして、$\mathrm{gcd} (x, y) \times \mathrm{lcm} (x, y) = a \times b$ と表せるので、$\displaystyle \mathrm{lcm} (x, y) = \frac{a \times b}{\mathrm{gcd} (x, y)}$ で最小公倍数が求められます。
また、foldr の親戚に foldr1 という関数があります。
これは空のリストが渡されるとエラーを吐くようになっており、その一歩手前、すなわち配列の最後の要素を v として計算してくれる foldr です。
foldr1' f [v] = v foldr1' f (x:xs) = f x (foldr1' f xs)
これを使えば、この問題ではわざわざ v を指定しなくても良くなります。
main = print $ foldr1 lcm [1..20]
Problem 6 -Sum Square Difference-
1 から 10 までの自然数の2乗の和は 385、和の2乗は 3025 である。
よって、この2つの差は 3025 - 385 = 2640 となる。
同じことを 1 から 100 までの自然数で行うと答えはどうなるか。
main = print $ (sum [1..100])^2 - sum [x^2 | x <- [1..100]]
単純に計算すれば良いだけです。
実行すると 25164150 と出力され、正解でした。
Problem 7 -10001st Prime-
初めの6つの素数を並べると 2 3 5 7 11 13 となり、6番目の素数は 13 だとわかる。
10001番目の素数は何か。
sieve [] = [] sieve l@(x:xs) = x : sieve [a | a <- l, a `mod` x /= 0] main = print $ (sieve [2..]) !! 10000
sieve では 2 以上の整数の無限リストを渡すと、その中から素数だけを返してくれます。
いわゆる「エラトステネスのふるい」を使っており、計算自体は Wikipedia (エラトステネスの篩 - Wikipedia) にあるのと同様です。
受け取ったリストの先頭の数の倍数を除いて、その結果をまた sieve に渡す、という感じです。
l@(x:xs) は、受け取ったリストを変数に束縛しています。
(x:xs) はリストの先頭を x に、残りを xs に入れることを意味しており、@ を挟んで何か変数 (ここでは l) をつければその変数にリスト全体を入れることができます。
答えとして 104743 が出力され、正解でした。
Problem 8 -Largest Product in a Series-
問題文にある1000桁の数の中で隣接した4個の数の積の最大値は 9×9×8×9 = 5832 である。
隣接する13個の数の積の最大値はいくつか。
num = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450" digit = 13 products = [product (separate x) | x <- adjacents num digit] where separate l = [read [l !! i] :: Int | i <- [0..(length l)-1]] adjacents l n = [extract l i n | i <- [0..(length l)-n]] extract l i n = [l !! (i+x) | x <- [0..n-1], i+x < length l] main = print $ maximum products
なかなか煩雑になってしまいました。
extract は l の中の i 番目の要素から n 個分取り出してくる関数です。
adjacents は l の中から n 個取り出したときに得られる数列全てを返す関数です。
separate は l から取り出した数列を1文字ずつに区切り、さらに数値に変換します。
products は取り出した数の各桁の積を計算し、その結果を全て入れておくリストです。
最後に products の中から最大値を探し、出力します。
答えとして 23514624000 が出力され、正解でした。
余談ですが、read 文字列 :: Int の文字列の部分は String 型でないといけないようです。
l !! i だけだと一文字に相当する Char 型として扱われてしまうので [] で囲うことでリスト化し、String 型に変換しています。
Problem 9 -Special Pythagorean Triplet-
ピタゴラス数は以下の条件を満たす3つの数の組み合わせである。
$$ a^{2} + b^{2} = c^{2}, ~ a < b < c $$ 例えば、$3^{2} + 4^{2} = 9 + 16 = 25 = 5^{2}$ となる。
$a + b + c = 1000$ となるピタゴラス数が1組存在するが、その積 $abc$ は何か。
triplets l = [[a, b, c] | m <- [1..l], n <- [1..m], let a = m^2-n^2, let b = 2*m*n, let c = m^2+n^2, a + b + c == l] main = print $ product $ (triplets 1000) !! 0
Wikipedia (ピタゴラス数 - Wikipedia) から、自然数 $m$ と $n$ について、$m > n$、$(a, b, c) = (m^{2}-n^{2}, 2mn, m^{2}+n^{2})$ を満たせば良いとわかるので、それをそのまま書いたような感じです。
また、各辺の和が 1000 になるという条件もあるので、$a + b + c = 1000$ も追加しています。
[375,200,425] が見つかり、積を計算して 31875000 が出力されます。正解でした。
Problem 10 -Summation of Primes-
primes = 2 : [x | x <- [3,5..], isPrime x] where isPrime n = all (\p -> n `mod` p /= 0) (takeWhile (\p -> p*p <= n) primes) main = print $ sum $ takeWhile (< 2000000) primes
Problem 7 でつくったエラトステネスのふるいが役に立ちます。
のはずでしたが、10001番目の出力でも若干時間がかかっていたこともあってか、
sieve [] = [] sieve l@(x:xs) = x : sieve [a | a <- l, a `mod` x /= 0] main = print $ sum $ takeWhile (< 2000000) (sieve [2..])
としても一向に答えが出力されませんでした。
というわけで、初めに載せたような解法を考えました。
試し割り法でもエラトステネスのふるいでも、考える数の最大値の平方根まで試せば良いので、判定する数列は takeWhile (\p -> p*p <= n) primes としています。
ここで、\p -> p*p <= n のような式は「ラムダ式」とよばれる関数で、この式は p を受け取って p*p <= n の真偽を返す関数となっています。
(ラムダ式に関しては記事を作成中です。(いつに公開できるようになるかわかりませんが。))
さらに、2 以外の偶数は全て合成数のはずなので、primes には先に 2 を入れておき、素数かどうかの判定 isPrime は奇数 [3,5..] のみを考えています。
isPrime では、takeWhile (\p -> p*p <= n) primes として取ってきたリスト全体に対して、\p -> nmodp /= 0 が真であった場合に True を返します。
4秒程度で 142913828922 と出力され、正解でした。
ちなみに、all は以下のように定義できます。
all' c [] = True all' c (x:xs) | c x = all' c xs | otherwise = False
まとめ
以上、Project Euler の問題を Haskell で解いてみました。
書いてみたらコードゴルフでもしているのかというくらい短くなっておもしろいですね。
でもまだまだ勉強が足りず、検索や ChatGPT に頼りまくってました。
冒頭でも書きましたがやっぱり私はこの言語が好きかもしれません。
続編をお楽しみに。
最後まで読んでいただいてありがとうございました。また次回。
