Project Euler 136: Singleton difference

Problem 136 of Project Euler can be solved in a very easy way, and a very fast way. So lets look at the problem and dive right into the problem which reads

The positive integers, x, y, and z, are consecutive terms of an arithmetic progression. Given that n is a positive integer, the equation,x² – y² – z² = n, has exactly one solution when n = 20:

13² – 10² – 7² = 20

In fact there are twenty-five values of n below one hundred for which the equation has a unique solution.

How many values of n less than fifty million have exactly one solution?

So this sounds a bit like Problem 135? Well it is a lot like that, and this is where we will get out easy solution from.

Easy solution

In fact we can solve the problem just by adjusting the limit and number of solutions we are looking for in the code for Problem 135. That uses a whole lot of memory when doing it like that,  but it will give us the solution 3.5 seconds. Not exactly what I am usually proud of, but indeed it gives us a correct solution.

The fast solution

We can derive a fast solution for solving this problem. However, deriving it will be a long a long write up. So go get a cup of tea before you read it.

You might want to read Problem 135 again, but recall that we can rewrite the problem as the arithmetic progression it is

 and change the variables such that we get that

where

or isolating d and z we have that

And that will be our point of departure for this little solution. I have a small jump in the reasoning here, since I don’t really know how I came up with the idea of the analysis. Other than I have read the method being used in some other analysis at one point. Anyway, bare with be here when I say that we can represent n as

Such that all the “evenness” is pulled out in the power of 2 and s is the odd fraction of n. Based on this decomposition of n, we can set up different cases. After I solved it I used Roberts writeup to sharpen the arguments and structure of the proof, which is why they are very similar.

Case 1: s is a prime and and r = 0.

It means we have n = 1s, and thus n is a prime. So we only have the divisors 1 and n. So we have two cases u = n, v = 1, which leads to z <= 0, since u <=3  and thus 3v – u is at most 0. Thus we only have the possible solution that u = 1, and v = n. In that case we have that

should be an integer. This happens if and . The second condition is less obvious, but if you go through all the possibilities you will conclude that noting else than 3 will yield an integer solution to the equation for z.

This happens if n is an integer on the form 4k +3 for some integer 4.

In the case for d we have that ((4k + 3) + 1) /4 which will yield the integer k + 1.

For the case of z we have that

And thus if we can conclude that we have a single solution if n is an odd prime which can be written on the form 4k + 3.

Case 2: r = 0, and s is any non-prime odd integer.

Since s is non-prime we can write it as s = qr where q and r are odd integers and we assume that q < r without loss of generality. Then we have three possible arrangement which is (u = 1, and v=qr) or (u=q and v= r) and (u= r and v = q). We can’t have that u=qr, since that would lead to a negative value of z.

Let us write q = 2j+1 and r=2k+1, something we can always do for odd integers.

Let us first consider u = 1, and v=qr

For d we have

Since we have that q < r it follows that j < k, so we can write k = j + a such that we get

This can only have a solution when a is odd since that makes a+1 even and thus divisible by 2. So we can only have a solution when a is odd.

For the z part of u = 1, v = qr we have that

Doing the same substitution as before with k = j + a we get that

Which gives us a solution when a is odd.

However, as we shall see the solution u = q, v = r also have a solution

So if k = j +a we get

Which gives us a solution whenever a is odd.

Furthermore we have that

meaning that we have a solution when a is odd and no solution when we have a solution when a is odd.

So far we have either 2 solutions to the problem if a is odd, and 0 solutions when a is even.

The last case here is that u= r and v = q, in which case d will develop completely similar, and for z we get that

Once again we can only have solutions to this if a is odd.

So the conclusion for this part is that either we have 0 solution or we have too many solutions.

This covers all the odd numbered cases.

Case 3: r = 1 and s is odd

This will never produce a solution since

will give an odd number in the numerator, and thus will not yield an integer. So the conclusion here is that we will never get a solution.

Case 4: r= 2 and s is odd prime

Now we have that .

Now we have the options that (u = 1, v = 4s), (u = 2, v = 2s), (u = 2s, v = 2) (u = 4, v = s) and (u = 4s, v = 1). The latter one will lead us to a negative z, so that is not an option.

The first case (u = 1, v = 4s) does not yield a solution since (1 + 4s) / 4, will never be an integer.

When we have that (u = 2, v = 2s) then we get

Which yields a solution when we write s = 2k +1, since we have that

For

So that is indeed a solution

For the option we have that (u = 2s, v = 2), we get for the same result for d as above.  For z we get that

Which will only give us a solution when s = 1 (meaning that n = 4). In that case we get the exact same solution as the above option since (u = 2, v = 2) in this case. So n=4 so far has only one solution, and the rest of the solutions above where (u=2, v = 2s) have only one solution so far.

The last option (u = 4, v = s) does not have solutions since 4 + s is not divisible by 4 when s is odd.

The conclusion for this case is that n = 4 is a solution and so is every case where n = 4s when s is a prime

Case 5: r = 2, s is an odd non-prime

In this case we can carry out the same argument as case 2, and reach the conclusion that there are multiple valid solutions for each candidate.

Case 6: r = 3, s is odd

Now we have that .

Even if we split s=2k+1, non of the options (u = 1, v = 8s), (u = 2, v = 4s), (u = 4, v = 2s), (u = 8, v = s), (u = 8s, v = 1), (u = 4s, v = 2), (u = 2s, v = 4), (u = s, v = 8) will have solutions. Since the condition for d cannot be fulfilled.

We have that

And you can do the rest. Conclusion is that there are no possible solutions here.

Case 7: r=4, s is a prime

Now we have that n = 16s and .

We have one solution where (u = 4, v = 4s), in that case we have

So we have one solution for this case. All other fails the condition for d, which you can check with the same argument as above. Furthermore we have a solution for s = 1, since we will then have u = 4 and v = 4.

The conclusion for this case is that n = 16 is a solution and so is every case where n = 16s when s is a prime

Case 8: r = 4, s is an odd non-prime

In this case we can carry the same argument as in case 2.

Case 9: r > 4, s is an odd integer

Then for any combination of (u = 2^q, v = 2^r-qs) will yield a solution, and thus there will be more than one solution to this combination.

Wrapping up on the cases

We have solutions whenever we have

1. n = 4p, where p is an odd prime or p = 1
2. n = 16p, where p is an odd prime, or p = 1
3. n = p, where p is prime and p = 4k+3

So now we can write a program that these conditions.

This code can be implemented in c# as

int n = 50000000;
int result = 2; //take care of the cases n= 4, n = 16
int[] primes = Sieve(1, n);

for (int i = 1; i < primes.Length; i++) {
    if (primes[i] < n / 4)
        result++;

    if (primes[i] < n / 16)
        result++;

    if ((primes[i] - 3) % 4 == 0)
        result++;
}

This code runs in 360ms, which is approximately 10 times faster than the other code. And the vast majority of the time goes with finding the primes.

Wrapping up

This concludes Problem 136, and as always you can find the source code here for both solutions.