# Euler Solution 120

### From ProgSoc Wiki

# Solutions for Problem 120

Let *r* be the remainder when *(a - 1) ^{n} + (a + 1)^{n}* is divided by

*a*.

^{2}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]))