Project Euler 135: Same differences

In Problem 135 of Project Euler we have another nice number theory problem. The problem reads

Given the positive integers, x, y, and z, are consecutive terms of an arithmetic progression, the least value of the positive integer, n, for which the equation, x² – y² – z² = n, has exactly two solutions is n = 27:

34² – 27² – 20² = 12² – 9² – 6² = 27

It turns out that n = 1155 is the least value which has exactly ten solutions.

How many values of n less than one million have exactly ten distinct solutions?

The first key insight which I missed for a while, is to notice that x,y and z is an arithmetic progression which means that we have that y = z + d and x = z + 2d. Where d is an integer, such that we can rewrite the problem to

Which means we can run through values of d and z in order to find solutions for the question. However, one problem is that we still have a subtraction, which means I have a problem finding  upper and lower bounds for d and z that we have to check. However we can change variables such that we have

Then we get that

And that means we can loop over positive values of u and v as long as  uv <= n. When we do that we have to check if z and d are positive integers.  Based on the definition of u and v we can solve for d and z. Then we get that

So if d and z are integers and 3v > u (meaning that z is positive), then we have a solution for n = uv. And then we just have to loop over all posible solutions, which we can do with the following piece of code

int n = 1000000;
int[] solutions = new int[n+1];</pre>
for (int u = 1; u <= n ; u++) { for (int v = 1; u * v <= n; v++) { if ((u + v) % 4 == 0 && 3 * v > u && ((3 * v - u) % 4) == 0) solutions[u * v]++; } } int result = solutions.Where(x => x == 10).Count(); 

This gives us the solution in less than 40ms. The solution is

number of values with exactly 10 solutions: 4989

You can find the complete source code here.