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

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
   (a2-2a+1) + (a2+2a+1)
   2a2 + 2

For n = 3:
   (a-1)3 + (a+1)3
   (a3-3a2+3a-1) + (a3+3a2+3a-1)
   2a3 + 6a

For n = 4:
   (a-1)4 + (a+1)4
   2a4 + 12a2 + 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 a2

For n = 5:
   (a-1)5 + (a+1)5
   2a5 + 20a3 + 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 a2.

So I only need to deal with odd values of n and the remainder calculation is just 2an % a2. The value of this function is obviously minimised when 2an = m.a2 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.

Advertisements

One Response to “Project Euler Problem #120”


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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: