Talk:Special pythagorean triplet: Difference between revisions

Content added Content deleted

Inline

Revision as of 11:13, 2 September 2021

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 n²+g²=i² and n+g+i=z n<g<i note the following:

the largest value n can take is 332 with g=333 and i=335
the smallest value of i²-g² is when g=(z-1-n)/2 and i=z-g
if i²-g² is greater than n² 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 n²
  given these conditions the solution is n, ((g+i)/2)-n²/2(g+i), ((g+i)/2)+n²/2(g+i) asserting that n<g.
if z-n is odd then:
  2(g+i)+1 must be a factor of n²
  given these conditions the solution is n, ((g+i)/2)-n²/(2(g+i)+1), ((g+i)/2)+n²/(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)

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 n-z is even identify a value g such that n+(g-1)+(g+1)=1000 (eg 3,498,499). The problem may be rewritten as n²=(g+x)²-(g-x)². (g+x)²-(g-x)² is 4xg. Therefore 4g must be a factor of n². To determine x I divide n² 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 n-z is odd similar logic applies identifying g such that n+g+(g+1)=1000 and solving for x: n²=(g+1+x)²-(g-x)²=4gx+2x+2g+1.--Nigel Galloway (talk) 14:06, 1 September 2021 (UTC)

@@ Line 1: / Line 1: @@
-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 n<sup>2</sup>+g<sup>2</sup>=i<sup>2</sup> and n+g+i=1000 n<g<i note the following:
+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 n<sup>2</sup>+g<sup>2</sup>=i<sup>2</sup> and n+g+i=z n<g<i note the following:
  the largest value n can take is 332 with g=333 and i=335
- the smallest value of i<sup>2</sup>-g<sup>2</sup> is when g=(999-n)/2 and i=1000-g
+ the smallest value of i<sup>2</sup>-g<sup>2</sup> is when g=(z-1-n)/2 and i=z-g
  if i<sup>2</sup>-g<sup>2</sup> is greater than n<sup>2</sup> then there can be no solution for this n with a smaller g
- n must be even
+ if z-n is even then:
 (g+i) must be a factor of n<sup>2</sup>
- given these conditions the solution is n, ((g+i)/2)-n<sup>2</sup>/2(g+i), ((g+i)/2)+n<sup>2</sup>/2(g+i) asserting that n<g.
+   given these conditions the solution is n, ((g+i)/2)-n<sup>2</sup>/2(g+i), ((g+i)/2)+n<sup>2</sup>/2(g+i) asserting that n<g.
+ if z-n is odd then:
+(g+i)+1 must be a factor of n<sup>2</sup>
+   given these conditions the solution is n, ((g+i)/2)-n<sup>2</sup>/(2(g+i)+1), ((g+i)/2)+n<sup>2</sup>/(2(g+i)+1) asserting that n<g.
 --[[User:Nigel Galloway|Nigel Galloway]] ([[User talk: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 ? --[[User:Tigerofdarkness|Tigerofdarkness]] ([[User talk:Tigerofdarkness|talk]]) 17:34, 31 August 2021 (UTC)
-:Given the rules above it is necessary to check 166 numbers (even numbers between 2 and 332), the XPL0 solution is checking ~465 I think.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:19, 1 September 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. --[[User:Nigel Galloway|Nigel Galloway]] ([[User talk: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. --[[User:Tigerofdarkness|Tigerofdarkness]] ([[User talk:Tigerofdarkness|talk]]) 18:14, 31 August 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 identify a value g such that n+(g-1)+(g+1)=1000 (eg 3,498,499). The problem may be rewritten as n<sup>2</sup>=(g+x)<sup>2</sup>-(g-x)<sup>2</sup>. (g+x)<sup>2</sup>-(g-x)<sup>2</sup> is 4xg. Therefore 4g must be a factor of n<sup>2</sup>, which implies that n is even. To determine x I divide n<sup>2</sup> 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.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:06, 1 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 n-z is even identify a value g such that n+(g-1)+(g+1)=1000 (eg 3,498,499). The problem may be rewritten as n<sup>2</sup>=(g+x)<sup>2</sup>-(g-x)<sup>2</sup>. (g+x)<sup>2</sup>-(g-x)<sup>2</sup> is 4xg. Therefore 4g must be a factor of n<sup>2</sup>. To determine x I divide n<sup>2</sup> 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 n-z is odd similar logic applies identifying g such that n+g+(g+1)=1000 and solving for x: n<sup>2</sup>=(g+1+x)<sup>2</sup>-(g-x)<sup>2</sup>=4gx+2x+2g+1.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:06, 1 September 2021 (UTC)