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

Letrbe the remainder when (a-1)^{n}+ (a+1)^{n}is divided bya^{2}.

For example, ifa= 7 andn= 3, thenr= 42: 6^{3}+ 8^{3}= 728 42 mod 49. And asnvaries, so too willr, but fora= 7 it turns out thatr_{max}= 42.

For 3 ≤a≤ 1000, find ∑r_{max}.

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.

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

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);

}

}

sry my mistake i found my mistake sry…

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

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

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