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

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

Written by on 27 October 2012

Topics: Project Euler

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.

6 Comments For This Post I'd Love to Hear Yours!

  1. Eman says:

    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;
    
    }
    
  2. Dilshan says:

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

  3. Dilshan says:

    sry my mistake i found my mistake sry…

  4. Henry says:

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

  5. Sukun says:

    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

  6. Sukun says:


    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 Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.