Talk:Special pythagorean triplet

From Rosetta Code

For those paying "attention to timings" and more importantly for those paying attention to other comments I have made on these Euler tasks about filling RC with solutions worse than I would expect from a schoolboy with a pencil, considering n2+g2=i2 and n+g+i=z n<g<i note the following:

the largest value n can take is (z-2)/3 with g=n+1 and i=n+1
the smallest value of i2-g2 is when g=(z-1-n)/2 and i=z-g
if i2-g2 is greater than n2 then there can be no solution for this n with a smaller g
if z-n is even then:
  2(g+i) must be a factor of n2
  given these conditions the solution is n, ((g+i)/2)-n2/2(g+i), ((g+i)/2)+n2/2(g+i) asserting that n<g.
if z-n is odd then:
  2(g+i)+1 must be a factor of n2
  given these conditions the solution is n, ((g+i)/2)-n2/(2(g+i)+1), ((g+i)/2)+n2/(2(g+i)+1) asserting that n<g.

--Nigel Galloway (talk) 14:11, 31 August 2021 (UTC)

Isn't the task to print out abc? Also, isn't using Euclid's formula (as in the XPL0 solution) going to be faster - less values to try ? --Tigerofdarkness (talk) 17:34, 31 August 2021 (UTC)

Given the rules above it is necessary to check 332, the XPL0 solution is checking ~465 I think. Note that the above runs in O[n] time. --Nigel Galloway (talk) 14:19, 1 September 2021 (UTC)

The task description says there is only one triple with a + b + c = 1000, so it must be a primitive one. --Tigerofdarkness (talk) 18:14, 31 August 2021 (UTC)

...or not - of course that doesn't follow and the triplet isn't a primitive one. Doh! --Tigerofdarkness (talk) 17:23, 6 September 2021 (UTC)

I have added three observations to the list above which remove the requirement for searching which I think may need explanation. For a given n when z-n is even identify a value g such that n+(g-1)+(g+1)=z (eg 200,399,401). The problem may be rewritten as n2=(g+x)2-(g-x)2. (g+x)2-(g-x)2 is 4xg. Therefore 4g must be a factor of n2. To determine x I divide n2 by 4g. Let me work this for n=200. g=400 {(1000-n)/2}. 4g=1600. 40,000/1600=25 so the solution is 200,400-25,400+25. When z-n is odd similar logic applies identifying g such that n+g+(g+1)=z and solving for x: n2=(g+1+x)2-(g-x)2=4gx+2x+2g+1.--Nigel Galloway (talk) 14:06, 1 September 2021 (UTC)

No description

If you are going to pilfer problems from another site you should at least copy the actual problem description over, maybe slightly reworded, and attempt to add some value to it, in this case perhaps (as above) brute force vs. smarter and/or (as per F# entry) solutions for 10^3..10^9. Note that Project Euler is always "find the secret answer" whereas this site is/should be more like "prove the only solution is 200,375,425". --Pete Lomax (talk) 11:42, 2 September 2021 (UTC)