# 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.

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