Pythagorean triples: Difference between revisions

 

 

<br><br>

 

=={{header|Ada}}==

Translation of efficient method from C, see [[wp:Pythagorean_triple#Parent.2Fchild_relationships|the WP article]]. Compiles on gnat/gcc.

 

 

procedure Pythagorean_Triples is

Large_Natural'Image(P_Cnt) & " Primitives");

end loop;

 

Output:

Up to 10 ** 8 : 113236940 Triples, 7023027 Primitives

Up to 10 ** 9 : 1294080089 Triples, 70230484 Primitives</pre>

 

=={{header|AutoHotkey}}==

SetBatchLines, -1

#SingleInstance, Force

 

Loop, 8

 

{{out}}

100000000: 7023027 primitives out of 113236940 triples</pre>

 

The built-in array arithmetic is very well suited to this task!

U0%() = 1, -2, 2, 2, -1, 2, 2, -2, 3

U1%() = 1, 2, 2, 2, 1, 2, 2, 2, 3

t%() = U2%() . i%()

PROCtri(t%(), mp%, all%, prim%)

'''Output:'''

<pre>

=={{header|Bracmat}}==

{{trans|C}}

total prim max-peri U

. (.(1,-2,2) (2,-1,2) (2,-2,3))

pythagoreanTriples$;

 

Output (under Linux):

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.

 

total prim max-peri U stack

. (.(1,-2,2) (2,-1,2) (2,-2,3))

);

 

 

=={{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.

#include <stdlib.h>

 

return 0;

#include <stdlib.h>

#include <stdint.h>

}

return 0;

Up to 100: 17 triples, 7 primitives.

Up to 1000: 325 triples, 70 primitives.

Up to 1000000: 808950 triples, 70229 primitives.

Up to 10000000: 9706567 triples, 702309 primitives.

 

Same as above, but with loop unwound and third recursion eliminated:

#include <stdlib.h>

#include <stdint.h>

}

return 0;

 

=={{header|C sharp|C#}}==

Based on Ada example, which is a translation of efficient method from C, see [[wp:Pythagorean_triple#Parent.2Fchild_relationships|the WP article]].

 

 

namespace RosettaCode.CSharp

}

}

 

Output:

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.

(defn pyth [peri]

(reduce (fn [[total prims] t] [(inc total), (if (first t) (inc prims) prims)])

[0 0]

To handle really large perimeters, we can dispense with actually generating the triples and just calculate the counts:

(reduce (fn [[total prims] k] [(+ total k), (inc prims)]) [0 0]

(for [m (range 2 (Math/sqrt (/ peri 2)))

:while (<= p peri)

:when (= 1 (gcd m n))]

 

=={{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.

 

gcd = (x, y) ->

return x if y == 0

max_perim = Math.pow 10, 9 # takes under a minute

count_triples(max_perim)

output

<pre>

 

=={{header|Common Lisp}}==

(loop for x in a collect

(loop for y in x

for z in b sum (* y z))))

 

 

1000: 70 prim, 325 all

10000: 703 prim, 4858 all

1000000: 70229 prim, 808950 all

10000000: 702309 prim, 9706567 all

 

=={{header|D}}==

===Lazy Functional Version===

With hints from the Haskell solution.

import std.stdio, std.range, std.algorithm, std.typecons, std.numeric;

 

writeln("Up to 100 there are ", xs.count, " triples, ",

xs.filter!q{ a[0] }.count, " are primitive.");

{{out}}

<pre>Up to 100 there are 17 triples, 7 are primitive.</pre>

 

===Shorter Version===

pure nothrow @safe @nogc {

immutable l = a + b + c;

foreach (immutable p; 1 .. 9)

writeln(10 ^^ p, ' ', tri(10 ^^ p));

{{out}}

<pre>10 [0, 0]

===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).

 

ulong2 tri(in ulong lim, in ulong a=3, in ulong b=4, in ulong c=5)

foreach (immutable p; 1 .. 9)

writeln(10 ^^ p, ' ', tri(10 ^^ p).array);

The output is the same. Run-time (32 bit system): about 0.67 seconds with ldc2.

 

===Faster Version===

{{trans|C}}

 

alias Xuint = uint; // ulong if going over 1 billion.

limit, nTriples, nPrimitives);

}

{{out}}

<pre>Up to 10: 0 triples, 0 primitives.

Up to 10000000000: 14557915466 triples, 702304875 primitives.

Up to 100000000000: 161750315680 triples, 7023049293 primitives.</pre>

 

=={{header|Eiffel}}==

class

APPLICATION

 

end

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Ruby}}

def count_triples(limit), do: count_triples(limit,3,4,5)

 

list = for n <- 1..8, do: Enum.reduce(1..n, 1, fn(_,acc)->10*acc end)

 

{{out}}

=={{header|Erlang}}==

 

%% Pythagorian triples in Erlang, J.W. Luiten

%%

L = lists:seq(1, Max),

Answer = lists:map(fun(X) -> count_triples(X) end, L),

 

Output:

 

=={{header|ERRE}}==

 

BEGIN

 

PRINT PRINT("** End **")

{{out}}

<pre>16:08:39

=={{header|Euphoria}}==

{{trans|D}}

sequence r

atom p

? tri(max_peri, {3, 4, 5})

max_peri *= 10

 

Output:

100000000: {7023027,113236940}

</pre>

 

=={{header|F_Sharp|F#}}==

{{trans|OCaml}}

let rec iter t =

let d = n - t*t

printfn "For perimeters up to %d there are %d total and %d primitive" i s p;;

{{out}}

<pre>For perimeters up to 100 there are 17 total and 7 primitive

Pretty slow (100 times slower than C)...

 

math.functions math.matrices math.ranges sequences ;

IN: rosettacode.pyth

"Up to %d: %d triples, %d primitives.\n" printf ;

: pyth ( -- )

 

<pre>Up to 10: 0 triples, 0 primitives.

Up to 100000000: 113236940 triples, 7023027 primitives.

Running time: 57.968821207 seconds</pre>

 

=={{header|Forth}}==

 

 

 

 

ok

 

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

{{trans|C efficient method}}

implicit none

max_peri = max_peri * 10

end do

Output:<pre>Up to 10 0 triples 0 primitives

Up to 100 17 triples 7 primitives

===Version 1===

Normal version

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>below triples primitive time

Attempt to make a faster version (about 20% faster)

 

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>below triples primitive time

 

=={{header|Go}}==

 

import "fmt"

maxPeri, total, prim)

}

Output:

<pre>

===Parent/Child Algorithm===

Solution:

BigInteger a, b, c

def getPerimeter() { this.with { a + b + c } }

}

}

 

Test:

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)

 

Output:

=={{header|Haskell}}==

 

pytr n =

filter

(\(_, a, b, c) -> a + b + c <= n)

[ (prim a b c, a, b, c)

where

xs = [1 .. n]

main =

putStrLn $

where

 

{{Out}}

 

Or equivalently (desugaring the list comprehension down to nested concatMaps, and pruning back the search space a little):

pythagoreanTriplesBelow n =

 

main :: IO ()

main =

mapM_

(print . length)

{{Out}}

<pre>17

 

Recursive primitive generation:

triangles max_peri

| max_peri < 12 = []

map

(map (sum . zipWith (*) t))

]

 

main =

mapM_

{{out}}

<pre>10 (0,0)

This uses the elegant formula (#IV) from [[wp:Formulas_for_generating_Pythagorean_triples|Formulas for generating Pythagorean triples]]

 

link numbers

link printf

every (s := "") ||:= !sort(x) do s ||:= ","

return s[1:-1]

 

{{libheader|Icon Programming Library}}

Under perimiter=10000000: Pythagorean Triples=9706567 including primitives=702309

Time=560625, Collections: total=16 string=8 block=8</pre>

 

=={{header|J}}==

Brute force approach:

 

r=. i. 0 3

for_a. 1 + i. <.(y-1)%3 do.

)

 

 

Example use:

First column indicates whether the triple is primitive, and the remaining three columns are a, b and c.

 

1 3 4 5

1 5 12 13

325 70

(# , [: {. +/) pytr 10000

 

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.

A slightly smarter approach:

 

'm n'=. |:(#~ 1 = 2 | +/"1)(#~ >/"1) ,/ ,"0/~ }. i. <. %: y

prim=. (#~ 1 = 2 +./@{. |:) (#~ y >: +/"1)m (-&*: ,. +:@* ,. +&*:) n

/:~ ; <@(,.~ # {. 1:)@(*/~ 1 + y i.@<.@% +/)"1 prim

 

usage for trips is the same as for pytr. Thus:

 

0 0

(# , 1 {. +/) trips 100

808950 70229

(# , 1 {. +/) trips 10000000

 

The last line took about 16 seconds.

That said, we do not actually have to generate all the triples, we just need to count them. Thus:

 

'm n'=. |:(#~ 1 = 2 | +/"1)(#~ >/"1) ,/ ,"0/~ }. i. <. %: y

<.y%+/"1 (#~ 1 = 2 +./@{. |:) (#~ y >: +/"1)m (-&*: ,. +:@* ,. +&*:) n

 

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.

 

 

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.

 

=={{header|Java}}==

===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.

import java.math.BigInteger;

import static java.math.BigInteger.ONE;

+ tripCount + " triples, of which " + primCount + " are primitive.");

}

Output:

<pre>3, 4, 5 primitive

[[Pythagorean triples/Java/Brute force primitives]]

===Parent/child===

{{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.

 

public class Triples{

}

}

Output:

<pre>100: 17 triples, 7 primitive.

===ES6===

Exhaustive search of a full cartesian product. Not scalable.

 

// Arguments: predicate, maximum perimeter

// pythTripleCount :: ((Int, Int, Int) -> Bool) -> Int -> Int

 

)

 

.map(n => ({

maxPerimeter: n,

}));

 

{{Out}}

{"maxPerimeter":100, "triples":17, "primitives":7},

 

=={{header|jq}}==

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.

def _gcd:

if .[1] == 0 then .[0]

 

# '''Example''':

 

range(1; 9) | . as $i | 10|pow($i) as $i | "\($i): \(count($i) )"

{{Out}}

10: [0,0]

100: [17,7]

10000000: [9706567,702309]

100000000: [113236940,7023027]

 

=={{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.

function primitiven{T<:Integer}(m::T)

1 < m || return T[]

println(@sprintf " 10^%02d %11d %9d" om fcnt pcnt)

end

 

{{out}}

{{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.

 

var total = 0L

maxPeri *= 10

}

 

{{out}}

 

=={{header|Lasso}}==

define num_pythagorean_triples(max_perimeter::integer) => {

local(max_b) = (#max_perimeter / 3)*2

stdout(`Number of Pythagorean Triples in a Perimeter of 100: `)

stdoutnl(num_pythagorean_triples(100))

Output:

<pre>Number of Pythagorean Triples in a Perimeter of 100: 17

 

=={{header|Liberty BASIC}}==

print time$()

 

print "End"

end

<pre>

17:59:34

End

</pre>

 

{{out}}

 

 

 

=={{header|MATLAB}} / {{header|Octave}}==

a = 1:N;

b = a(ones(N,1),:).^2;

 

printf('There are %i Pythagorean Triples and %i primitive triples with a perimeter smaller than %i.\n',...

 

Output:

<pre> There are 17 Pythagorean Triples and 7 primitive triples with a perimeter smaller than 100.</pre>

 

=={{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.

 

IMPORT IO, Fmt;

i := i * 10;

UNTIL i = 10000000;

 

Output:

1000000: 808950 Triples, 70229 Primitives

</pre>

 

=={{header|Nim}}==

{{trans|C}}

[ 1, 2, 2, 2, 1, 2, 2, 2, 3],

[-1, 2, 2, -2, 1, 2, -2, 2, 3]]

maxPeri = 10

 

var p = ins[0] + ins[1] + ins[2]

if p > maxPeri: return

newTri([3, 4, 5])

echo "Up to ", maxPeri, ": ", total, " triples, ", prim, " primitives"

Output:

<pre>Up to 10: 0 triples, 0 primitives

 

=={{header|OCaml}}==

let rec iter t =

let d = n - t*t in

Printf.printf "For perimeters up to %d there are %d total and %d primitive\n%!" i s p;;

 

Output:

<pre>For perimeters up to 100 there are 17 total and 7 primitive

For perimeters up to 10000000 there are 9706567 total and 702309 primitive

For perimeters up to 100000000 there are 113236940 total and 7023027 primitive</pre>

 

=={{header|PARI/GP}}==

This version is reasonably efficient and can handle inputs like a million quickly.

my(prim,total,P);

lim\=1;

[prim,total]

};

 

=={{header|Pascal}}==

 

var

maxPeri := maxPeri * 10;

end;

Output (on Core2Duo 2GHz laptop):

<pre>time ./PythagoreanTriples

 

=={{header|Perl}}==

my ($n, $m) = @_;

while($n){

 

tripel 10**$_ for 1..8;

{{out}}

<pre>Max. perimeter: 10, Total: 0, Primitive: 0

</pre>

 

 

 

 

 

}

 

 

 

 

 

 

 

 

 

=={{header|PicoLisp}}==

{{trans|C}}

(let (Total 0 Prim 0 In (3 4 5))

(recur (In)

(recurse

(mapcar '((U) (sum * U In)) Row) ) ) ) ) )

Output:

<pre>Up to 10: 0 triples, 0 primitives.

=={{header|PL/I}}==

Version 1

/*********************************************************************

* REXX pgm counts number of Pythagorean triples

End;

 

Version 2

pythagorean: procedure options (main, reorder); /* 23 January 2014 */

declare (a, b, c) fixed (3);

end GCD;

 

Output:

<pre>

 

=={{header|PowerShell}}==

function triples($p) {

if($p -gt 4) {

"There are $(($triples).Count) Pythagorean triples with perimeter no larger than 100

and $(($coprime).Count) of them are coprime."

<b>Output:</b>

<pre>

There are 17 Pythagorean triples with perimeter no larger than 100 and 7 of them are coprime.

</pre>

 

<math>n \le 10,000</math><br /><br />

 

 

Procedure.i ConsoleWrite(t.s) ; compile using /CONSOLE option

ConsoleWrite("")

et=ElapsedMilliseconds()-st:ConsoleWrite("Elapsed time = "+str(et)+" milliseconds")

 

 

=={{header|Python}}==

Two methods, the second of which is much faster

 

 

for maxperimeter in range(mn, mx+1, mn):

printit(maxperimeter, algo)

 

;Output:

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>

setrecursionlimit(2000) # 2000 ought to be big enough for everybody

 

 

for peri in [10 ** e for e in range(1, 8)]:

100 (7, 17)

1000 (70, 325)

100000 (7026, 64741)

1000000 (70229, 808950)

 

=={{header|Racket}}==

 

#| Euclid's enumeration formula and counting is fast enough for extra credit.

113236940, 7023027.

cpu time: 11976 real time: 12215 gc time: 2381

 

=={{header|REXX}}==

/*──────────────────── perimeter of N, and also counts how many of them are primitives.*/

parse arg N . /*obtain optional argument from the CL.*/

do c=b+1 /*compute the value of the third side. */

end /*c*/

end /*b*/

end /*a*/

say 'max perimeter =' N _ "Pythagorean triples =" T _ 'primitives =' P

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

<pre>

max perimeter = 100 Pythagorean triples = 17 primitives = 7

</pre>

<pre>

max perimeter = 1000 Pythagorean triples = 325 primitives = 70

===using single evenness for determinacy===

This REXX version takes advantage that primitive Pythagorean triples must have one and only one &nbsp; ''even'' &nbsp; number.

 

Non-primitive Pythagorean triples are generated after a primitive triple is found.

/*──────────────────── perimeter of N, and also counts how many of them are primitives.*/

parse arg N . /*obtain optional argument from the CL.*/

aEven= a//2==0 /*set variable to 1 if A is even. */

do c=b + 1 /*compute the value of the third side. */

do m=2 while a*m+b*m+c*m<=N /*generate non-primitives Pythagoreans.*/

end /*m*/

end /*c*/

end /*b*/

 

=={{header|Ring}}==

size = 100

sum = 0

end

return gcd

Output:

<pre>

=={{header|Ruby}}==

{{trans|Java}}

def initialize(limit)

@limit = limit

p [perim, c.total, c.primitives]

perim *= 10

 

output

[10000000, 9706567, 702309]

[100000000, 113236940, 7023027]</pre>

 

=={{header|Scheme}}==

{{works with|Gauche Scheme}}

 

(define (py perim)

(begin (when (= 1 (gcd a b)) (inc! prim)))

1)

<b>Testing:</b>

<pre>

7

</pre>

 

=={{header|Scratch}}==

The example below uses [http://seed7.sourceforge.net/libraries/bigint.htm bigInteger] numbers:

 

include "bigint.s7i";

 

max_peri *:= 10_;

end while;

 

Output:

 

=={{header|Sidef}}==

var primitive = 0

var civilized = 0

for n (1..Inf) {

say triples(10**n)

 

{{out}}

=={{header|Swift}}==

{{trans|Pascal}}

var prim = 0

var maxPeri = 100

print("Up to \(maxPeri) : \(total) triples \( prim) primitives.")

maxPeri *= 10

 

{{out}}

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! -->

lappend q 3 4 5

set idx [set count [set prim 0]]

lassign [countPythagoreanTriples $i] count primitive

puts "perimeter limit $i => $count triples, $primitive primitive"

Output:

<pre>

perimeter limit 1000000 => 808950 triples, 70229 primitive

perimeter limit 10000000 => 9706567 triples, 702309 primitive

</pre>

 

=={{header|VBScript}}==

{{trans|Perl}}

For i=1 To 8

WScript.StdOut.WriteLine triples(10^i)

Loop

End Function

 

=={{header|zkl}}==

{{trans|D}}

p:=a + b + c;

if(p>lim) return(0,0);

tri(lim, -a + 2*b + 2*c, -2*a + b + 2*c, -2*a + 2*b + 3*c)

);

{{out}}

<pre>10: L(0,0)

</pre>

Max stack size is arbitrary but not adjustable.

=={{header|ZX Spectrum Basic}}==

ZX Spectrum: 8 bit microprocessor 3.5 Mhz doing all the work.

Set in line nr: 11 IF L<=1000 THEN GO TO 2

 

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

9 NEXT U

10 PRINT L;TAB 8;T;TAB 16;P

{{out}}

<pre>limit trip. prim.