## Project Euler Problem #120

### May 3, 2010

Read the details of the problem here

**Summary**

Finding the maximum remainder when (a ā 1)^{n} + (a + 1)^{n} is divided by a^{2}.

**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)^{1} + (a+1)^{1}

2a

For n = 2:

(a-1)^{2} + (a+1)^{2}

(a^{2}-2a+1) + (a^{2}+2a+1)

2a^{2} + 2

For n = 3:

(a-1)^{3} + (a+1)^{3}

(a^{3}-3a^{2}+3a-1) + (a^{3}+3a^{2}+3a-1)

2a^{3} + 6a

For n = 4:

(a-1)^{4} + (a+1)^{4}

2a^{4} + 12a^{2} + 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 ^{2}*

For n = 5:

(a-1)^{5} + (a+1)^{5}

2a^{5} + 20a^{3} + 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 ^{2}*.

So I only need to deal with odd values of *n* and the remainder calculation is just *2an % a ^{2}*. The value of this function is obviously minimised when

*2an = m.a*for all values of

^{2}*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.

May 18, 2012 at 20:17

[…] and KeyZero Conversation both have good discussions about this […]