120_square_remainders.rb

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

# For example, if a = 7 and n = 3, then r = 42: 63 + 83 = 728 ≡ 42 mod 49.
# And as n varies, so too will r, but for a = 7 it turns out that rmax = 42.

# For  3 ≤ a ≤ 1000, find ∑ rmax.

sum_of_maximum_remainders = 0
(3..1000).each do |a|
  remainder = []
  (1..1500).each do |n|
    remainder << ((a - 1) ** n + (a + 1) ** n ) % a ** 2
  end
  sum_of_maximum_remainders += remainder.max
end

p sum_of_maximum_remainders