Special pythagorean triplet: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(C++ entry) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (4 intermediate revisions by 4 users not shown) | |||
Line 1:
{{Draft task}}
;Task:
Find the Pythagorean triplet for which a + b + c = 1000 and print the product of a, b, and c. The problem was taken from [https://projecteuler.net/problem=9 Project Euler problem 9]
<br>
;Related task
Line 7 ⟶ 10:
<br><br>
=={{header|11l}}==
<
L(a) 1 .. PERIMETER
L(b) a + 1 .. PERIMETER
V c = PERIMETER - a - b
I a * a + b * b == c * c
print((a, b, c))</
{{out}}
Line 22 ⟶ 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.
<br>Does not stop after the solution has been found, thus verifying there is only one solution.
<
# a + b + c = 1000, a2 + b2 = c2, a < b < c #
INT perimeter = 1000;
Line 52 ⟶ 55:
OD;
print( ( whole( count, 0 ), " iterations", newline ) )
END</
{{out}}
<pre>
Line 64 ⟶ 67:
{{trans|Wren}}
...but doesn't stop on the first solution (thus verifying there is only one).
<
for a := 1 until 1000 div 3 do begin
integer a2, b;
Line 80 ⟶ 83:
end for_b ;
endB:
end for_a .</
{{out}}
<pre>
Line 88 ⟶ 91:
</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SPECIAL_PYTHAGOREAN_TRIPLET.AWK
# converted from FreeBASIC
Line 111 ⟶ 114:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 119 ⟶ 122:
=={{header|C++}}==
<
#include <concepts>
#include <iostream>
Line 179 ⟶ 182:
cout << "Perimeter not found\n";
}
}</
{{out}}
<pre>
Line 190 ⟶ 193:
A conventional solution:
<
(defun special-triple (sum)
(loop
Line 200 ⟶ 203:
when (= (* c c) (+ (* a a) (* b b)))
do (return-from conventional-triple-search (list a b c)))))
</syntaxhighlight>
This version utilizes SCREAMER which provides constraint solving:
<
(ql:quickload "screamer")
(in-package :screamer-user)
Line 218 ⟶ 221:
(print (one-value (special-pythagorean-triple 1000)))
;; => (200 375 425 31875000)
</syntaxhighlight>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
{Define structure to contain triple}
type TTriple = record
A, B, C: integer;
end;
{Make dynamic array of triples}
type TTripleArray = array of TTriple;
procedure PythagorianTriples(Limit: integer; var TA: TTripleArray);
{Find pythagorian Triple up to limit - Return result in list TA}
var Limit2: integer;
var I,J,K: integer;
begin
SetLength(TA,0);
Limit2:=Limit div 2;
for I:=1 to Limit2 do
for J:=I to Limit2 do
for K:=J to Limit do
if ((I+J+K)<Limit) and ((I*I+J*J)=(K*K)) then
begin
SetLength(TA,Length(TA)+1);
TA[High(TA)].A:=I;
TA[High(TA)].B:=J;
TA[High(TA)].C:=K;
end;
end;
procedure ShowPythagoreanTriplet(Memo: TMemo);
var TA: TTripleArray;
var I, Sum, Prod: integer;
begin
{Find triples up to 1100}
PythagorianTriples(1100,TA);
for I:=0 to High(TA) do
begin
{Look for sum of 1000}
Sum:=TA[I].A + TA[I].B + TA[I].C;
if Sum<>1000 then continue;
{Display result}
Prod:=TA[I].A * TA[I].B * TA[I].C;
Memo.Lines.Add(Format('%d + %d + %d = %10.0n',[TA[I].A, TA[I].B, TA[I].C, Sum+0.0]));
Memo.Lines.Add(Format('%d * %d * %d = %10.0n',[TA[I].A, TA[I].B, TA[I].C, Prod+0.0]));
end;
end;
</syntaxhighlight>
{{out}}
<pre>
200 + 375 + 425 = 1,000
200 * 375 * 425 = 31,875,000
Elapsed Time: 210.001 ms.
</pre>
=={{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.
<
// 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
Line 228 ⟶ 294:
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)
</syntaxhighlight>
{{out}}
<pre>
Line 597 ⟶ 663:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 711 ⟶ 777:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>Brute force
Line 736 ⟶ 802:
=={{header|Go}}==
{{trans|Wren}}
<
import (
Line 760 ⟶ 826:
}
}
}</
{{out}}
Line 774 ⟶ 840:
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<
| range($a+1;1000) as $b
| (1000 - $a - $b) as $c
| select($a*$a + $b*$b == $c*$c)
| {$a, $b, $c, product: ($a*$b*$c)}</
{{out}}
<pre>
Line 785 ⟶ 851:
Or, with a tiny bit of thought:
<
| range($a+1;1000/2) as $b
| (1000 - $a - $b) as $c
| select($a*$a + $b*$b == $c*$c)
| {$a, $b, $c, product: ($a*$b*$c)}}</
=={{header|Julia}}==
Line 808 ⟶ 874:
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
FindInstance[
a + b + c == 1000 && a > 0 && b > 0 && c > 0 &&
a^2 + b^2 == c^2, {a, b, c}, Integers];
Join[List @@@ sol, {{"Product:" , a b c /. sol}}] // TableForm</
{{out}}<pre>
Line 824 ⟶ 890:
My solution from Project Euler:
<
from math import floor, sqrt
Line 843 ⟶ 909:
echo fmt"a: {(s - int(r)) div 2}"
echo fmt"b: {(s + int(r)) div 2}"
echo fmt"c: {c}"</
{{out}}
Line 852 ⟶ 918:
=={{header|Perl}}==
<
use warnings;
Line 862 ⟶ 928:
print "$a² + $b² = $c²\n$a + $b + $c = 1000\n" and last if $a2 + $b**2 == $c**2
}
}</
{{out}}
<pre>200² + 375² = 425²
Line 873 ⟶ 939:
=== 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.
<!--<
<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>
Line 887 ⟶ 953:
<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>
<!--</
{{out}}
<pre>
Line 896 ⟶ 962:
=== smarter (166 iterations) ===
It would of course be 100 iterations if we quit once found (whereas the above would be 69775).
<!--<
<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>
Line 911 ⟶ 977:
<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>
<!--</
{{out}}
<pre>
Line 921 ⟶ 987:
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...
<
/* CP/M BDOS SYSTEM CALL */
Line 1,049 ⟶ 1,115:
END;
EOF</
{{out}}
<pre>
Line 1,064 ⟶ 1,130:
=={{header|Raku}}==
<syntaxhighlight lang="raku"
my $a2 = $a²;
for $a + 1 .. 999 -> $b {
Line 1,072 ⟶ 1,138:
and exit if $a2 + $b² == $c²
}
}</
{{out}}
<pre>200² + 375² = 425²
Line 1,083 ⟶ 1,149:
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).
<
parse arg sum hi n . /*obtain optional argument from the CL.*/
if sum=='' | sum=="," then sum= 1000 /*Not specified? Then use the default.*/
Line 1,108 ⟶ 1,174:
/*──────────────────────────────────────────────────────────────────────────────────────*/
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</
{{out|output|text= when using the default inputs:}}
<pre>
Line 1,117 ⟶ 1,183:
=={{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.
<
? "working..."
Line 1,220 ⟶ 1,286:
? "Elapsed time = " + et / tf + " ms" + nl
see "done..."</
{{out}}
<pre>working...
Line 1,248 ⟶ 1,314:
done...</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
use std::collections::HashSet ;
fn main() {
let mut numbers : HashSet<u32> = HashSet::new( ) ;
for a in 1u32..=1000u32 {
for b in 1u32..=1000u32 {
for c in 1u32..=1000u32 {
if a + b + c == 1000 && a * a + b * b == c * c {
numbers.insert( a ) ;
numbers.insert( b ) ;
numbers.insert( c ) ;
}
}
}
}
let mut product : u32 = 1 ;
for k in &numbers {
product *= *k ;
}
println!("{:?}" , numbers ) ;
println!("The product of {:?} is {}" , numbers , product) ;
}
</syntaxhighlight>
{{out}}
<pre>
{375, 425, 200}
The product of {375, 425, 200} is 31875000
</pre>
=={{header|Wren}}==
Very simple approach, only takes 0.013 seconds even in Wren.
<
while (true) {
var b = a + 1
Line 1,266 ⟶ 1,363:
}
a = a + 1
}</
{{out}}
Line 1,276 ⟶ 1,373:
<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:
<
var b = a + 1
while (true) {
Line 1,288 ⟶ 1,385:
b = b + 1
}
}</
=={{header|XPL0}}==
<
for N:= 1 to sqrt(1000) do
for M:= N+1 to sqrt(1000) do
Line 1,299 ⟶ 1,396:
if A+B+C = 1000 then
IntOut(0, A*B*C);
]</
{{out}}
| |||