Rosetta Code

Pythagorean triples: Difference between revisions

Page Discussion

Pythagorean triples (view source)

Revision as of 11:35, 28 August 2022

3,463 bytes added ,  1 year ago
m
syntax highlighting fixup automation
m (syntax highlighting fixup automation)
Line 28:
{{trans|D}}
 
<langsyntaxhighlight lang="11l">Int64 nTriples, nPrimitives, limit
 
F countTriples(Int64 =x, =y, =z)
Line 57:
nTriples = nPrimitives = 0
countTriples(3, 4, 5)
print(‘Up to #11: #11 triples, #9 primitives.’.format(limit, nTriples, nPrimitives))</langsyntaxhighlight>
 
{{out}}
Line 73:
=={{header|360 Assembly}}==
{{trans|Perl}}
<langsyntaxhighlight lang="360asm">* Pythagorean triples - 12/06/2018
PYTHTRI CSECT
USING PYTHTRI,R13 base register
Line 199:
ISQRTSA DS 8A context store
YREGS
END PYTHTRI</langsyntaxhighlight>
{{out}}
<pre>
Line 211:
 
=={{header|Action!}}==
<langsyntaxhighlight Actionlang="action!">DEFINE PTR="CARD"
DEFINE ENTRY_SIZE="3"
TYPE TRIPLE=[BYTE a,b,c]
Line 318:
PrintF("%E%E%E%B of them are primitive:%E%E",res2.count)
PrintTriples(res2)
RETURN</langsyntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Pythagorean_triples.png Screenshot from Atari 8-bit computer]
Line 336:
Translation of efficient method from C, see [[wp:Pythagorean_triple#Parent.2Fchild_relationships|the WP article]]. Compiles on gnat/gcc.
 
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO;
 
procedure Pythagorean_Triples is
Line 368:
Large_Natural'Image(P_Cnt) & " Primitives");
end loop;
end Pythagorean_Triples;</langsyntaxhighlight>
 
Output:
Line 386:
Translation of BBC BASIC Program
 
<langsyntaxhighlight ANSIlang="ansi Standardstandard BASICbasic">100 DECLARE EXTERNAL SUB tri
110 !
120 PUBLIC NUMERIC U0(3,3), U1(3,3), U2(3,3), all, prim
Line 428:
500 NEXT i
510 LET SUM = temp
520 END FUNCTION</langsyntaxhighlight>
 
=={{header|Arturo}}==
 
<langsyntaxhighlight lang="rebol">triples: new []
loop 1..50 'x [
loop 1..50 'y [
Line 452:
print ""
print [size primitive "of them are primitive:"]
print primitive</langsyntaxhighlight>
 
{{out}}
Line 463:
 
=={{header|APL}}==
<syntaxhighlight lang="apl">
<lang APL>
⍝ Determine whether given list of integers has GCD = 1
primitive←∧/1=2∨/⊢
Line 495:
perimeter_rule←{maxperimeter≥+/⍵}
res←perimeter_rule¨filter add_c¨sos_is_sq filter a_b_pairs
∇</langsyntaxhighlight>
{{out}}
<pre>
Line 507:
 
=={{header|AutoHotkey}}==
<langsyntaxhighlight lang="autohotkey">#NoEnv
SetBatchLines, -1
#SingleInstance, Force
Line 536:
 
Loop, 8
Msgbox % 10**A_Index ": " count_triples(10**A_Index)</langsyntaxhighlight>
 
{{out}}
Line 549:
 
=={{header|AWK}}==
<syntaxhighlight lang="awk">
<lang AWK>
# syntax: GAWK -f PYTHAGOREAN_TRIPLES.AWK
# converted from Go
Line 573:
}
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 590:
=={{header|BBC BASIC}}==
The built-in array arithmetic is very well suited to this task!
<langsyntaxhighlight lang="bbcbasic"> DIM U0%(2,2), U1%(2,2), U2%(2,2), seed%(2)
U0%() = 1, -2, 2, 2, -1, 2, 2, -2, 3
U1%() = 1, 2, 2, 2, 1, 2, 2, 2, 3
Line 616:
t%() = U2%() . i%()
PROCtri(t%(), mp%, all%, prim%)
ENDPROC</langsyntaxhighlight>
'''Output:'''
<pre>
Line 631:
=={{header|Bracmat}}==
{{trans|C}}
<langsyntaxhighlight lang="bracmat">(pythagoreanTriples=
total prim max-peri U
. (.(1,-2,2) (2,-1,2) (2,-2,3))
Line 684:
pythagoreanTriples$;
</syntaxhighlight>
</lang>
 
Output (under Linux):
Line 699:
With very few changes we can get rid of the stack exhausting recursion. Instead of calling <code>new-tri</code> recursively, be push the triples to test onto a stack and return to the <code>Main</code> function. In the innermost loop we pop a triple from the stack and call <code>new-tri</code>. The memory overhead is only a few megabytes for a max perimeter of 100,000,000. On my Windows XP box the whole computation takes at least 15 minutes! Given enough time (and memory), the program can compute results for larger perimeters.
 
<langsyntaxhighlight lang="bracmat">(pythagoreanTriples=
total prim max-peri U stack
. (.(1,-2,2) (2,-1,2) (2,-2,3))
Line 752:
);
 
pythagoreanTriples$;</langsyntaxhighlight>
 
=={{header|C}}==
 
Sample implemention; naive method, patentedly won't scale to larger numbers, despite the attempt to optimize it. Calculating up to 10000 is already a test of patience.
<langsyntaxhighlight Clang="c">#include <stdio.h>
#include <stdlib.h>
Line 802:
 
return 0;
}</langsyntaxhighlight>output:<syntaxhighlight lang="text">Up to 100, there are 17 triples, of which 7 are primitive</langsyntaxhighlight>
Efficient method, generating primitive triples only as described in [[wp:Pythagorean_triple#Parent.2Fchild_relationships|the same WP article]]:<langsyntaxhighlight Clang="c">#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
Line 850:
}
return 0;
}</langsyntaxhighlight>Output<syntaxhighlight lang="text">Up to 10: 0 triples, 0 primitives.
Up to 100: 17 triples, 7 primitives.
Up to 1000: 325 triples, 70 primitives.
Line 857:
Up to 1000000: 808950 triples, 70229 primitives.
Up to 10000000: 9706567 triples, 702309 primitives.
Up to 100000000: 113236940 triples, 7023027 primitives.</langsyntaxhighlight>
 
Same as above, but with loop unwound and third recursion eliminated:
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
Line 910:
}
return 0;
}</langsyntaxhighlight>
 
=={{header|C++}}==
 
<langsyntaxhighlight lang="cpp">#include <cmath>
#include <iostream>
#include <numeric>
Line 968:
}
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 986:
Based on Ada example, which is a translation of efficient method from C, see [[wp:Pythagorean_triple#Parent.2Fchild_relationships|the WP article]].
 
<langsyntaxhighlight Clang="c sharp">using System;
 
namespace RosettaCode.CSharp
Line 1,025:
}
}
}</langsyntaxhighlight>
 
Output:
Line 1,042:
for each pair ''(m,n)'' such that ''m>n>0'', ''m'' and ''n'' coprime and of opposite polarity (even/odd),
there is a primitive Pythagorean triple. It can be proven that the converse is true as well.
<langsyntaxhighlight lang="clojure">(defn gcd [a b] (if (zero? b) a (recur b (mod a b))))
(defn pyth [peri]
Line 1,058:
(reduce (fn [[total prims] t] [(inc total), (if (first t) (inc prims) prims)])
[0 0]
ts))</langsyntaxhighlight>
To handle really large perimeters, we can dispense with actually generating the triples and just calculate the counts:
<langsyntaxhighlight lang="clojure">(defn pyth-count [peri]
(reduce (fn [[total prims] k] [(+ total k), (inc prims)]) [0 0]
(for [m (range 2 (Math/sqrt (/ peri 2)))
Line 1,067:
:while (<= p peri)
:when (= 1 (gcd m n))]
(quot peri p))))</langsyntaxhighlight>
 
=={{header|CoffeeScript}}==
This algorithm scales linearly with the max perimeter. It uses two loops that are capped by the square root of the half-perimeter to examine/count provisional values of m and n, where m and n generate a, b, c, and p using simple number theory.
 
<langsyntaxhighlight lang="coffeescript">
gcd = (x, y) ->
return x if y == 0
Line 1,106:
max_perim = Math.pow 10, 9 # takes under a minute
count_triples(max_perim)
</syntaxhighlight>
</lang>
output
<pre>
Line 1,115:
 
=={{header|Common Lisp}}==
<langsyntaxhighlight lang="lisp">(defun mmul (a b)
(loop for x in a collect
(loop for y in x
Line 1,131:
(format t "~a: ~a prim, ~a all~%" lim prim cnt)))
 
(loop for p from 2 do (count-tri (expt 10 p)))</langsyntaxhighlight>output<syntaxhighlight lang="text">100: 7 prim, 17 all
1000: 70 prim, 325 all
10000: 703 prim, 4858 all
Line 1,137:
1000000: 70229 prim, 808950 all
10000000: 702309 prim, 9706567 all
...</langsyntaxhighlight>
 
=={{header|Crystal}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="ruby">class PythagoranTriplesCounter
def initialize(limit = 0)
@limit = limit
Line 1,170:
p [perim, c.total, c.primitives]
perim *= 10
end</langsyntaxhighlight>
 
output
Line 1,185:
===Lazy Functional Version===
With hints from the Haskell solution.
<langsyntaxhighlight lang="d">void main() @safe {
import std.stdio, std.range, std.algorithm, std.typecons, std.numeric;
 
Line 1,199:
writeln("Up to 100 there are ", xs.count, " triples, ",
xs.filter!q{ a[0] }.count, " are primitive.");
}</langsyntaxhighlight>
{{out}}
<pre>Up to 100 there are 17 triples, 7 are primitive.</pre>
 
===Shorter Version===
<langsyntaxhighlight lang="d">ulong[2] tri(ulong lim, ulong a=3, ulong b=4, ulong c=5)
pure nothrow @safe @nogc {
immutable l = a + b + c;
Line 1,220:
foreach (immutable p; 1 .. 9)
writeln(10 ^^ p, ' ', tri(10 ^^ p));
}</langsyntaxhighlight>
{{out}}
<pre>10 [0, 0]
Line 1,234:
===Short SIMD Version===
With LDC compiler this is a little faster than the precedent version (remove @nogc to compile it with the current version of LDC compiler).
<langsyntaxhighlight lang="d">import std.stdio, core.simd;
 
ulong2 tri(in ulong lim, in ulong a=3, in ulong b=4, in ulong c=5)
Line 1,251:
foreach (immutable p; 1 .. 9)
writeln(10 ^^ p, ' ', tri(10 ^^ p).array);
}</langsyntaxhighlight>
The output is the same. Run-time (32 bit system): about 0.67 seconds with ldc2.
 
===Faster Version===
{{trans|C}}
<langsyntaxhighlight lang="d">import std.stdio;
 
alias Xuint = uint; // ulong if going over 1 billion.
Line 1,295:
limit, nTriples, nPrimitives);
}
}</langsyntaxhighlight>
{{out}}
<pre>Up to 10: 0 triples, 0 primitives.
Line 1,344:
The number of primitive triples divided by the maximum perimeter seems to tend to a limit,
which looks very much like (ln 2)/pi^2 = 0.07023049277 (see especially the FreeBASIC output below).
<langsyntaxhighlight lang="edsac">
[Pythagorean triples for Rosetta code.
Counts (1) all Pythagorean triples (2) primitive Pythagorean triples,
Line 1,558:
E 15 Z [define entry point]
P F [acc = 0 on entry]
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,571:
 
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
<lang Eiffel>
class
APPLICATION
Line 1,619:
 
end
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,631:
=={{header|Elixir}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="elixir">defmodule RC do
def count_triples(limit), do: count_triples(limit,3,4,5)
Line 1,644:
 
list = for n <- 1..8, do: Enum.reduce(1..n, 1, fn(_,acc)->10*acc end)
Enum.each(list, fn n -> IO.inspect {n, RC.count_triples(n)} end)</langsyntaxhighlight>
 
{{out}}
Line 1,660:
=={{header|Erlang}}==
 
<syntaxhighlight lang="erlang">%%
<lang Erlang>%%
%% Pythagorian triples in Erlang, J.W. Luiten
%%
Line 1,704:
L = lists:seq(1, Max),
Answer = lists:map(fun(X) -> count_triples(X) end, L),
lists:foreach(fun(Result) -> display_result(Result) end, Answer).</langsyntaxhighlight>
 
Output:
Line 1,722:
 
=={{header|ERRE}}==
<langsyntaxhighlight ERRElang="erre">PROGRAM PIT
 
BEGIN
Line 1,780:
 
PRINT PRINT("** End **")
END PROGRAM</langsyntaxhighlight>
{{out}}
<pre>16:08:39
Line 1,802:
=={{header|Euphoria}}==
{{trans|D}}
<langsyntaxhighlight lang="euphoria">function tri(atom lim, sequence in)
sequence r
atom p
Line 1,822:
? tri(max_peri, {3, 4, 5})
max_peri *= 10
end while</langsyntaxhighlight>
 
Output:
Line 1,837:
=={{header|F_Sharp|F#}}==
{{trans|OCaml}}
<langsyntaxhighlight lang="fsharp">let isqrt n =
let rec iter t =
let d = n - t*t
Line 1,868:
printfn "For perimeters up to %d there are %d total and %d primitive" i s p;;
List.iter show [ 100; 1000; 10000; 100000; 1000000; 10000000; 100000000 ]</langsyntaxhighlight>
{{out}}
<pre>For perimeters up to 100 there are 17 total and 7 primitive
Line 1,881:
Pretty slow (100 times slower than C)...
 
<langsyntaxhighlight lang="factor">USING: accessors arrays formatting kernel literals math
math.functions math.matrices math.ranges sequences ;
IN: rosettacode.pyth
Line 1,923:
"Up to %d: %d triples, %d primitives.\n" printf ;
: pyth ( -- )
8 [1,b] [ 10^ dup count-triplets pprint-triplet-count ] each ;</langsyntaxhighlight>
 
<pre>Up to 10: 0 triples, 0 primitives.
Line 1,938:
 
 
<syntaxhighlight lang="forth ">
<lang Forth >
 
 
Line 2,111:
ok
 
</syntaxhighlight>
</lang>
 
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
{{trans|C efficient method}}
<langsyntaxhighlight lang="fortran">module triples
implicit none
Line 2,161:
max_peri = max_peri * 10
end do
end program Pythagorean</langsyntaxhighlight>
Output:<pre>Up to 10 0 triples 0 primitives
Up to 100 17 triples 7 primitives
Line 2,178:
===Version 1===
Normal version
<langsyntaxhighlight lang="freebasic">' version 30-05-2016
' compile with: fbc -s console
 
Line 2,267:
Print : Print "hit any key to end program"
Sleep
End</langsyntaxhighlight>
{{out}}
<pre>below triples primitive time
Line 2,288:
Attempt to make a faster version (about 20% faster)
 
<langsyntaxhighlight lang="freebasic">' version 30-05-2016
' compile with: fbc -s console
 
Line 2,369:
Print : Print "hit any key to end program"
Sleep
End</langsyntaxhighlight>
{{out}}
<pre>below triples primitive time
Line 2,395:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 2,419:
maxPeri, total, prim)
}
}</langsyntaxhighlight>
Output:
<pre>
Line 2,437:
===Parent/Child Algorithm===
Solution:
<langsyntaxhighlight lang="groovy">class Triple {
BigInteger a, b, c
def getPerimeter() { this.with { a + b + c } }
Line 2,472:
}
}
}</langsyntaxhighlight>
 
Test:
<langsyntaxhighlight lang="groovy">printf (' LIMIT PRIMATIVE ALL\n')
findPythagTriples().sort().each { perimeterLimit, result ->
def exponent = perimeterLimit.toString().size() - 1
printf ('a+b+c <= 10E%2d %9d %12d\n', exponent, result.primative, result.total)
}</langsyntaxhighlight>
 
Output:
Line 2,496:
=={{header|Haskell}}==
 
<langsyntaxhighlight lang="haskell">pytr :: Int -> [(Bool, Int, Int, Int)]
pytr n =
filter
Line 2,519:
<> " are primitive."
where
xs = pytr 100</langsyntaxhighlight>
 
{{Out}}
Line 2,525:
 
Or equivalently (desugaring the list comprehension down to nested concatMaps, and pruning back the search space a little):
<langsyntaxhighlight lang="haskell">------------------- PYTHAGOREAN TRIPLES ------------------
 
pythagoreanTriplesBelow :: Int -> [[Int]]
Line 2,550:
( [id, filter (\[x, y, _] -> gcd x y == 1)]
<*> [pythagoreanTriplesBelow 100]
)</langsyntaxhighlight>
{{Out}}
<pre>17
Line 2,556:
 
Recursive primitive generation:
<langsyntaxhighlight lang="haskell">triangles :: Int -> [[Int]]
triangles max_peri
| max_peri < 12 = []
Line 2,579:
mapM_
((putStrLn . (\n -> show n <> " " <> show (triangleCount n))) . (10 ^))
[1 .. 7]</langsyntaxhighlight>
{{out}}
<pre>10 (0,0)
Line 2,592:
This uses the elegant formula (#IV) from [[wp:Formulas_for_generating_Pythagorean_triples|Formulas for generating Pythagorean triples]]
 
<syntaxhighlight lang="icon">
<lang Icon>
link numbers
link printf
Line 2,630:
every (s := "") ||:= !sort(x) do s ||:= ","
return s[1:-1]
end</langsyntaxhighlight>
 
{{libheader|Icon Programming Library}}
Line 2,664:
Brute force approach:
 
<langsyntaxhighlight lang="j">pytr=: 3 :0
r=. i. 0 3
for_a. 1 + i. <.(y-1)%3 do.
Line 2,677:
)
 
prim=: 1 = 2 +./@{. |:</langsyntaxhighlight>
 
Example use:
Line 2,683:
First column indicates whether the triple is primitive, and the remaining three columns are a, b and c.
 
<langsyntaxhighlight lang="j"> pytr 100
1 3 4 5
1 5 12 13
Line 2,708:
325 70
(# , [: {. +/) pytr 10000
4858 703</langsyntaxhighlight>
 
pytr 10000 takes 4 seconds on this laptop, and time to complete grows with square of perimeter, so pytr 1e6 should take something like 11 hours using this algorithm on this machine.
Line 2,714:
A slightly smarter approach:
 
<langsyntaxhighlight lang="j">trips=:3 :0
'm n'=. |:(#~ 1 = 2 | +/"1)(#~ >/"1) ,/ ,"0/~ }. i. <. %: y
prim=. (#~ 1 = 2 +./@{. |:) (#~ y >: +/"1)m (-&*: ,. +:@* ,. +&*:) n
/:~ ; <@(,.~ # {. 1:)@(*/~ 1 + y i.@<.@% +/)"1 prim
)</langsyntaxhighlight>
 
usage for trips is the same as for pytr. Thus:
 
<langsyntaxhighlight lang="j"> (# , 1 {. +/) trips 10
0 0
(# , 1 {. +/) trips 100
Line 2,735:
808950 70229
(# , 1 {. +/) trips 10000000
9706567 702309</langsyntaxhighlight>
 
The last line took about 16 seconds.
Line 2,741:
That said, we do not actually have to generate all the triples, we just need to count them. Thus:
 
<langsyntaxhighlight lang="j">trc=:3 :0
'm n'=. |:(#~ 1 = 2 | +/"1)(#~ >/"1) ,/ ,"0/~ }. i. <. %: y
<.y%+/"1 (#~ 1 = 2 +./@{. |:) (#~ y >: +/"1)m (-&*: ,. +:@* ,. +&*:) n
)</langsyntaxhighlight>
 
The result is a list of positive integers, one number for each primitive triple which fits within the limit, giving the number of triples which are multiples of that primitive triple whose perimeter is no greater than the limiting perimeter.
 
<syntaxhighlight lang="text"> (#,+/)trc 1e8
7023027 113236940</langsyntaxhighlight>
 
But note that J's memory footprint reached 6.7GB during the computation, so to compute larger values the computation would have to be broken up into reasonable sized blocks.
===Traversal of the Tree of Primitive Pythagorean Triples===
On my laptop this code takes 1.35 seconds for a perimeter of up to 1 million, though it takes 2 minutes for 10 million, so performance is between the previous code "brute force" and what is called "slightly smarter approach" It could probably be sped up slightly by not sorting the triples (there is no need with this problem.)
<syntaxhighlight lang="j">
<lang J>
mp =: +/ . * "2 1
 
Line 2,785:
echo count 10 ^ >: i.6
exit ''
</syntaxhighlight>
</lang>
{{Out}}
<pre>
Line 2,800:
===Brute force===
[[Category:Arbitrary precision]]Theoretically, this can go "forever", but it takes a while, so only the minimum is shown. Luckily, <code>BigInteger</code> has a GCD method built in.
<langsyntaxhighlight lang="java">
import java.math.BigInteger;
import static java.math.BigInteger.ONE;
Line 2,851:
+ tripCount + " triples, of which " + primCount + " are primitive.");
}
}</langsyntaxhighlight>
Output:
<pre>3, 4, 5 primitive
Line 2,877:
{{works with|Java|1.5+}}
This can also go "forever" theoretically. Letting it go to another order of magnitude overflowed the stack on the computer this was tested on. This version also does not show the triples as it goes, it only counts them.
<langsyntaxhighlight lang="java5">import java.math.BigInteger;
 
public class Triples{
Line 2,914:
}
}
}</langsyntaxhighlight>
Output:
<pre>100: 17 triples, 7 primitive.
Line 2,926:
===ES6===
Exhaustive search of a full cartesian product. Not scalable.
<langsyntaxhighlight JavaScriptlang="javascript">(() => {
"use strict";
 
Line 2,994:
// MAIN ---
return main();
})();</langsyntaxhighlight>
{{Out}}
<langsyntaxhighlight JavaScriptlang="javascript">[{"maxPerimeter":10, "triples":0, "primitives":0},
{"maxPerimeter":100, "triples":17, "primitives":7},
{"maxPerimeter":1000, "triples":325, "primitives":70}]</langsyntaxhighlight>
 
=={{header|jq}}==
Line 3,006:
The implementation illustrates how an inner function with arity 0 can
attain a high level of efficiency with both jq 1.4 and later. A simpler implementation is possible with versions of jq greater than 1.4.
<langsyntaxhighlight lang="jq">def gcd(a; b):
def _gcd:
if .[1] == 0 then .[0]
Line 3,043:
 
range(1; 9) | . as $i | 10|pow($i) as $i | "\($i): \(count($i) )"
</syntaxhighlight>
</lang>
{{Out}}
<langsyntaxhighlight lang="sh">$ jq -M -c -r -n -f Pythagorean_triples.jq
10: [0,0]
100: [17,7]
Line 3,054:
10000000: [9706567,702309]
100000000: [113236940,7023027]
</syntaxhighlight>
</lang>
 
=={{header|Julia}}==
This solution uses the the Euclidian concept of m and n as generators of Pythagorean triplets. When m and n are coprime and have opposite parity, the generated triplets are primitive. It works reasonably well up to a limit of 10^10.
<syntaxhighlight lang="julia">
<lang Julia>
function primitiven{T<:Integer}(m::T)
1 < m || return T[]
Line 3,096:
println(@sprintf " 10^%02d %11d %9d" om fcnt pcnt)
end
</syntaxhighlight>
</lang>
 
{{out}}
Line 3,117:
{{trans|Go}}
Due to deep recursion, I needed to increase the stack size to 4MB to get up to a maximum perimeter of 10 billion. Expect a run time of around 30 seconds on a typical laptop.
<langsyntaxhighlight lang="scala">// version 1.1.2
 
var total = 0L
Line 3,143:
maxPeri *= 10
}
}</langsyntaxhighlight>
 
{{out}}
Line 3,159:
 
=={{header|Lasso}}==
<langsyntaxhighlight lang="lasso">// Brute Force: Too slow for large numbers
define num_pythagorean_triples(max_perimeter::integer) => {
local(max_b) = (#max_perimeter / 3)*2
Line 3,177:
stdout(`Number of Pythagorean Triples in a Perimeter of 100: `)
stdoutnl(num_pythagorean_triples(100))
</syntaxhighlight>
</lang>
Output:
<pre>Number of Pythagorean Triples in a Perimeter of 100: 17
Line 3,183:
 
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
<lang lb>
print time$()
 
Line 3,228:
print "End"
end
</syntaxhighlight>
</lang>
<pre>
17:59:34
Line 3,248:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
=== Brute force ===
<langsyntaxhighlight Mathematicalang="mathematica">pythag[n_]:=Block[{soln=Solve[{a^2+b^2==c^2,a+b+c<=n,0<a<b<c},{a,b,c},Integers]},{Length[soln],Count[GCD[a,b]/.soln,1]}]</langsyntaxhighlight>
 
Now prepare timings
 
<syntaxhighlight lang="mathematica">
<lang Mathematica>
pTiming[n_] := With[{comp = Timing@pythag@(10^n)},
{HoldForm[10^n], comp[[2, 1]], comp[[2, 2]], Round@comp[[1]]}];
{{"n", "Triples", "Primitives", "Timing(s)"}}~Join~(pTiming /@ Range@5) // Grid
</syntaxhighlight>
</lang>
{{out}}
 
Line 3,272:
The following uses generating formulae and is adapted from [[:https://mathematica.stackexchange.com/a/15904/2249]]
 
<langsyntaxhighlight Mathematicalang="mathematica">primitivePythag[p_] := Join @@ Table[If[CoprimeQ[m, n], {2 m n, m^2 - n^2, m^2 + n^2}, ## &[]],{m, 2, Floor @ Sqrt @ p},{n, 1 + m ~Mod~ 2, m, 2}] // Select[Total[#] <= p &] // Length</langsyntaxhighlight>
 
Now prepare timings
 
<langsyntaxhighlight Mathematicalang="mathematica">ppTiming[n_] := With[{comp = Timing@primitivePythag@(10^n)},{HoldForm[10^n], comp[[2]], Round@comp[[1]]}];
{{"n", "Primitives", "Timing(s)"}}~Join~(ppTiming /@ Range@9) // Grid</langsyntaxhighlight>
{{out}}
 
Line 3,296:
 
=={{header|MATLAB}} / {{header|Octave}}==
<langsyntaxhighlight Matlablang="matlab">N= 100;
a = 1:N;
b = a(ones(N,1),:).^2;
Line 3,311:
 
printf('There are %i Pythagorean Triples and %i primitive triples with a perimeter smaller than %i.\n',...
sum(ix), length(p), N); </langsyntaxhighlight>
 
Output:
Line 3,320:
From [[List comprehensions]]:
 
<langsyntaxhighlight lang="mercury">
:- module comprehension.
:- interface.
Line 3,343:
solutions((pred(Triple::out) is nondet :- pythTrip(20,Triple)),Result),
write(Result,!IO).
</syntaxhighlight>
</lang>
 
=={{header|Modula-3}}==
Note that this code only works on 64bit machines (where <tt>INTEGER</tt> is 64 bits). Modula-3 provides a <tt>LONGINT</tt> type, which is 64 bits on 32 bit systems, but there is a bug in the implementation apparently.
<langsyntaxhighlight lang="modula3">MODULE PyTriple64 EXPORTS Main;
 
IMPORT IO, Fmt;
Line 3,377:
i := i * 10;
UNTIL i = 10000000;
END PyTriple64.</langsyntaxhighlight>
 
Output:
Line 3,391:
===Brute force method===
{{trans|Java}}
<langsyntaxhighlight Nanoquerylang="nanoquery">import math
 
// a function to check if three numbers are a valid triple
Line 3,435:
 
print "Up to a perimeter of " + perimeter + ", there are " + ts
println " triples, of which " + ps + " are primitive."</langsyntaxhighlight>
{{out}}
<pre>3, 4, 5 primitive
Line 3,459:
Compile with option <code>-d:release</code>. Without release option (i.e. in debug mode), the programs ends prematurely by reaching the recursion depth limit.
{{trans|C}}
<langsyntaxhighlight lang="nim">const u = [[ 1, -2, 2, 2, -1, 2, 2, -2, 3],
[ 1, 2, 2, 2, 1, 2, 2, 2, 3],
[-1, 2, 2, -2, 1, 2, -2, 2, 3]]
Line 3,483:
newTri([3, 4, 5])
echo "Up to ", maxPeri, ": ", total, " triples, ", prim, " primitives"
maxPeri *= 10</langsyntaxhighlight>
Output:
<pre>Up to 10: 0 triples, 0 primitives
Line 3,495:
 
=={{header|OCaml}}==
<langsyntaxhighlight OCamllang="ocaml">let isqrt n =
let rec iter t =
let d = n - t*t in
Line 3,527:
Printf.printf "For perimeters up to %d there are %d total and %d primitive\n%!" i s p;;
 
List.iter show [ 100; 1000; 10000; 100000; 1000000; 10000000; 100000000 ]</langsyntaxhighlight>
Output:
<pre>For perimeters up to 100 there are 17 total and 7 primitive
Line 3,538:
 
=={{header|Ol}}==
<langsyntaxhighlight lang="scheme">
; triples generator based on Euclid's formula, creates lazy list
(define (euclid-formula max)
Line 3,567:
(print max ": " (calculate max)))
(map (lambda (n) (expt 10 n)) (iota 6 1)))
</syntaxhighlight>
</lang>
 
{{out}}
Line 3,581:
=={{header|PARI/GP}}==
This version is reasonably efficient and can handle inputs like a million quickly.
<langsyntaxhighlight lang="parigp">do(lim)={
my(prim,total,P);
lim\=1;
Line 3,595:
[prim,total]
};
do(100)</langsyntaxhighlight>
 
=={{header|Pascal}}==
<langsyntaxhighlight lang="pascal">Program PythagoreanTriples (output);
 
var
Line 3,628:
maxPeri := maxPeri * 10;
end;
end.</langsyntaxhighlight>
Output (on Core2Duo 2GHz laptop):
<pre>time ./PythagoreanTriples
Line 3,643:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">sub gcd {
my ($n, $m) = @_;
while($n){
Line 3,669:
 
tripel 10**$_ for 1..8;
</syntaxhighlight>
</lang>
{{out}}
<pre>Max. perimeter: 10, Total: 0, Primitive: 0
Line 3,683:
=={{header|Phix}}==
{{Trans|Pascal}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">total</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">prim</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxPeri</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span>
Line 3,705:
<span style="color: #000000;">maxPeri</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 3,719:
 
=={{header|PHP}}==
<langsyntaxhighlight lang="php"><?php
function gcd($a, $b)
Line 3,755:
}
 
echo 'Up to ' . $max_p . ', there are ' . $pytha . ' triples, of which ' . $prim . ' are primitive.';</langsyntaxhighlight>
{{out}}<pre>Up to 100, there are 17 triples, of which 7 are primitive.</pre>
 
Line 3,761:
===Prolog-style===
{{trans|Prolog}}
<langsyntaxhighlight Picatlang="picat">main :-
garbage_collect(300_000_000),
Data = [100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000],
Line 3,796:
order2(A, B, A, B) :- A < B, !.
order2(A, B, B, A).</langsyntaxhighlight>
 
{{out}}
Line 3,813:
Picat doesn't have global variables, so all parameters are placed in the call to <code>newTri/6</code>. This is slightly faster than the Prolog port.
 
<langsyntaxhighlight Picatlang="picat">main =>
foreach(MaxPeri in [10**I : I in 2..8])
[Total, Prim] = newTri(MaxPeri,0,0,3,4,5),
Line 3,832:
PrimRet = Prim,
TotalRet = Total
end.</langsyntaxhighlight>
 
{{out}}
Line 3,847:
===With "global variables"===
Actually, Picat has some support for global variables, using the global available map (<code>get_global_map</code>).
<langsyntaxhighlight Picatlang="picat">main =>
foreach(MaxPeri in [10**I : I in 2..8])
Map = get_global_map(),
Line 3,866:
newTri2(+1*S0+2*S1+2*S2, +2*S0+1*S1+2*S2, +2*S0+2*S1+3*S2),
newTri2(-1*S0+2*S1+2*S2, -2*S0+1*S1+2*S2, -2*S0+2*S1+3*S2)
end.</langsyntaxhighlight>
 
This version is - however - slower: 7.401s.
Line 3,872:
=={{header|PicoLisp}}==
{{trans|C}}
<langsyntaxhighlight PicoLisplang="picolisp">(for (Max 10 (>= 100000000 Max) (* Max 10))
(let (Total 0 Prim 0 In (3 4 5))
(recur (In)
Line 3,886:
(recurse
(mapcar '((U) (sum * U In)) Row) ) ) ) ) )
(prinl "Up to " Max ": " Total " triples, " Prim " primitives.") ) )</langsyntaxhighlight>
Output:
<pre>Up to 10: 0 triples, 0 primitives.
Line 3,899:
=={{header|PL/I}}==
Version 1
<langsyntaxhighlight PLlang="pl/Ii">*process source attributes xref or(!);
/*********************************************************************
* REXX pgm counts number of Pythagorean triples
Line 3,988:
End;
 
End;</langsyntaxhighlight>
Version 2
<syntaxhighlight lang="pl/i">
<lang PL/I>
pythagorean: procedure options (main, reorder); /* 23 January 2014 */
declare (a, b, c) fixed (3);
Line 4,022:
end GCD;
 
end pythagorean;</langsyntaxhighlight>
Output:
<pre>
Line 4,033:
 
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
<lang PowerShell>
function triples($p) {
if($p -gt 4) {
Line 4,084:
"There are $(($triples).Count) Pythagorean triples with perimeter no larger than 100
and $(($coprime).Count) of them are coprime."
</syntaxhighlight>
</lang>
<b>Output:</b>
<pre>
Line 4,091:
 
=={{header|Prolog}}==
<langsyntaxhighlight lang="prolog">
show :-
Data = [100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000],
Line 4,129:
order2(A, B, A, B) :- A < B, !.
order2(A, B, B, A).
</syntaxhighlight>
</lang>
 
{{Out}}
Line 4,153:
<math>n \le 10,000</math><br /><br />
 
<langsyntaxhighlight lang="purebasic">
 
Procedure.i ConsoleWrite(t.s) ; compile using /CONSOLE option
Line 4,222:
ConsoleWrite("")
et=ElapsedMilliseconds()-st:ConsoleWrite("Elapsed time = "+str(et)+" milliseconds")
</syntaxhighlight>
</lang>
 
 
Line 4,246:
=={{header|Python}}==
Two methods, the second of which is much faster
<langsyntaxhighlight lang="python">from fractions import gcd
 
 
Line 4,302:
for maxperimeter in range(mn, mx+1, mn):
printit(maxperimeter, algo)
</syntaxhighlight>
</lang>
 
;Output:
Line 4,362:
Up to a perimeter of 19500 there are 10388 triples, of which 1373 are primitive
Up to a perimeter of 20000 there are 10689 triples, of which 1408 are primitive</pre>
Barebone minimum for this task:<langsyntaxhighlight Pythonlang="python">from sys import setrecursionlimit
setrecursionlimit(2000) # 2000 ought to be big enough for everybody
 
Line 4,375:
 
for peri in [10 ** e for e in range(1, 8)]:
print peri, triples(peri)</langsyntaxhighlight>Output:<syntaxhighlight lang="text">10 (0, 0)
100 (7, 17)
1000 (70, 325)
Line 4,381:
100000 (7026, 64741)
1000000 (70229, 808950)
10000000 (702309, 9706567)</langsyntaxhighlight>
 
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">#lang racket
 
#| Euclid's enumeration formula and counting is fast enough for extra credit.
Line 4,428:
113236940, 7023027.
cpu time: 11976 real time: 12215 gc time: 2381
|#</langsyntaxhighlight>
 
=={{header|Raku}}==
Line 4,434:
{{works with|Rakudo|2018.09}}
Here is a straight-forward, naive brute force implementation:
<syntaxhighlight lang="raku" perl6line>constant limit = 100;
 
for [X] [^limit] xx 3 -> (\a, \b, \c) {
say [a, b, c] if a < b < c and a**2 + b**2 == c**2
}</langsyntaxhighlight>
{{out}}
<pre style="height:25ex">3 4 5
Line 4,490:
65 72 97</pre>
Here is a slightly less naive brute force implementation, but still not practical for large perimeter limits.
<syntaxhighlight lang="raku" perl6line>my $limit = 10000;
my atomicint $i = 0;
my @triples[$limit/2];
Line 4,503:
 
say my $result = "There are {+@triples.grep:{$_ !eqv Any}} Pythagorean Triples with a perimeter <= $limit,"
~"\nof which {[+] @triples.grep: so *} are primitive.";</langsyntaxhighlight>
{{out}}
<pre>There are 4858 Pythagorean Triples with a perimeter <= 10000,
of which 703 are primitive.</pre>
Here's a much faster version. Hint, "oyako" is Japanese for "parent/child". <tt>:-)</tt>
<syntaxhighlight lang="raku" perl6line>sub triples($limit) {
my $primitive = 0;
my $civilized = 0;
Line 4,527:
for 10,100,1000 ... * -> $limit {
say triples $limit;
}</langsyntaxhighlight>
Output:
<pre>10 => (0 0)
Line 4,542:
 
Here is an alternate version that avoids naming any scalars that can be handled by vector processing instead. Using vectorized ops allows a bit more potential for parallelization in theory, but techniques like the use of complex numbers to add two numbers in parallel, and the use of <tt>gather</tt>/<tt>take</tt> generate so much overhead that this version runs 70-fold slower than the previous one.
<syntaxhighlight lang="raku" perl6line>constant @coeff = [[+1, -2, +2], [+2, -1, +2], [+2, -2, +3]],
[[+1, +2, +2], [+2, +1, +2], [+2, +2, +3]],
[[-1, +2, +2], [-2, +1, +2], [-2, +2, +3]];
Line 4,564:
for 10, 100, 1000, 10000 -> $limit {
say triples $limit;
}</langsyntaxhighlight>
{{out}}
<pre>10 => (0 0)
Line 4,573:
=={{header|REXX}}==
===using GCD for determinacy===
<langsyntaxhighlight lang="rexx">/*REXX program counts the number of Pythagorean triples that exist given a maximum */
/*──────────────────── perimeter of N, and also counts how many of them are primitives.*/
parse arg N . /*obtain optional argument from the CL.*/
Line 4,598:
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
gcd: procedure; parse arg x,y; do until y==0; parse value x//y y with y x; end; return x</langsyntaxhighlight>
{{out|output|text= &nbsp; when using the default input of: &nbsp; &nbsp; <tt> 100 </tt>}}
<pre>
Line 4,614:
 
Non-primitive Pythagorean triples are generated after a primitive triple is found.
<langsyntaxhighlight lang="rexx">/*REXX program counts the number of Pythagorean triples that exist given a maximum */
/*──────────────────── perimeter of N, and also counts how many of them are primitives.*/
parse arg N . /*obtain optional argument from the CL.*/
Line 4,642:
end /*a*/ /*stick a fork in it, we're all done. */
_= left('', 7) /*for padding the output with 7 blanks.*/
say 'max perimeter =' N _ "Pythagorean triples =" T _ 'primitives =' P</langsyntaxhighlight>
{{out|output|text= &nbsp; is identical to the 1<sup>st</sup> REXX version.}}<br><br>
 
Line 4,651:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
size = 100
sum = 0
Line 4,675:
end
return gcd
</syntaxhighlight>
</lang>
Output:
<pre>
Line 4,701:
=={{header|Ruby}}==
{{trans|Java}}
<langsyntaxhighlight lang="ruby">class PythagoranTriplesCounter
def initialize(limit)
@limit = limit
Line 4,729:
p [perim, c.total, c.primitives]
perim *= 10
end</langsyntaxhighlight>
 
output
Line 4,742:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">use std::thread;
 
fn f1 (a : u64, b : u64, c : u64, d : u64) -> u64 {
Line 4,787:
new_th_1.join().unwrap();
new_th_2.join().unwrap();
}</langsyntaxhighlight>
{{out}}
<pre> Primitive triples below 100 : 7
Line 4,816:
=={{header|Scala}}==
{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/CAz60TW/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/soOLJ673Q82l78OCgIx4oQ Scastie (remote JVM)].
<langsyntaxhighlight Scalalang="scala">object PythagoreanTriples extends App {
 
println(" Limit Primatives All")
Line 4,840:
println(f"a + b + c <= ${limit.toFloat}%3.1e $primCount%9d $tripCount%12d")
}
}</langsyntaxhighlight>
 
=={{header|Scheme}}==
{{works with|Gauche Scheme}}
<langsyntaxhighlight Schemelang="scheme">(use srfi-42)
 
(define (py perim)
Line 4,855:
(begin (when (= 1 (gcd a b)) (inc! prim)))
1)
prim))</langsyntaxhighlight>
<b>Testing:</b>
<pre>
Line 4,874:
The example below uses [http://seed7.sourceforge.net/libraries/bigint.htm bigInteger] numbers:
 
<langsyntaxhighlight lang="seed7">$ include "seed7_05.s7i";
include "bigint.s7i";
 
Line 4,904:
max_peri *:= 10_;
end while;
end func;</langsyntaxhighlight>
 
Output:
Line 4,920:
=={{header|Sidef}}==
{{trans|Raku}}
<langsyntaxhighlight lang="ruby">func triples(limit) {
var primitive = 0
var civilized = 0
Line 4,940:
for n (1..Inf) {
say triples(10**n)
}</langsyntaxhighlight>
 
{{out}}
Line 4,955:
=={{header|Swift}}==
{{trans|Pascal}}
<langsyntaxhighlight Swiftlang="swift">var total = 0
var prim = 0
var maxPeri = 100
Line 4,977:
print("Up to \(maxPeri) : \(total) triples \( prim) primitives.")
maxPeri *= 10
}</langsyntaxhighlight>
 
{{out}}
Line 4,993:
Using the efficient method based off the Wikipedia article:
<!--There's no technical reason to limit the code to just these values, but generation does get progressively slower with larger maximum perimiters. 10M is about as much as I have patience for; I'm generally impatient! -->
<langsyntaxhighlight lang="tcl">proc countPythagoreanTriples {limit} {
lappend q 3 4 5
set idx [set count [set prim 0]]
Line 5,017:
lassign [countPythagoreanTriples $i] count primitive
puts "perimeter limit $i => $count triples, $primitive primitive"
}</langsyntaxhighlight>
Output:
<pre>
Line 5,030:
 
=={{header|VBA}}==
{{trans|Pascal}}<langsyntaxhighlight lang="vb">Dim total As Variant, prim As Variant, maxPeri As Variant
Private Sub newTri(s0 As Variant, s1 As Variant, s2 As Variant)
Dim p As Variant
Line 5,051:
maxPeri = maxPeri * 10
Loop
End Sub</langsyntaxhighlight>{{out}}
<pre>Up to 100 : 17 triples, 7 primitives.
Up to 1000 : 325 triples, 70 primitives.
Line 5,062:
=={{header|VBScript}}==
{{trans|Perl}}
<syntaxhighlight lang="vb">
<lang vb>
For i=1 To 8
WScript.StdOut.WriteLine triples(10^i)
Line 5,099:
Loop
End Function
</syntaxhighlight>
</lang>
 
=={{header|Visual Basic}}==
Line 5,108:
{{works with|VBA|6.5}}
{{works with|VBA|7.1}}
<langsyntaxhighlight lang="vb">Option Explicit
 
Dim total As Long, prim As Long, maxPeri As Long
Line 5,135:
maxPeri = maxPeri * 10
Loop
End Sub</langsyntaxhighlight>
{{out}}
<pre>Up to 100 : 17 triples, 7 primitives.
Line 5,148:
{{trans|Go}}
Limited to a maximum perimeter of 10 billion in order to finish in a reasonable time.
<langsyntaxhighlight lang="ecmascript">var sc = System.clock
var total = 0
var prim = 0
Line 5,173:
System.print("Up to %(maxPeri): %(total) triples, %(prim) primitives, %(secs) seconds")
maxPeri = 10 * maxPeri
}</langsyntaxhighlight>
 
{{out}}
Line 5,191:
=={{header|XPL0}}==
Simple minded algorithm:
<langsyntaxhighlight XPL0lang="xpl0">func GCD(N, D); \Return the greatest common divisor of N and D
int N, D, R; \numerator and denominator
[if D > N then
Line 5,225:
Max:= Max*10;
until Max > 10_000;
]</langsyntaxhighlight>
 
{{out}}
Line 5,236:
 
{{trans|Go}}
<langsyntaxhighlight XPL0lang="xpl0">int Total, Prim, MaxPeri;
proc NewTri(S0, S1, S2);
Line 5,261:
MaxPeri:= MaxPeri*10;
];
]</langsyntaxhighlight>
 
{{out}}
Line 5,277:
=={{header|zkl}}==
{{trans|D}}
<langsyntaxhighlight lang="zkl">fcn tri(lim,a=3,b=4,c=5){
p:=a + b + c;
if(p>lim) return(0,0);
Line 5,285:
tri(lim, -a + 2*b + 2*c, -2*a + b + 2*c, -2*a + 2*b + 3*c)
);
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">n:=10; do(10){ println("%,d: %s".fmt(n,tri(n).reverse())); n*=10; }</langsyntaxhighlight>
{{out}}
<pre>10: L(0,0)
Line 5,319:
Set in line nr: 11 IF L<=1000 THEN GO TO 2
 
<langsyntaxhighlight lang="zxbasic"> 1 LET Y=0: LET X=0: LET Z=0: LET V=0: LET U=0: LET L=10: LET T=0: LET P=0: LET N=4: LET M=0: PRINT "limit trip. prim."
2 FOR U=2 TO INT (SQR (L/2)): LET Y=U-INT (U/2)*2: LET N=N+4: LET M=U*U*2: IF Y=0 THEN LET M=M-U-U
3 FOR V=1+Y TO U-1 STEP 2: LET M=M+N: LET X=U: LET Y=V
Line 5,329:
9 NEXT U
10 PRINT L;TAB 8;T;TAB 16;P
11 LET N=4: LET T=0: LET P=0: LET L=L*10: IF L<=100000 THEN GO TO 2</langsyntaxhighlight>
{{out}}
<pre>limit trip. prim.
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328218"