 # Project Euler 120: Finding the maximum remainder when (a − 1)^n + (a + 1)^n is divided by a^2

Problem 120 of Project Euler is back in the very mathy part of the questions. Or at least the part where I have been able to find a pretty mathy solution for the problem. It reads

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.

If we wanted to brute force this, we would have to investigate all values of a, as well as a whole lot of values of n for each a. So likely it would be a rather big problem space to search through. So let us look at the polynomial expression on the left (a-1)n + (a+1)n.

## The pattern as n evolves

Let us expand the expression for a few values of n

n=1 :

n=2 :

n=3 :

n=4 :

n=5 :

Do you see a pattern here? Since we are interested in the result modulo we can disregard any part of the result with a order equal to or higher than 2 since that will leave no remainder. So we get

n=1 :

n=2 :

n=3 :

n=4 :

n=5 :

So we get that for any even value of n we get 2 as the remainder, and for any odd value we get 2na as the remainder. The question is if we can determine which n will maximize r in the expression .

Well, we can at least say that for for any integer value of m the expression is minimized. Let us look at the smallest value of m=1, we then get which can be rearranged to give .

Since we are dealing with modular arithmetic increasing it means that the expression must be maximized for the value . If you think of the arithmetic as a clock with the hand going around. It has the maximum value just before it reaches zero again. This is the same logic I used here. One thing to note here is that the division should be an integer division, otherwise you would end up with a decimal value of n which is not allowed in the answer.

So now we know the maximum value of n in order to maximize r. So let us substitute that into the original equation and we get

## Coding the solution

Now that we have an analytic expression for for an arbitrary a we can build a simple loop over a and find the solution to the problem.

```int r = 0;
for (int a = 3; a <= 1000; a++) {
r += 2*a*((a-1) / 2);
}
```

This can be executed on my computer in 0.0012ms, or virtually no time at all. It gives us the solution of

```sum of r max = 333082500
```

You can as always find the full source code here.

I know there is a way to rewrite the loop over a into an analytic expression by using a geometric series. But I haven’t dived into that, you can see more about that here. ### Posted by Kristian Eman

Wow great solution. I used brute force and chose a limit for iterating the exponent. It ran pretty quickly indeed. Here it C++.

```#include <iostream>
#include <ctime>
#include <cmath>

using namespace std;
const int LIMIT = 1000;

int main()
{

time_t start = clock();

int i,j;
long long max;
long long temp;
long long moduloLimit;
long long modulo;
long long a,b;   // a = n-1, b = n+1
long long sum = 0;

for(i = 3;i<=LIMIT;i++){

max = 0;
a = i - 1;
b = i + 1;
modulo = i*i;
moduloLimit = i;

for(j = 0;j < moduloLimit;j++){
temp = (a + b) % modulo;

if(temp > max)
max = temp;

a = (a * (i-1)*(i-1)) % modulo;
b = (b * (i+1)*(i+1)) % modulo;
}

sum += max;
}

cout<<sum<<endl;
cout<<"Program last:\t"<<(clock()- start)<<endl;

}
``` Dilshan

i think we have to consider both even and odd values

public class Prob120 {

static long x;

public static void main(String[] args) {
for (int i = 3; i <= 1000; i++) {
x += (i % 2 == 0 ? ((i – 2) * i) : ((i – 1) * i));
}
System.out.println(x);
}
} Dilshan

sry my mistake i found my mistake sry… Henry

To back the “right before 12” argument we can use a congruence “cancellation law.” Forgive me if this was implied, but I think laying it out elucidates the floor division.

In general if ac = bc (mod m) and d = gcd(m, c), then a = c (mod m/d). In our case gcd(a, a^2) = a, so that 2na = 2n (mod a). Of course, the maximum value in this modulus is (a – 1). And maximizing the reduction 2n will maximize 2na, since we just multiply by a.

Now, assume a is odd, so that (a – 1) is even. The maximum occurs with 2n = (a – 1), i.e. n = (a – 1)/2 = floor{ (a – 1)/2 }.

Otherwise, assume a is even. Then gcd(2, a) = 2 and we cancel 2n = n (mod a/2). The maximum occurs with with n = a/2 – 1 = (a – 2)/2 = floor{ (a – 1)/2 }. Sukun

Don’t we need to check that floor((a-1)/2) isn’t even. since if it’s even then n = even => the remainder is 2. What am I missing here?

``` rsm = 0 for a in range(3, 1001): rmx = 0 asq = a*a for n in range(1, a+1, 1): rem = ((a-1)**n) + ((a+1) ** n) rem = rem % asq rmx = max(rmx, rem) rsm += rmx ```

this gives a different answer than the one that’s accepted Sukun

``` rsm = 0 for a in range(3, 1001): rmx = 0 asq = a*a for n in range(1, a+1, 1): rem = ((a-1)**n) + ((a+1) ** n) rem = rem % asq rmx = max(rmx, rem) rsm += rmx ```