Project Euler 135: Same differences

Project Euler 135: Same differences

Written by on 9 February 2013

Topics: Project Euler

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.

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

  1. Jean-Marie Hachey says:

    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

  2. Jean-Marie Hachey says:

    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

  3. Jean-Marie Hachey says:

    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

  4. Jean-Marie Hachey says:

    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)

  5. sani says:

    hi

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

  6. Kristian says:

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

  7. Dav2.71828 says:

    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

  8. Leonardo says:

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

  9. Kristian says:

    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.

  10. Matthew Gladback says:

    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.

  11. BartV says:

    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.

  12. Jean-Marie Hachey says:

    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

  13. Jean-Marie Hachey says:

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