Project Euler 25-27

Problem 25

http://projecteuler.net/index.php?section=problems&id=25


単に桁数を求めると遅いが、桁数は数列の前の項のそれと同じかそれより1大きいかなので、それを考慮すると速くなる。


-- number of digits of n is m or m + 1
num_digits n m = if n < 10^m then m else (m + 1)

fib = 1:1:[ a + b | (a, b) <- zip fib (tail fib) ]
fib_num = (1,1):[ (n, num_digits n m) | (n, (_,m)) <- zip (tail fib) fib_num ]
a = filter (\(_,(_,m)) -> m >= 1000) (zip [1..] fib_num)
main = print(fst(head a))

Problem 26

http://projecteuler.net/index.php?section=problems&id=26


dを2と5で割り切ってd'とし、10のべき乗のd'の剰余が最初に1になる指数を探す。
これを999から調べていく。1/dの周期は最大でd-1だから、d-1になったらそこで終わり。だからtakeWhileを使えばよさそうだが、takeWhileはFalseになったらその手前で終わりなのでそれではまずい。そこでFalseになったところまで取るtakeWhile2を自作した。


div_pow n m = if (mod n m) == 0 then div_pow (div n m) m else n
pow_mod n e d | e == 0 = 1
| mod e 2 == 0 = mod (p * p) d
| otherwise = mod (n * p * p) d
where p = pow_mod n (div e 2) d
num_cycle_core n = head (filter (\e -> pow_mod 10 e n == 1) [1..])
num_cycle n = num_cycle_core (foldl div_pow n [2,5])

takeWhile2 f (p:ps) = if f p then p:(takeWhile2 f ps) else [p]

n = 1000
a = map (\m -> (m, num_cycle m)) [n-1,n-2..]
longer (k1,n1) (k2,n2) = if n1 >= n2 then (k1,n1) else (k2,n2)
main = print(fst(foldr longer (1, 1) (takeWhile2 (\(k,n) -> k > n + 1) a)))

Problem 27

http://projecteuler.net/index.php?section=problems&id=27


素直に書く。n=0で素数だから、b素数


import Data.List

is_prime m | m < 2 = False
| otherwise = all (\p -> mod m p /= 0)
(takeWhile (\p -> m >= p * p) primes)
primes = 2:[ m | m <- [3,5..], is_prime m ]
num_primes (a,b) = length (takeWhile (\n -> is_prime (n * (n + a) + b)) [0..])

c = [ (a * b, num_primes (a, b)) |
a <- [-999..999], b <- takeWhile (<1000) primes ]
longer x y = if snd x >= snd y then x else y
main = print(fst(foldl' longer (0, 0) c))