Project Euler Problem #120

Read the details of the problem here

Summary

Finding the maximum remainder when (a − 1)ⁿ + (a + 1)ⁿ is divided by a².

Solution

It’s best, as always, to try to understand and to simplify the search space for these maths type problems in an attempt to reduce the processing complexity especially where Groovy is concerned. The total is the sum of two polynomial expansions which will rapidly grow too large to process as the value of n increases so probably won’t be amenable to a brute-force attempt – at least not without some optimization.

So, looking at the expanded polynomial calculations this is what we get.

For n = 1:
   (a-1)¹ + (a+1)¹
   2a

For n = 2:
   (a-1)² + (a+1)²
   (a²-2a+1) + (a²+2a+1)
   2a² + 2

For n = 3:
   (a-1)³ + (a+1)³
   (a³-3a²+3a-1) + (a³+3a²+3a-1)
   2a³ + 6a

For n = 4:
   (a-1)⁴ + (a+1)⁴
   2a⁴ + 12a² + 2

This pattern is true for all even values of n – the last element will always just be 2 and the other terms are all even powers of a and so evenly divisible by a²

For n = 5:
   (a-1)⁵ + (a+1)⁵
   2a⁵ + 20a³ + 10a

This pattern is followed for all of the odd values of n. Only the lowest element in the expansion, 2an, is significant as the leading elements will always evenly divisible by a².

So I only need to deal with odd values of n and the remainder calculation is just 2an % a². The value of this function is obviously minimised when 2an = m.a² for all values of m. Ignoring m and rearranging that I get n = a/2 – this means that the function will be maximized for n = (a-1)/2. Substituting this back into the exemplar of a=7, n=3 to test it – 2 * 7 * (7-1)/2 = 2 * 7 * 3 = 42. Cool. This means that there’s no need to loop through values for n at all.

Coding this is then very straightforward.

def answer =
    (3..1000).sum { 2 * it * (it - 1).intdiv(2) }
 

This runs in 43 ms.

Conclusion

In the end, Groovy was quite capable of implementing this in a terse and effective manner. A brute force attempt might not have been so successful though.