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,x2 – y2 – z2 = n, has exactly one solution when n = 20:
132 – 102 – 72 = 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 = 2q, v = 2r-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
- n = 4p, where p is an odd prime or p = 1
- n = 16p, where p is an odd prime, or p = 1
- 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.
As shown in the above article, equation [1] can be rewritten as :
x^2 – y^2 – z^2 = n [1]
[(z+2d)^2 – (z+d)^2 – z^2 = n] [2]
Where d is the difference in the arithmetic progression.
1) Substitution of eqn [1] by eqn [2] implies that x = (z+2d) and y = (z+d).
2) We can see that if z = 3d, then n=0
If z>3d, then n<0
If z0
3) Whether n is positive or negative, then :
n is equal to (z+d) or is a multiple of (z+d)
______
Results observed for n<=100 :
Table 1
Decreasing arithmetic progressions with one solution
x^2 – y^2 – z^2 = n
[(z+2d)^2 – (z+d)^2 – z^2 = n]; (1<=n<=100)
[Re: Project Euler 136: Singleton difference]
http://img40.imageshack.us/img40/7021/pe136tablone.JPG
______
Table 2
Decreasing arithmetic progressions with two solutions
x^2 – y^2 – z^2 = n
[(z+2d)^2 – (z+d)^2 – z^2 = n]; (1<=n<=100)
[Re: Project Euler 136: Singleton difference]
http://img850.imageshack.us/img850/1360/pe136tabltwo.jpg
______
Table 3
Decreasing arithmetic progressions with three solutions
x^2 – y^2 – z^2 = n
[(z+2d)^2 – (z+d)^2 – z^2 = n]; (1<=n<=100)
[Re: Project Euler 136: Singleton difference]
http://img542.imageshack.us/img542/1476/pe136tablthree.jpg
______
Table 4
Decreasing arithmetic progressions with four solutions
x^2 – y^2 – z^2 = n
[(z+2d)^2 – (z+d)^2 – z^2 = n]; (1<=n<=100)
[Re: Project Euler 136: Singleton difference]
http://img13.imageshack.us/img13/6416/pe136tablfour.jpg
______
Results observed for n<=100 :
Our results indicate that there is no solution if we go above four equations.
Number of equations searched (number of equations found) :
One (25)
Two (9)
Three (8)
Four (2)
Five (0)
Six (0)
Seven (0)
Eight (0)
Nine (0)
Ten (0)
______
Sources:
1) Project Euler 136
Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem136.cs
2) Microsoft Visual C# 2010 Express
3) Microsoft Office Excel (2007)
Hi Kristian.
I was trying to solve this one by actually finding solutions. I can only find 22 of them below 100. Could you post a list of solutions below 100, please? I’d really appreciate that.
In my comment above: (February 24, 2013 at 13:10)
1) This link (unavailable):
http://img40.imageshack.us/img40/7021/pe136tablone.JPG
has been replaced by :
http://www.hostingpics.net/viewer.php?id=318374pe136tabone.jpg
___
2) This link (unavailable):
http://img850.imageshack.us/img850/1360/pe136tabltwo.jpg
has been replaced by :
http://www.hostingpics.net/viewer.php?id=932208pe136tabtwo.jpg
___
3) This link (unavailable):
http://img542.imageshack.us/img542/1476/pe136tablthree.jpg
has been replaced by :
http://www.hostingpics.net/viewer.php?id=372837pe136tabthree.jpg
___
4) This link (unavailable):
http://img13.imageshack.us/img13/6416/pe136tablfour.jpg
has been replaced by :
http://www.hostingpics.net/viewer.php?id=566749pe136tabfour.jpg