Project Euler 25-27

Haskell

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))