0. 概要
Project Eulerの問題をHaskellで解いてみました.
(題名そのまま)
取り敢えず1から10まで。
1. 問題
Problem 1 「3と5の倍数」
10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.
同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.
Problem1.hs
main :: IO()
main = print $ sum [x | x <-[1..999], x `mod` 3 == 0 || x `mod` 5 == 0]
Problem 2 「偶数のフィボナッチ数」
フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項の値が400万以下の, 偶数値の項の総和を求めよ.
Problem2.hs
fib :: [Integer] -> [Integer]
fib f@(x1:x2:y) | x1 > 4*10^6 = x2:y
| otherwise = fib ((x1+x2):f)
fib _ = [1]
main :: IO()
main = print $ (sum . filter even . fib) [2,1]
Problem 3 「最大の素因数」
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
Problem3.hs
import Data.List
main :: IO()
main = do
let n = 600851475143
print $ head . head . filter (\x -> length x == 2) . map divisor $ divisor n
divisor :: Integer -> [Integer]
divisor n = divisor' n 2 bound [1,n]
where bound = (truncate . sqrt . realToFrac) n
divisor' :: Integer -> Integer -> Integer -> [Integer] -> [Integer]
divisor' n d b ret | b < d = (sortBy . flip) compare ret
| n `mod` d == 0 = divisor' n (d+1) b (d:(n `div` d):ret)
| otherwise = divisor' n (d+1) b ret
Problem 4 「最大の回文積」
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.
Problem4.hs
main :: IO()
main = print $ maximum [x * y | x <- [100..999], y <- [100..999], cond (x * y)]
cond :: Integer -> Bool
cond n = and $ zipWith (==) (show n) ((reverse . show) n)
Problem 5 「最小の倍数」
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
Problem5.hs
main :: IO()
main = print $ foldl1 lcm [1..20]
Problem 6 「二乗和の差」
最初の10個の自然数について, その二乗の和は,
1^2 + 2^2 + ... + 10^2 = 385
最初の10個の自然数について, その和の二乗は,
(1 + 2 + ... + 10)^2 = 3025
これらの数の差は $3025 - 385 = 2640$ となる.
同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.
Problem6.hs
main :: IO()
main = print $ (sum [1..100])^2 - sum [x^2|x<-[1..100]]
Problem 7 「10001番目の素数」
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10 001 番目の素数を求めよ.
Problem7.hs
import Data.Numbers.Primes
main :: IO()
main = print $ primes !! (10001-1)
Problem 8 「数字列中の最大の積」
以下の1000桁の数字から13個の連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか.
73167176531330624919225119674426574742355349194934 \\
96983520312774506326239578318016984801869478851843 \\
85861560789112949495459501737958331952853208805511 \\
12540698747158523863050715693290963295227443043557 \\
66896648950445244523161731856403098711121722383113 \\
62229893423380308135336276614282806444486645238749 \\
30358907296290491560440772390713810515859307960866 \\
70172427121883998797908792274921901699720888093776 \\
65727333001053367881220235421809751254540594752243 \\
52584907711670556013604839586446706324415722155397 \\
53697817977846174064955149290862569321978468622482 \\
83972241375657056057490261407972968652414535100474 \\
82166370484403199890008895243450658541227588666881 \\
16427171479924442928230863465674813919123162824586 \\
17866458359124566529476545682848912883142607690042 \\
24219022671055626321111109370544217506941658960408 \\
07198403850962455444362981230987879927244284909188 \\
84580156166097919133875499200524063689912560717606 \\
05886116467109405077541002256983155200055935729725 \\
71636269561882670428252483600823257530420752963450
EX 6桁の数123789なら, 1*2*3*7*8と2*3*7*8*9の二通りとなり, 後者の2*3*7*8*9＝3024が最大の積となる.
Problem8.hs
import Data.Char
inStr :: String
inStr = "73167176531330624919225119674426574742355349194934" ++
"96983520312774506326239578318016984801869478851843" ++
"85861560789112949495459501737958331952853208805511" ++
"12540698747158523863050715693290963295227443043557" ++
"66896648950445244523161731856403098711121722383113" ++
"62229893423380308135336276614282806444486645238749" ++
"30358907296290491560440772390713810515859307960866" ++
"70172427121883998797908792274921901699720888093776" ++
"65727333001053367881220235421809751254540594752243" ++
"52584907711670556013604839586446706324415722155397" ++
"53697817977846174064955149290862569321978468622482" ++
"83972241375657056057490261407972968652414535100474" ++
"82166370484403199890008895243450658541227588666881" ++
"16427171479924442928230863465674813919123162824586" ++
"17866458359124566529476545682848912883142607690042" ++
"24219022671055626321111109370544217506941658960408" ++
"07198403850962455444362981230987879927244284909188" ++
"84580156166097919133875499200524063689912560717606" ++
"05886116467109405077541002256983155200055935729725" ++
"71636269561882670428252483600823257530420752963450"
main :: IO()
main = print $ maxProduct inStr 0
maxProduct :: String -> Int -> Int
maxProduct [] ret = ret
maxProduct str ret | length str >= 13 = maxProduct (tail str) (max val ret)
| otherwise = ret
where val = (product . map digitToInt . take 13) str
Problem 9 「特別なピタゴラス数」
ピタゴラス数(ピタゴラスの定理を満たす自然数)とは $a < b < c$ で以下の式を満たす数の組である.
a^2 + b^2 = c^2
例えば, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$ である.
$a + b + c = 1000$ となるピタゴラスの三つ組が一つだけ存在する.
これらの積 $abc$ を計算しなさい.
Problem9.hs
main :: IO()
main = print $ [x*y*z| x<-[1..998], y <-[1..1000-x], z <- [1..1000-(x+y)], x^2+y^2==z^2]
Problem 10 「素数の和」
10以下の素数の和は $2 + 3 + 5 + 7 = 17$ である.
200万以下の全ての素数の和を求めよ.
Problem10.hs
import Data.Numbers.Primes
main :: IO()
main = print $ sum $ takeWhile (<=2000000) primes