Special pythagorean triplet: Difference between revisions
Content added Content deleted
(Added simple description) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 10: | Line 10: | ||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
=={{header|11l}}== |
||
< |
<syntaxhighlight lang="11l">V PERIMETER = 1000 |
||
L(a) 1 .. PERIMETER |
L(a) 1 .. PERIMETER |
||
L(b) a + 1 .. PERIMETER |
L(b) a + 1 .. PERIMETER |
||
V c = PERIMETER - a - b |
V c = PERIMETER - a - b |
||
I a * a + b * b == c * c |
I a * a + b * b == c * c |
||
print((a, b, c))</ |
print((a, b, c))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 25: | Line 25: | ||
Uses Euclid's formula, as in the XPL0 sample but also uses the fact that M and N must be factors of half the triangle's perimeter to reduce the number of candidate M's to check. A loop is not needed to find N once a candidate M has been found. |
Uses Euclid's formula, as in the XPL0 sample but also uses the fact that M and N must be factors of half the triangle's perimeter to reduce the number of candidate M's to check. A loop is not needed to find N once a candidate M has been found. |
||
<br>Does not stop after the solution has been found, thus verifying there is only one solution. |
<br>Does not stop after the solution has been found, thus verifying there is only one solution. |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find the product of the of the Pythagorian triplet a, b, c where: # |
||
# a + b + c = 1000, a2 + b2 = c2, a < b < c # |
# a + b + c = 1000, a2 + b2 = c2, a < b < c # |
||
INT perimeter = 1000; |
INT perimeter = 1000; |
||
Line 55: | Line 55: | ||
OD; |
OD; |
||
print( ( whole( count, 0 ), " iterations", newline ) ) |
print( ( whole( count, 0 ), " iterations", newline ) ) |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 67: | Line 67: | ||
{{trans|Wren}} |
{{trans|Wren}} |
||
...but doesn't stop on the first solution (thus verifying there is only one). |
...but doesn't stop on the first solution (thus verifying there is only one). |
||
< |
<syntaxhighlight lang="algolw">% find the Pythagorian triplet a, b, c where a + b + c = 1000 % |
||
for a := 1 until 1000 div 3 do begin |
for a := 1 until 1000 div 3 do begin |
||
integer a2, b; |
integer a2, b; |
||
Line 83: | Line 83: | ||
end for_b ; |
end for_b ; |
||
endB: |
endB: |
||
end for_a .</ |
end for_a .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 91: | Line 91: | ||
</pre> |
</pre> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f SPECIAL_PYTHAGOREAN_TRIPLET.AWK |
# syntax: GAWK -f SPECIAL_PYTHAGOREAN_TRIPLET.AWK |
||
# converted from FreeBASIC |
# converted from FreeBASIC |
||
Line 114: | Line 114: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 122: | Line 122: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">#include <cmath> |
||
#include <concepts> |
#include <concepts> |
||
#include <iostream> |
#include <iostream> |
||
Line 182: | Line 182: | ||
cout << "Perimeter not found\n"; |
cout << "Perimeter not found\n"; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 193: | Line 193: | ||
A conventional solution: |
A conventional solution: |
||
< |
<syntaxhighlight lang="lisp"> |
||
(defun special-triple (sum) |
(defun special-triple (sum) |
||
(loop |
(loop |
||
Line 203: | Line 203: | ||
when (= (* c c) (+ (* a a) (* b b))) |
when (= (* c c) (+ (* a a) (* b b))) |
||
do (return-from conventional-triple-search (list a b c))))) |
do (return-from conventional-triple-search (list a b c))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
This version utilizes SCREAMER which provides constraint solving: |
This version utilizes SCREAMER which provides constraint solving: |
||
< |
<syntaxhighlight lang="lisp"> |
||
(ql:quickload "screamer") |
(ql:quickload "screamer") |
||
(in-package :screamer-user) |
(in-package :screamer-user) |
||
Line 221: | Line 221: | ||
(print (one-value (special-pythagorean-triple 1000))) |
(print (one-value (special-pythagorean-triple 1000))) |
||
;; => (200 375 425 31875000) |
;; => (200 375 425 31875000) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
Here I present a solution based on the ideas on the discussion page. It finds all Pythagorean triplets whose elements sum to a given value. It runs in O[n] time. Normally I would exclude triplets with a common factor but for this demonstration I prefer to leave them. |
Here I present a solution based on the ideas on the discussion page. It finds all Pythagorean triplets whose elements sum to a given value. It runs in O[n] time. Normally I would exclude triplets with a common factor but for this demonstration I prefer to leave them. |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Special pythagorean triplet. Nigel Galloway: August 31st., 2021 |
// Special pythagorean triplet. Nigel Galloway: August 31st., 2021 |
||
let fG n g=let i=(n-g)/2L in match (n+g)%2L with 0L->if (g*g)%(4L*i)=0L then Some(g,i-(g*g)/(4L*i),i+(g*g)/(4L*i)) else None |
let fG n g=let i=(n-g)/2L in match (n+g)%2L with 0L->if (g*g)%(4L*i)=0L then Some(g,i-(g*g)/(4L*i),i+(g*g)/(4L*i)) else None |
||
Line 231: | Line 231: | ||
let E9 n=let fN=fG n in seq{1L..(n-2L)/3L}|>Seq.choose fN|>Seq.iter(fun(n,g,l)->printfn $"%d{n*n}(%d{n})+%d{g*g}(%d{g})=%d{l*l}(%d{l})") |
let E9 n=let fN=fG n in seq{1L..(n-2L)/3L}|>Seq.choose fN|>Seq.iter(fun(n,g,l)->printfn $"%d{n*n}(%d{n})+%d{g*g}(%d{g})=%d{l*l}(%d{l})") |
||
[1L..260L]|>List.iter(fun n->printfn "Sum = %d" n; E9 n) |
[1L..260L]|>List.iter(fun n->printfn "Sum = %d" n; E9 n) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 600: | Line 600: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">' version 06-10-2021 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 714: | Line 714: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Brute force |
<pre>Brute force |
||
Line 739: | Line 739: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 763: | Line 763: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 777: | Line 777: | ||
{{works with|jq}} |
{{works with|jq}} |
||
'''Works with gojq, the Go implementation of jq''' |
'''Works with gojq, the Go implementation of jq''' |
||
< |
<syntaxhighlight lang="jq">range(1;1000) as $a |
||
| range($a+1;1000) as $b |
| range($a+1;1000) as $b |
||
| (1000 - $a - $b) as $c |
| (1000 - $a - $b) as $c |
||
| select($a*$a + $b*$b == $c*$c) |
| select($a*$a + $b*$b == $c*$c) |
||
| {$a, $b, $c, product: ($a*$b*$c)}</ |
| {$a, $b, $c, product: ($a*$b*$c)}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 788: | Line 788: | ||
Or, with a tiny bit of thought: |
Or, with a tiny bit of thought: |
||
< |
<syntaxhighlight lang="jq">range(1;1000/3) as $a |
||
| range($a+1;1000/2) as $b |
| range($a+1;1000/2) as $b |
||
| (1000 - $a - $b) as $c |
| (1000 - $a - $b) as $c |
||
| select($a*$a + $b*$b == $c*$c) |
| select($a*$a + $b*$b == $c*$c) |
||
| {$a, $b, $c, product: ($a*$b*$c)}}</ |
| {$a, $b, $c, product: ($a*$b*$c)}}</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Line 811: | Line 811: | ||
</pre> |
</pre> |
||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">sol = First@ |
||
FindInstance[ |
FindInstance[ |
||
a + b + c == 1000 && a > 0 && b > 0 && c > 0 && |
a + b + c == 1000 && a > 0 && b > 0 && c > 0 && |
||
a^2 + b^2 == c^2, {a, b, c}, Integers]; |
a^2 + b^2 == c^2, {a, b, c}, Integers]; |
||
Join[List @@@ sol, {{"Product:" , a b c /. sol}}] // TableForm</ |
Join[List @@@ sol, {{"Product:" , a b c /. sol}}] // TableForm</syntaxhighlight> |
||
{{out}}<pre> |
{{out}}<pre> |
||
Line 827: | Line 827: | ||
My solution from Project Euler: |
My solution from Project Euler: |
||
< |
<syntaxhighlight lang="nim">import strformat |
||
from math import floor, sqrt |
from math import floor, sqrt |
||
Line 846: | Line 846: | ||
echo fmt"a: {(s - int(r)) div 2}" |
echo fmt"a: {(s - int(r)) div 2}" |
||
echo fmt"b: {(s + int(r)) div 2}" |
echo fmt"b: {(s + int(r)) div 2}" |
||
echo fmt"c: {c}"</ |
echo fmt"c: {c}"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 855: | Line 855: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
Line 865: | Line 865: | ||
print "$a² + $b² = $c²\n$a + $b + $c = 1000\n" and last if $a2 + $b**2 == $c**2 |
print "$a² + $b² = $c²\n$a + $b + $c = 1000\n" and last if $a2 + $b**2 == $c**2 |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>200² + 375² = 425² |
<pre>200² + 375² = 425² |
||
Line 876: | Line 876: | ||
=== brute force (83000 iterations) === |
=== brute force (83000 iterations) === |
||
Not that this is in any way slow (0.1s, or 0s with the displays removed), and not that it deliberately avoids using sensible loop limits, you understand. |
Not that this is in any way slow (0.1s, or 0s with the displays removed), and not that it deliberately avoids using sensible loop limits, you understand. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">constant</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1000</span> |
<span style="color: #008080;">constant</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1000</span> |
||
Line 890: | Line 890: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d iterations\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d iterations\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 899: | Line 899: | ||
=== smarter (166 iterations) === |
=== smarter (166 iterations) === |
||
It would of course be 100 iterations if we quit once found (whereas the above would be 69775). |
It would of course be 100 iterations if we quit once found (whereas the above would be 69775). |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">constant</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1000</span> |
<span style="color: #008080;">constant</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1000</span> |
||
Line 914: | Line 914: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d iterations\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d iterations\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 924: | Line 924: | ||
Based on the XPL0 solution. |
Based on the XPL0 solution. |
||
<br>As the original 8080 PL/M compiler only has unsigned 8 and 16 bit integer arithmetic, the PL/M [https://www.rosettacode.org/wiki/Long_multiplication long multiplication routines] and also a square root routine based that in the PL/M sample for the [https://www.rosettacode.org/wiki/Frobenius_numbers Frobenius Numbers task] are used - which makes this somewhat longer than it would otherwose be... |
<br>As the original 8080 PL/M compiler only has unsigned 8 and 16 bit integer arithmetic, the PL/M [https://www.rosettacode.org/wiki/Long_multiplication long multiplication routines] and also a square root routine based that in the PL/M sample for the [https://www.rosettacode.org/wiki/Frobenius_numbers Frobenius Numbers task] are used - which makes this somewhat longer than it would otherwose be... |
||
< |
<syntaxhighlight lang="pli">100H: /* FIND THE PYTHAGOREAN TRIPLET A, B, C WHERE A + B + C = 1000 */ |
||
/* CP/M BDOS SYSTEM CALL */ |
/* CP/M BDOS SYSTEM CALL */ |
||
Line 1,052: | Line 1,052: | ||
END; |
END; |
||
EOF</ |
EOF</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,067: | Line 1,067: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>hyper for 1..998 -> $a { |
||
my $a2 = $a²; |
my $a2 = $a²; |
||
for $a + 1 .. 999 -> $b { |
for $a + 1 .. 999 -> $b { |
||
Line 1,075: | Line 1,075: | ||
and exit if $a2 + $b² == $c² |
and exit if $a2 + $b² == $c² |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>200² + 375² = 425² |
<pre>200² + 375² = 425² |
||
Line 1,086: | Line 1,086: | ||
Also, there were multiple shortcuts to limit an otherwise exhaustive search; Once a sum or a square was too big, |
Also, there were multiple shortcuts to limit an otherwise exhaustive search; Once a sum or a square was too big, |
||
<br>the next integer was used (for the previous DO loop). |
<br>the next integer was used (for the previous DO loop). |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm computes integers A, B, C that solve: 0<A<B<C; A+B+C = 1000; A^2+B^2 = C^2 */ |
||
parse arg sum hi n . /*obtain optional argument from the CL.*/ |
parse arg sum hi n . /*obtain optional argument from the CL.*/ |
||
if sum=='' | sum=="," then sum= 1000 /*Not specified? Then use the default.*/ |
if sum=='' | sum=="," then sum= 1000 /*Not specified? Then use the default.*/ |
||
Line 1,111: | Line 1,111: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
s: if arg(1)==1 then return arg(3); return word(arg(2) 's', 1) /*simple pluralizer*/ |
s: if arg(1)==1 then return arg(3); return word(arg(2) 's', 1) /*simple pluralizer*/ |
||
show: #= #+1; say pad 'a=' a pad "b=" b pad 'c=' c; if #>=n then signal done; return</ |
show: #= #+1; say pad 'a=' a pad "b=" b pad 'c=' c; if #>=n then signal done; return</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 1,120: | Line 1,120: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
Various algorithms presented, some are quite fast. Timings are from Tio.run. On the desktop of a core i7-7700 @ 3.60Ghz, it goes about 6.5 times faster. |
Various algorithms presented, some are quite fast. Timings are from Tio.run. On the desktop of a core i7-7700 @ 3.60Ghz, it goes about 6.5 times faster. |
||
< |
<syntaxhighlight lang="ring">tf = 1000 # time factor adjustment for different Ring versions |
||
? "working..." |
? "working..." |
||
Line 1,223: | Line 1,223: | ||
? "Elapsed time = " + et / tf + " ms" + nl |
? "Elapsed time = " + et / tf + " ms" + nl |
||
see "done..."</ |
see "done..."</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>working... |
<pre>working... |
||
Line 1,254: | Line 1,254: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
Very simple approach, only takes 0.013 seconds even in Wren. |
Very simple approach, only takes 0.013 seconds even in Wren. |
||
< |
<syntaxhighlight lang="ecmascript">var a = 3 |
||
while (true) { |
while (true) { |
||
var b = a + 1 |
var b = a + 1 |
||
Line 1,269: | Line 1,269: | ||
} |
} |
||
a = a + 1 |
a = a + 1 |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,279: | Line 1,279: | ||
<br> |
<br> |
||
Incidentally, even though we are '''told''' there is only one solution, it is almost as quick to verify this by observing that, since a < b < c, the maximum value of a must be such that 3a + 2 = 1000 or max(a) = 332. The following version ran in 0.015 seconds and, of course, produced the same output: |
Incidentally, even though we are '''told''' there is only one solution, it is almost as quick to verify this by observing that, since a < b < c, the maximum value of a must be such that 3a + 2 = 1000 or max(a) = 332. The following version ran in 0.015 seconds and, of course, produced the same output: |
||
< |
<syntaxhighlight lang="ecmascript">for (a in 3..332) { |
||
var b = a + 1 |
var b = a + 1 |
||
while (true) { |
while (true) { |
||
Line 1,291: | Line 1,291: | ||
b = b + 1 |
b = b + 1 |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">int N, M, A, B, C; |
||
for N:= 1 to sqrt(1000) do |
for N:= 1 to sqrt(1000) do |
||
for M:= N+1 to sqrt(1000) do |
for M:= N+1 to sqrt(1000) do |
||
Line 1,302: | Line 1,302: | ||
if A+B+C = 1000 then |
if A+B+C = 1000 then |
||
IntOut(0, A*B*C); |
IntOut(0, A*B*C); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |