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, 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.
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
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
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
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?
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.
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.
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
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
Hi! That’s not very complicated to find boundaries for z and d, even with subtraction. To produce positive n, d need to be larger than z/3. This approach worked for me.