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

6 comments

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;

}

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

Leave a Reply