5

Good morning, I'm new here and I bring a small problem. I'm having trouble develop efficient an algorithm for the following problem: I need to find combinations of three positive numbers x, y and z so that x + y, x - y, y + z, y - z, x + z and x - z are perfect squares. The issue is to develop an algorithm that finds all combinations of x, y and z between 1 and 2,000,000.

Currently I use a for within a for that certainly will not end before I have my grandchildren.

user2156850
  • 51
  • 1
  • 5
  • accelerate grandchildren acquisition then, could be a fun way to solve this ;) +1 for the good question – kostja Mar 11 '13 at 13:04
  • 3
    Is the constraint that `1 – High Performance Mark Mar 11 '13 at 13:28
  • 1
    It may help for some cases to know that [every square is the sum of two consecutive triangular numbers](http://www.jstor.org/discover/10.2307/3621134?uid=3739728&uid=2&uid=4&uid=3739256&sid=21101806678781) (though that of course does not mean that only triangular numbers sum to squares). – Waleed Khan Mar 11 '13 at 13:35
  • It is necessary that the result of the expression x + y, x - y, y + z, y - z, x and x + z - z are perfect squares. Such that x, y and z are between 1 and 2000,000. Whereby the algorithm appears to be realized that the requirement X> Y> Z since according to the above expressions xy negative if Y would be higher as XZ. – user2156850 Mar 11 '13 at 13:50

2 Answers2

4

The basic idea to begin with a substitution, like:

 u = x + y
 v = x - y
 w = y + z

Then x + y, x - y, y + z, y - z, x + z and x - z becomes 

 u, v, w, u - v - w, v + w, u - w   [all have to be squares]

Then with another substitution, u = a², v = b², w = c², you get:

 a², b², c², a² - b² - c², b² + c², a² - c²    [all have to be squares]

now you can enumerate all a, b, c-s which may already be fast enough.

Further ideas could be to first enumerate all b², c², b²+c² using Pythagorean triples (by substituting it to m and n, enumerating all coprime (m,n) and then using Euclid formula) and then find for given (b,c) the as in a similar way (e.g. change a² - c² = x² to a² = x² + c² and use the triples again).

BeniBela
  • 16,412
  • 4
  • 45
  • 52
  • So I had the idea to start looking for the ultimate X and then Y to find the answer expressions X + Y is a perfect square (regardless of whether the result is in range or if it is different from other results), X - Y is perfect square. Having "X" and "Y" looking for "Z", and other expressions realize until you find a valid combination and store or print. BeniBela "The basic idea to begin with a substitution, like: u = x + y v = x - y w = y + z" seems a good idea, I'll try work with that. thank you – user2156850 Mar 11 '13 at 13:56
0

Extending BeniBela's answer,

x + y = (x - z) + (y + z)
x + y = (x + z) + (y - z)

So, triplets are valid only if the hypotenuse can be represented in two different forms. Further filtering can be done by observing that (x - z) and (x + z) also form the hypotenuse of a Pythagorean triplet.

Community
  • 1
  • 1
Rozuur
  • 4,115
  • 25
  • 31