Euler Solution 120

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 120

Let r be the remainder when (a - 1)n + (a + 1)n is divided by a2.

Find the sum of the maximum r for all a in the range 2< a < 1001.

Haskell by SanguineV

Runtime: 27.960 seconds

{- All numbers are cyclic under multiplication modulo "m". So find
 - all the numbers in the cycle for "n". -}
cyc :: Integer -> Integer -> [Integer]
cyc n m = inner (iterate (\x -> mod (x * n) m) n) []
  where
    inner (x:xs) rs
      | elem x rs = rs
      | otherwise = inner xs (x:rs)

{- Given a number, find its maximum remainder as defined in the problem.
 - Note: optimisations to do with length of cycles having common divisors. -}
maxR :: Integer -> Integer
maxR a = maximum tot
  where
    a2  = a * a
    ams = cyc (a - 1) a2
    aps = cyc (a + 1) a2
    lam = length ams
    lap = length aps
    (tam,tap) = case (mod lam lap,mod lap lam,gcd lam lap) of
                  (0,0,_) -> (1,1)
                  (0,_,_) -> (1,div lam lap)
                  (_,0,_) -> (div lap lam,1)
                  (_,_,x) -> (div lap x,div lam x)
    tot = zipWith (\x y -> mod (x + y) a2)
                  (concat (take tam (repeat ams)))
                  (concat (take tap (repeat aps)))

{- Find the sum of all maximum "r"s for "a" in [3..1000] -}
main = print (sum (map maxR [3..1000]))
Personal tools