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