Special pythagorean triplet: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(→{{header|Common Lisp}}: Added Common Lisp version) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (9 intermediate revisions by 8 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
* [[Pythagorean triples]]
<br><br>
=={{header|11l}}==
<syntaxhighlight lang="11l">V PERIMETER = 1000
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))</syntaxhighlight>
{{out}}
<pre>
(200, 375, 425)
</pre>
=={{header|ALGOL 68}}==
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 39 ⟶ 55:
OD;
print( ( whole( count, 0 ), " iterations", newline ) )
END</
{{out}}
<pre>
Line 51 ⟶ 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 67 ⟶ 83:
end for_b ;
endB:
end for_a .</
{{out}}
<pre>
a = 200, b = 375, c = 425
a + b + c = 1000
a * b * c = 31875000
</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SPECIAL_PYTHAGOREAN_TRIPLET.AWK
# converted from FreeBASIC
BEGIN {
main()
exit(0)
}
function main(a,b,c, limit) {
limit = 1000
for (a=1; a<=limit; a++) {
for (b=a+1; b<=limit; b++) {
for (c=b+1; c<=limit; c++) {
if (a*a + b*b == c*c) {
if (a+b+c == limit) {
printf("%d+%d+%d=%d\n",a,b,c,a+b+c)
printf("%d*%d*%d=%d\n",a,b,c,a*b*c)
return
}
}
}
}
}
}
</syntaxhighlight>
{{out}}
<pre>
200+375+425=1000
200*375*425=31875000
</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <cmath>
#include <concepts>
#include <iostream>
#include <numeric>
#include <optional>
#include <tuple>
using namespace std;
optional<tuple<int, int ,int>> FindPerimeterTriplet(int perimeter)
{
unsigned long long perimeterULL = perimeter;
auto max_M = (unsigned long long)sqrt(perimeter/2) + 1;
for(unsigned long long m = 2; m < max_M; ++m)
{
for(unsigned long long n = 1 + m % 2; n < m; n+=2)
{
if(gcd(m,n) != 1)
{
continue;
}
// The formulas below will generate primitive triples if:
// 0 < n < m
// m and n are relatively prime (gcd == 1)
// m + n is odd
auto a = m * m - n * n;
auto b = 2 * m * n;
auto c = m * m + n * n;
auto primitive = a + b + c;
// check all multiples of the primitive at once
auto factor = perimeterULL / primitive;
if(primitive * factor == perimeterULL)
{
// the triplet has been found
if(b<a) swap(a, b);
return tuple{a * factor, b * factor, c * factor};
}
}
}
// the triplet was not found
return nullopt;
}
int main()
{
auto t1 = FindPerimeterTriplet(1000);
if(t1)
{
auto [a, b, c] = *t1;
cout << "[" << a << ", " << b << ", " << c << "]\n";
cout << "a * b * c = " << a * b * c << "\n";
}
else
{
cout << "Perimeter not found\n";
}
}</syntaxhighlight>
{{out}}
<pre>
[200, 375, 425]
a * b * c = 31875000
</pre>
=={{header|Common Lisp}}==
A conventional solution:
<syntaxhighlight lang="lisp">
(defun special-triple (sum)
(loop
for a from 1
do (loop
for b from (1+ a)
for c = (- sum a b)
when (< c b) do (return)
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:
<syntaxhighlight lang="lisp">
(ql:quickload "screamer")
(in-package :screamer-user)
Line 92 ⟶ 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 102 ⟶ 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 471 ⟶ 663:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 585 ⟶ 777:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>Brute force
Line 610 ⟶ 802:
=={{header|Go}}==
{{trans|Wren}}
<
import (
Line 634 ⟶ 826:
}
}
}</
{{out}}
Line 648 ⟶ 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 659 ⟶ 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 680 ⟶ 872:
(a, b, c) = (200, 375, 425)
0.001073 seconds (20 allocations: 752 bytes)
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">sol = First@
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</syntaxhighlight>
{{out}}<pre>
a 200
b 375
c 425
Product: 31875000
</pre>
Line 685 ⟶ 890:
My solution from Project Euler:
<
from math import floor, sqrt
Line 704 ⟶ 909:
echo fmt"a: {(s - int(r)) div 2}"
echo fmt"b: {(s + int(r)) div 2}"
echo fmt"c: {c}"</
{{out}}
Line 713 ⟶ 918:
=={{header|Perl}}==
<
use warnings;
Line 723 ⟶ 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 734 ⟶ 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 748 ⟶ 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 757 ⟶ 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 772 ⟶ 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 782 ⟶ 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 910 ⟶ 1,115:
END;
EOF</
{{out}}
<pre>
Line 925 ⟶ 1,130:
=={{header|Raku}}==
<syntaxhighlight lang="raku"
my $a2 = $a²;
for $a + 1 .. 999 -> $b {
Line 933 ⟶ 1,138:
and exit if $a2 + $b² == $c²
}
}</
{{out}}
<pre>200² + 375² = 425²
Line 944 ⟶ 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 969 ⟶ 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 978 ⟶ 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,081 ⟶ 1,286:
? "Elapsed time = " + et / tf + " ms" + nl
see "done..."</
{{out}}
<pre>working...
Line 1,109 ⟶ 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,127 ⟶ 1,363:
}
a = a + 1
}</
{{out}}
Line 1,137 ⟶ 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,149 ⟶ 1,385:
b = b + 1
}
}</
=={{header|XPL0}}==
<
for N:= 1 to sqrt(1000) do
for M:= N+1 to sqrt(1000) do
Line 1,160 ⟶ 1,396:
if A+B+C = 1000 then
IntOut(0, A*B*C);
]</
{{out}}
| |||