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, xy, and z, are consecutive terms of an arithmetic progression, the least value of the positive integer, n, for which the equation, x2 – y2 – z2 = n, has exactly two solutions is n = 27:

342 – 272 – 202 = 122 – 92 – 62 = 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.

Posted by Kristian

13 comments

Jean-Marie Hachey

Hi Kristian !

Thanks for the cool solution
🙂

I was wondering about the smallest equation.
I found it with your code.
x=4, y=3, z=2.
(n=3, one solution)

Have a great day,

Jean-Marie

Jean-Marie Hachey

Project Euler 135
and
Graphing Calculator 4.0

http://img22.imageshack.us/img22/8708/pe135graph.jpg

___

Source :

Pacific Tech
http://www.pacifict.com/Home.html

Jean-Marie Hachey

As shown above, the equation of Project Euler 135 can be written as follows :

(z+2d)^2 – (z+d)^2 – z^2 = n

Where d is difference in the variables of this arithmetic decreasing progression.

We can see that if z = 3d, then n=0.
If z>3d, then n<0
If z<3d, then n>0

Jean-Marie Hachey

Table 1
Arithmetic progression
x^2 – y^2 – z^2 = n
(n=1155)
(RE: Project Euler 135: Same differences)

http://img51.imageshack.us/img51/540/pe135tabl1arithprogr.jpg

All d values are prime numbers except in EN 10 where
d=289 (17×17).
___

Sources:

1) Project Euler 135
Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem135.cs

2) Microsoft Visual C# 2010 Express

3) Microsoft Office Excel (2007)

hi

don’t you have tutorials for subjects regarding this interesting topics of math.

Anything in particular you are thinking about, or just in general?

Dav2.71828

Another good solution. I used the quadratic equation on
3d^2 + 2dz – z^2 = n
and it got a bit messy.

One thing I noticed along the way…
(u+v)%4==0 implies u=-v mod 4
This means (3v-u) mod 4 will always equal 0, and does not need to be checked.
Also, since n=u*v (which equals 0,-1,-4, or -9 (mod 4)) There are no solutions for n if n = 1 or 2 (mod 4)
You can use this fact to halve the size of the solution array

I’m very confuzzled. How did you derive “y=z+d” and “x=z+2d”, from your arithmetic progression steps?

I googled the words “arithmetic progression”, the wikipedia article explains pretty nicely what that means. Once you notice that an aritmetic progression is a series of numbers with a fixed distance d, this should be clear.

Matthew Gladback

This solution can be sharpened a good bit. As I’m a C++ programmer, I’m not sure if all these suggestions translate to C#. You can get mod-4 results by bitwise-and 3. You can take advantage of the mod-4 space to precalculate a valid v and increment by 4 to ensure the sums will be zero mod-4. Since u*v must be 0, only values of u less <= floor(sqrt(3*10^6)) will have v values that are valid. Since u is then in O(n^0.5) space, the whole solution becomes O(n). None of this really matters for this problem, but if you want to use this for 136, it makes the solution much faster — I got mine in 1.1 seconds.

z + d = (3 * v - u) / 4 + (v + u) / 4 = 4 * v / 4 = v
So, if v is an integer, it is enough to check either z or d for being integer, no need to check both.

Jean-Marie Hachey

In my comment above : (February 13, 2013 at 12:55)

This link (unavailable) :
http://img22.imageshack.us/img22/8708/pe135graph.jpg

has been replaced by :

http://hpics.li/28c5783

Jean-Marie Hachey

In my comment above : (February 16, 2013 at 19:59)

This link (unavailable) :

http://img51.imageshack.us/img51/540/pe135tabl1arithprogr.jpg

has been replaced by :

http://hpics.li/ecf0b45

Leave a Reply