Heronian triangles: Difference between revisions
m (→{{header|REXX}}: adjusted the REXX statement number mentioned.) |
m (→{{header|REXX}}: quantified the optimization (before and after).) |
||
Line 1,269: | Line 1,269: | ||
Also, a fair amount of code was added to optimize the speed (at the expense of program simplicity); by thoughtful ordering of |
Also, a fair amount of code was added to optimize the speed (at the expense of program simplicity); by thoughtful ordering of |
||
<br>the "elimination" checks, and also the use of an integer version of a SQRT subroutine, the execution time was greatly reduced |
<br>the "elimination" checks, and also the use of an integer version of a SQRT subroutine, the execution time was greatly reduced |
||
<br>(by a factor of six). |
|||
Note that the '''iSQRT''' subroutine doesn't use floating point. |
Note that the '''iSQRT''' subroutine doesn't use floating point. |
Revision as of 18:53, 8 February 2015
You are encouraged to solve this task according to the task description, using any language you may know.
Hero's formula for the area of a triangle given the length of its three sides a, b, and c is given by:
where s is half the perimeter of the triangle; that is,
Heronian triangles are triangles whose sides and area are all integers.
- An example is the triangle with sides 3, 4, 5 whose area is 6 (and whose perimeter is 12).
Note that any triangle whose sides are all an integer multiple of 3,4,5; such as 6,8,10, will also be a Heronian triangle.
Define a Primitive Heronian triangle as a Heronian triangle where the greatest common divisor of all three sides is 1. This will exclude, for example triangle 6,8,10
The task is to:
- Create a named function/method/procedure/... that implements Hero's formula.
- Use the function to generate all the primitive Heronian triangles with sides <= 200.
- Show the count of how many triangles are found.
- Order the triangles by first increasing area, then by increasing perimeter, then by increasing maximum side lengths
- Show the first ten ordered triangles in a table of sides, perimeter, and area.
- Show a similar ordered table for those triangles with area = 210
Show all output here.
Note: when generating triangles it may help to restrict
C#
<lang Csharp> using System; using System.Collections.Generic;
namespace heron {
class Program{ static void Main(string[] args){ List<int[]> list = new List<int[]>(); for (int c = 1; c <= 200; c++) for (int b = 1; b <= c; b++) for (int a = 1; a <= b; a++) if (gcd(a, gcd(b, c)) == 1 && isHeron(heronArea(a, b, c))) list.Add(new int[] { a, b, c, a + b + c, (int)heronArea(a, b, c)}); sort(list); Console.WriteLine("Number of primitive Heronian triangles with sides up to 200: " + list.Count + "\n\nFirst ten when ordered by increasing area, then perimeter,then maximum sides:\nSides\t\t\tPerimeter\tArea"); for(int i = 0; i < 10; i++) Console.WriteLine(list[i][0] + "\t" + list[i][1] + "\t" + list[i][2] + "\t" + list[i][3] + "\t\t" + list[i][4]); Console.WriteLine("\nPerimeter = 210\nSides\t\t\tPerimeter\tArea"); foreach (int[] i in list) if (i[4] == 210) Console.WriteLine(i[0] + "\t" + i[1] + "\t" + i[2] + "\t" + i[3] + "\t\t" + i[4]); } static bool isHeron(double heronArea){ return heronArea % 1 == 0 && heronArea != 0; } static double heronArea(int a, int b, int c){ double s = (a + b + c) / 2d; return Math.Sqrt(s * (s - a) * (s - b) * (s - c)); } static int gcd(int a, int b){ int remainder = 1, dividend, divisor; dividend = a > b ? a : b; divisor = a > b ? b : a; while (remainder != 0){ remainder = dividend % divisor; if (remainder != 0){ dividend = divisor; divisor = remainder; } } return divisor; } static void sort(List<int[]> list){ int[] temp = new int[5]; bool changed = true; while(changed){ changed = false; for (int i = 1; i < list.Count; i++) if (list[i][4] < list[i - 1][4] || list[i][4] == list[i - 1][4] && list[i][3] < list[i - 1][3]){ temp = list[i]; list[i] = list[i - 1]; list[i - 1] = temp; changed = true; } } } }
} </lang>
- Output:
<lang> Number of primitive Heronian triangles with sides up to 200: 517
First ten when ordered by increasing area, then perimeter,then maximum sides: Sides Perimeter Area 3 4 5 12 6 5 5 6 16 12 5 5 8 18 12 4 13 15 32 24 5 12 13 30 30 9 10 17 36 36 3 25 26 54 36 7 15 20 42 42 10 13 13 36 60 8 15 17 40 60
Perimeter = 210 Sides Perimeter Area 17 25 28 70 210 20 21 29 70 210 12 35 37 84 210 17 28 39 84 210 7 65 68 140 210 3 148 149 300 210 </lang>
D
<lang d>import std.stdio, std.math, std.range, std.algorithm, std.numeric, std.traits, std.typecons;
double hero(in uint a, in uint b, in uint c) pure nothrow @safe @nogc {
immutable s = (a + b + c) / 2.0; immutable a2 = s * (s - a) * (s - b) * (s - c); return (a2 > 0) ? a2.sqrt : 0.0;
}
bool isHeronian(in uint a, in uint b, in uint c) pure nothrow @safe @nogc {
immutable h = hero(a, b, c); return h > 0 && h.floor == h.ceil;
}
T gcd3(T)(in T x, in T y, in T z) pure nothrow @safe @nogc {
return gcd(gcd(x, y), z);
}
void main() /*@safe*/ {
enum uint maxSide = 200;
// Sort by increasing area, perimeter, then sides. //auto h = cartesianProduct!3(iota(1, maxSide + 1)) auto r = iota(1, maxSide + 1); const h = cartesianProduct(r, r, r) //.filter!({a, b, c} => ... .filter!(t => t[0] <= t[1] && t[1] <= t[2] && t[0] + t[1] > t[2] && t[].gcd3 == 1 && t[].isHeronian) .array .schwartzSort!(t => tuple(t[].hero, t[].only.sum, t.reverse)) .release;
static void showTriangles(R)(R ts) @safe { "Area Perimeter Sides".writeln; foreach (immutable t; ts) writefln("%3s %8d %3dx%dx%d", t[].hero, t[].only.sum, t[]); }
writefln("Primitive Heronian triangles with sides up to %d: %d", maxSide, h.length); "\nFirst ten when ordered by increasing area, then perimeter,then maximum sides:".writeln; showTriangles(h.take(10));
"\nAll with area 210 subject to the previous ordering:".writeln; showTriangles(h.filter!(t => t[].hero == 210));
}</lang>
- Output:
Primitive Heronian triangles with sides up to 200: 517 First ten when ordered by increasing area, then perimeter,then maximum sides: Area Perimeter Sides 6 12 3x4x5 12 16 5x5x6 12 18 5x5x8 24 32 4x13x15 30 30 5x12x13 36 36 9x10x17 36 54 3x25x26 42 42 7x15x20 60 36 10x13x13 60 40 8x15x17 All with area 210 subject to the previous ordering: Area Perimeter Sides 210 70 17x25x28 210 70 20x21x29 210 84 12x35x37 210 84 17x28x39 210 140 7x65x68 210 300 3x148x149
ERRE
<lang ERRE> PROGRAM HERON
DIM LISTA%[600,4]
PROCEDURE GCD(J%,K%->MCD%)
WHILE J%<>K% DO IF J%>K% THEN J%=J%-K% ELSE K%=K%-J% END IF END WHILE MCD%=J%
END PROCEDURE
BEGIN
PRINT(CHR$(12);) !CLS FOR C%=1 TO 200 DO FOR B%=1 TO C% DO FOR A%=1 TO B% DO S#=(A%+B%+C%)/2# AREA#=S#*(S#-A%)*(S#-B%)*(S#-C%) IF AREA#>0 THEN AREA#=SQR(AREA#) IF AREA#=INT(AREA#) THEN GCD(B%,C%->RES%) GCD(A%,RES%->RES%) IF RES%=1 THEN COUNT%=COUNT%+1 LISTA%[COUNT%,0]=A% LISTA%[COUNT%,1]=B% LISTA%[COUNT%,2]=C% LISTA%[COUNT%,3]=2*S# LISTA%[COUNT%,4]=AREA# END IF END IF END IF END FOR END FOR
END FOR
PRINT("Number of triangles:";COUNT%)
! sorting array FLIPS%=TRUE WHILE FLIPS% DO
FLIPS%=FALSE FOR I%=1 TO COUNT%-1 DO IF LISTA%[I%,4]>LISTA%[I%+1,4] THEN FOR K%=0 TO 4 DO SWAP(LISTA%[I%,K%],LISTA%[I%+1,K%]) END FOR FLIPS%=TRUE END IF END FOR
END WHILE
! first ten FOR I%=1 TO 10 DO
PRINT(#1,LISTA%[I%,0],LISTA%[I%,1],LISTA%[I%,2],LISTA%[I%,3],LISTA%[I%,4])
END FOR PRINT
! triangle with area=210 FOR I%=1 TO COUNT% DO
IF LISTA%[I%,4]=210 THEN PRINT(LISTA%[I%,0],LISTA%[I%,1],LISTA%[I%,2],LISTA%[I%,3],LISTA%[I%,4]) END IF
END FOR END PROGRAM </lang>
Number of triangles: 517 3 4 5 12 6 5 5 6 16 12 5 5 8 18 12 4 13 15 32 24 5 12 13 30 30 9 10 17 36 36 3 25 26 54 36 7 15 20 42 42 10 13 13 36 60 8 15 17 40 60 17 25 28 70 210 20 21 29 70 210 12 35 37 84 210 17 28 39 84 210 7 65 68 140 210 3 148 149 300 210
Haskell
<lang Haskell>import qualified Data.List as L import Data.Maybe import Data.Ord import Text.Printf
-- Determine if a number n is a perfect square and return its square root if so. -- This is used instead of sqrt to avoid fixed sized floating point numbers. perfectSqrt :: Integral a => a -> Maybe a perfectSqrt n
| n == 1 = Just 1 | n < 4 = Nothing | otherwise = let search low high = let guess = (low + high) `div` 2 square = guess ^ 2 next | square == n = Just guess | low == guess = Nothing | square < n = search guess high | otherwise = search low guess in next in search 0 n
-- Determine the area of a Heronian triangle if it is one. heronTri :: Integral a => a -> a -> a -> Maybe a heronTri a b c =
let -- Rewrite Heron's formula to factor out the term 16 under the root. areaSq16 = (a + b + c) * (b + c - a) * (a + c - b) * (a + b - c) (areaSq, r) = areaSq16 `divMod` 16 in if r == 0 then perfectSqrt areaSq else Nothing
isPrimitive :: Integral a => a -> a -> a -> a isPrimitive a b c = gcd a (gcd b c)
third (_, _, x, _, _) = x fourth (_, _, _, x, _) = x fifth (_, _, _, _, x) = x
orders :: Ord b => [(a -> b)] -> a -> a -> Ordering orders [f] a b = comparing f a b orders (f:fx) a b =
case comparing f a b of EQ -> orders fx a b n -> n
main :: IO () main = do
let range = [1 .. 200] tris :: [(Integer, Integer, Integer, Integer, Integer)] tris = L.sortBy (orders [fifth, fourth, third]) $ map (\(a, b, c, d, e) -> (a, b, c, d, fromJust e)) $ filter (isJust . fifth) [(a, b, c, a + b + c, heronTri a b c) | a <- range, b <- range, c <- range , a <= b, b <= c, isPrimitive a b c == 1] printTri (a, b, c, d, e) = printf "%3d %3d %3d %9d %4d\n" a b c d e printf "Heronian triangles found: %d\n\n" $ length tris putStrLn " Sides Perimeter Area" mapM_ printTri $ take 10 tris putStrLn "" mapM_ printTri $ filter ((== 210) . fifth) tris</lang>
- Output:
Heronian triangles found: 517 Sides Perimeter Area 3 4 5 12 6 5 5 6 16 12 5 5 8 18 12 4 13 15 32 24 5 12 13 30 30 9 10 17 36 36 3 25 26 54 36 7 15 20 42 42 10 13 13 36 60 8 15 17 40 60 17 25 28 70 210 20 21 29 70 210 12 35 37 84 210 17 28 39 84 210 7 65 68 140 210 3 148 149 300 210
J
Supporting implementation:
<lang J>a=:0&{"1 b=:1&{"1 c=:2&{"1 s=:(a+b+c)%2: A=:2 %: s*(s-a)*(s-b)*(s-c) P=:+/"1 isprimhero=:(0&~:*(=<.@+))@A*1=a+.b+.c
tri=: (/: A,.P,.{:"1) (#~ isprimhero)~./:"1~1+200 200 200#:i.200^3</lang>
Required examples:
<lang J> #tri 517
10{.(,._,.A,.P) tri 3 4 5 _ 6 12 5 5 6 _ 12 16 5 5 8 _ 12 18 4 13 15 _ 24 32 5 12 13 _ 30 30 9 10 17 _ 36 36 3 25 26 _ 36 54 7 15 20 _ 42 42
10 13 13 _ 60 36
8 15 17 _ 60 40
(#~210=A) (,._,.A,.P) tri
17 25 28 _ 210 70 20 21 29 _ 210 70 12 35 37 _ 210 84 17 28 39 _ 210 84
7 65 68 _ 210 140 3 148 149 _ 210 300</lang>
Java
<lang Java> import java.util.ArrayList; public class Heron { public static void main(String[] args) { ArrayList<int[]> list = new ArrayList<int[]>(); for(int c = 1; c <= 200; c++){ for(int b = 1; b <= c; b++){ for(int a = 1; a <= b; a++){ if(gcd(gcd(a, b), c) == 1 && isHeron(heronArea(a, b, c) list.add(new int[]{a, b, c, a + b + c, (int)heronArea(a, b, c)}); } } } sort(list); System.out.printf("Number of primitive Heronian triangles with sides up to 200: %d\n\nFirst ten when ordered by increasing area, then perimeter:\nSides Perimeter Area", list.size()); for(int i = 0; i < 10; i++){ System.out.printf("\n%d x %d x %d %d %d",list.get(i)[0], list.get(i)[1], list.get(i)[2], list.get(i)[3], list.get(i)[4]); } System.out.printf("\n\nArea = 210\nSides Perimeter Area"); for(int i = 0; i < list.size(); i++){ if(list.get(i)[4] == 210) System.out.printf("\n%d x %d x %d %d %d",list.get(i)[0], list.get(i)[1], list.get(i)[2], list.get(i)[3], list.get(i)[4]); } } public static double heronArea(int a, int b, int c){ double s = (a + b + c)/ 2f; return Math.sqrt(s *(s -a)*(s - b)*(s - c)); } public static boolean isHeron(double h){ return h % 1 == 0 && h > 0; } public static int gcd(int a, int b){ int leftover = 1, dividend = a > b ? a : b, divisor = a > b ? b : a; while(leftover != 0){ leftover = dividend % divisor; if(leftover > 0){ dividend = divisor; divisor = leftover; } } return divisor; } public static void sort(ArrayList<int[]> list){ boolean swapped = true; int[] temp; while(swapped){ swapped = false; for(int i = 1; i < list.size(); i++){ if(list.get(i)[4] < list.get(i - 1)[4] || list.get(i)[4] == list.get(i - 1)[4] && list.get(i)[3] < list.get(i - 1)[3]){ temp = list.get(i); list.set(i, list.get(i - 1)); list.set(i - 1, temp); swapped = true; } } } } } </lang>
- Output:
<lang> Number of primitive Heronian triangles with sides up to 200: 517
First ten when ordered by increasing area, then perimeter: Sides Perimeter Area 3 x 4 x 5 12 6 5 x 5 x 6 16 12 5 x 5 x 8 18 12 4 x 13 x 15 32 24 5 x 12 x 13 30 30 9 x 10 x 17 36 36 3 x 25 x 26 54 36 7 x 15 x 20 42 42 10 x 13 x 13 36 60 8 x 15 x 17 40 60
Area = 210 Sides Perimeter Area 17 x 25 x 28 70 210 20 x 21 x 29 70 210 12 x 35 x 37 84 210 17 x 28 x 39 84 210 7 x 65 x 68 140 210 3 x 148 x 149 300 210 </lang>
JavaScript
<lang JavaScript> window.onload = function(){
var list = []; var j = 0; for(var c = 1; c <= 200; c++) for(var b = 1; b <= c; b++) for(var a = 1; a <= b; a++)
if(gcd(gcd(a, b), c) == 1 && isHeron(heronArea(a, b, c))) list[j++] = new Array(a, b, c, a + b + c, heronArea(a, b, c));
sort(list);
document.write("
Primitive Heronian triangles with sides up to 200: " + list.length + "
First ten when ordered by increasing area, then perimeter:
");for(var i = 0; i < 10; i++)document.write(""); document.write("
Sides | Perimeter | Area |
---|---|---|
" + list[i][0] + " x " + list[i][1] + " x " + list[i][2] + " | " + list[i][3] + " | " + list[i][4] + " |
Area = 210
");for(var i = 0; i < list.length; i++)
if(list[i][4] == 210)
document.write("");function heronArea(a, b, c){
var s = (a + b + c)/ 2; return Math.sqrt(s *(s -a)*(s - b)*(s - c));
} function isHeron(h){ return h % 1 == 0 && h > 0; } function gcd(a, b){
var leftover = 1, dividend = a > b ? a : b, divisor = a > b ? b : a; while(leftover != 0){ leftover = dividend % divisor; if(leftover > 0){ dividend = divisor; divisor = leftover; } } return divisor;
} function sort(list){
var swapped = true; var temp = []; while(swapped){ swapped = false; for(var i = 1; i < list.length; i++){ if(list[i][4] < list[i - 1][4] || list[i][4] == list[i - 1][4] && list[i][3] < list[i - 1][3]){ temp = list[i]; list[i] = list[i - 1]; list[i - 1] = temp; swapped = true; } } }
}
} </lang>
- Output:
<lang> Primitive Heronian triangles with sides up to 200: 517
First ten when ordered by increasing area, then perimeter: Sides Perimeter Area 3 x 4 x 5 12 6 5 x 5 x 6 16 12 5 x 5 x 8 18 12 4 x 13 x 15 32 24 5 x 12 x 13 30 30 9 x 10 x 17 36 36 3 x 25 x 26 54 36 7 x 15 x 20 42 42 10 x 13 x 13 36 60 8 x 15 x 17 40 60
Area = 210 Sides Perimeter Area 17 x 25 x 28 70 210 20 x 21 x 29 70 210 12 x 35 x 37 84 210 17 x 28 x 39 84 210 7 x 65 x 68 140 210 3 x 148 x 149 300 210 </lang>
jq
<lang jq># input should be an array of the lengths of the sides def hero:
(add/2) as $s | ($s*($s - .[0])*($s - .[1])*($s - .[2])) as $a2 | if $a2 > 0 then ($a2 | sqrt) else 0 end;
def is_heronian:
hero as $h | $h > 0 and ($h|floor) == $h;
def gcd3(x; y; z):
# subfunction expects [a,b] as input def rgcd: if .[1] == 0 then .[0] else [.[1], .[0] % .[1]] | rgcd end; [ ([x,y] | rgcd), z ] | rgcd;
def task(maxside):
def rjust(width): tostring | " " * (width - length) + .; [ range(1; maxside+1) as $c | range(1; $c+1) as $b | range(1; $b+1) as $a | if ($a + $b) > $c and gcd3($a; $b; $c) == 1 then [$a,$b,$c] | if is_heronian then . else empty end else empty end ]
# sort by increasing area, perimeter, then sides | sort_by( [ hero, add, .[2] ] ) | "The number of primitive Heronian triangles with sides up to \(maxside): \(length)", "The first ten when ordered by increasing area, then perimeter, then maximum sides:", " perimeter area", (.[0:10][] | "\(rjust(11)) \(add | rjust(3)) \(hero | rjust(4))" ), "All those with area 210, ordered as previously:", " perimeter area", ( .[] | select( hero == 210 ) | "\(rjust(11)) \(add|rjust(3)) \(hero|rjust(4))" ) ;
task(200)</lang>
- Output:
<lang sh>$ time jq -n -r -f heronian.jq The number of primitive Heronian triangles with sides up to 200: 517 The first ten when ordered by increasing area, then perimeter, then maximum sides:
perimeter area [3,4,5] 12 6 [5,5,6] 16 12 [5,5,8] 18 12 [4,13,15] 32 24 [5,12,13] 30 30 [9,10,17] 36 36 [3,25,26] 54 36 [7,15,20] 42 42 [10,13,13] 36 60 [8,15,17] 40 60
All those with area 210, ordered as previously:
perimeter area [17,25,28] 70 210 [20,21,29] 70 210 [12,35,37] 84 210 [17,28,39] 84 210 [7,65,68] 140 210
[3,148,149] 300 210</lang>
Nim
<lang nim>import math, algorithm, strfmt, sequtils
type
HeronianTriangle = tuple a: int b: int c: int s: float A: int
proc `$` (t: HeronianTriangle): string =
fmt("{:3d}, {:3d}, {:3d}\t{:3.3f}\t{:3d}", t.a, t.b, t.c, t.s, t.A)
proc hero(a:int, b:int, c:int): tuple[s, A: float] =
let s: float = (a + b + c) / 2 result = (s, sqrt( s * (s - float(a)) * (s - float(b)) * (s - float(c)) ))
proc isHeronianTriangle(x: float): bool = ceil(x) == x and x.toInt > 0
proc gcd(x: int, y: int): int =
var (dividend, divisor) = if x > y: (x, y) else: (y, x) remainder = dividend mod divisor while remainder != 0: dividend = divisor divisor = remainder remainder = dividend mod divisor result = divisor
var list = newSeq[HeronianTriangle]() const max = 200
for c in 1..max:
for b in 1..c: for a in 1..b: let (s, A) = hero(a, b, c) if isHeronianTriangle(A) and gcd(a, gcd(b, c)) == 1: let t:HeronianTriangle = (a, b, c, s, A.toInt) list.add(t)
echo "Numbers of Heronian Triangle : ", list.len
list.sort do (x, y: HeronianTriangle) -> int:
result = cmp(x.A, y.A) if result == 0: result = cmp(x.s, y.s) if result == 0: result = cmp(max(x.a, x.b, x.c), max(y.a, y.b, y.c))
echo "Ten first Heronian triangle ordered : " echo "Sides Perimeter Area" for t in list[0 .. <10]:
echo t
echo "Heronian triangle ordered with Area 210 : " echo "Sides Perimeter Area" for t in list.filter(proc (x: HeronianTriangle): bool = x.A == 210):
echo t</lang>
- Output:
Numbers of Heronian Triangle : 517 Ten first Heronian triangle ordered : Sides Perimeter Area 3, 4, 5 6.000 6 5, 5, 6 8.000 12 5, 5, 8 9.000 12 4, 13, 15 16.000 24 5, 12, 13 15.000 30 9, 10, 17 18.000 36 3, 25, 26 27.000 36 7, 15, 20 21.000 42 10, 13, 13 18.000 60 8, 15, 17 20.000 60 Heronian triangle ordered with Area 210 : Sides Perimeter Area 17, 25, 28 35.000 210 20, 21, 29 35.000 210 12, 35, 37 42.000 210 17, 28, 39 42.000 210 7, 65, 68 70.000 210 3, 148, 149 150.000 210
ooRexx
Derived from REXX with some changes <lang rexx>/*REXX pgm generates primitive Heronian triangles by side length & area.*/
Call time 'R' Numeric Digits 12 Parse Arg mxs area list If mxs = Then mxs =200 If area= Then area=210 If list= Then list=10 tx='primitive Heronian triangles' Call heronian mxs /* invoke sub with max SIDES. */ Say nt tx 'found with side length up to' mxs "(inclusive)." Call show '2' Call show '3' Say time('E') 'seconds elapsed' Exit
heronian:
abc.=0 /* abc.ar.p.* contains 'a b c' for area ar and perimeter p */ nt=0 /* number of triangles found */ min.= max.= mem.=0 ln=length(mxs) Do a=3 To mxs Do b=a To mxs ab=a+b Do c=b To mxs If hgcd(a,b,c)=1 Then Do /* GCD=1 */ ar=heron_area() If pos('.',ar)=0 Then Do /* is an integer */ nt=nt+1 /* a primitive Heronian triangle.*/ Call minmax '0P',p Call minmax '0A',a per=ab+c abc_ar=right(per,4) right(a,4) right(b,4) right(c,4), right(ar,5) Call mem abc_ar End End End End End /* say 'min.p='min.0p say 'max.p='max.0p say 'min.a='min.0a say 'max.a='max.0a */ Return nt
hgcd: Procedure
Parse Arg x Do j=2 For 2 y=arg(j) Do Until _==0 _=x//y x=y y=_ End End Return x
minmax:
Parse Arg which,x If min.which= Then Do min.which=x max.which=x End Else Do min.which=min(min.which,x) max.which=max(max.which,x) End --Say which min.which '-' max.which Return
heron_area:
p=ab+c /* perimeter */ s=p/2 ar2=s*(s-a)*(s-b)*(s-c) /* area**2 */ If pos(right(ar2,1),'014569')=0 Then /* ar2 cannot be */ Return '.' /* square of an integer*/ If ar2>0 Then ar=sqrt(ar2) /* area */ Else ar='.' Return ar
show: Parse Arg which
Say Select When which='2' Then Do Say 'Listing of the first' list tx":" Do i=1 To list Call ot i,mem.i End End When which='3' Then Do Say 'Listing of the' tx "with area=210" j=0 Do i=1 To mem.0 Parse Var mem.i per a b c area If area=210 Then Do j=j+1 Call ot j,mem.i End End End End Return
ot: Parse Arg k,mem
Parse Var mem per a b c area Say right(k,9)' area:'right(area,6)||, ' perimeter:'right(per,4)' sides:', right(a,3) right(b,3) right(c,3) Return
mem:
Parse Arg e Do i=1 To mem.0 If mem.i>>e Then Leave End Do j=mem.0 to i By -1 j1=j+1 mem.j1=mem.j End mem.i=e mem.0=mem.0+1 Return
/* for "Classic" REXX sqrt: procedure; parse arg x;if x=0 then return 0;d=digits();numeric digits 11 numeric form; parse value format(x,2,1,,0) 'E0' with g 'E' _ .; g=g*.5'E'_%2 p=d+d%4+2; m.=11; do j=0 while p>9; m.j=p; p=p%2+1; end; do k=j+5 to 0 by -1 if m.k>11 then numeric digits m.k;g=.5*(g+x/g);end;numeric digits d;return g/1
- /
/* for ooRexx */
- requires rxmath library
- routine sqrt
Return rxCalcSqrt(arg(1),14)</lang>
- Output:
517 primitive Heronian triangles found with side length up to 200 (inclusive). Listing of the first 10 primitive Heronian triangles: 1 area: 6 perimeter: 12 sides: 3 4 5 2 area: 12 perimeter: 16 sides: 5 5 6 3 area: 12 perimeter: 18 sides: 5 5 8 4 area: 30 perimeter: 30 sides: 5 12 13 5 area: 24 perimeter: 32 sides: 4 13 15 6 area: 36 perimeter: 36 sides: 9 10 17 7 area: 60 perimeter: 36 sides: 10 13 13 8 area: 60 perimeter: 40 sides: 8 15 17 9 area: 42 perimeter: 42 sides: 7 15 20 10 area: 84 perimeter: 42 sides: 13 14 15 Listing of the primitive Heronian triangles with area=210 1 area: 210 perimeter: 70 sides: 17 25 28 2 area: 210 perimeter: 70 sides: 20 21 29 3 area: 210 perimeter: 84 sides: 12 35 37 4 area: 210 perimeter: 84 sides: 17 28 39 5 area: 210 perimeter: 140 sides: 7 65 68 6 area: 210 perimeter: 300 sides: 3 148 149 26.054000 seconds elapsed
Perl
<lang perl>use strict; use warnings; use List::Util qw(max);
sub gcd { $_[1] == 0 ? $_[0] : gcd($_[1], $_[0] % $_[1]) }
sub hero {
my ($a, $b, $c) = @_[0,1,2]; my $s = ($a + $b + $c) / 2; sqrt $s*($s - $a)*($s - $b)*($s - $c);
}
sub heronian_area {
my $hero = hero my ($a, $b, $c) = @_[0,1,2]; sprintf("%.0f", $hero) eq $hero ? $hero : 0
}
sub primitive_heronian_area {
my ($a, $b, $c) = @_[0,1,2]; heronian_area($a, $b, $c) if 1 == gcd $a, gcd $b, $c;
}
sub show {
print " Area Perimeter Sides\n"; for (@_) { my ($area, $perim, $c, $b, $a) = @$_;
printf "%7d %9d %d×%d×%d\n", $area, $perim, $a, $b, $c;
}
}
sub main {
my $maxside = shift // 200; my $first = shift // 10; my $witharea = shift // 210; my @h; for my $c (1 .. $maxside) {
for my $b (1 .. $c) { for my $a ($c - $b + 1 .. $b) { if (my $area = primitive_heronian_area $a, $b, $c) { push @h, [$area, $a+$b+$c, $c, $b, $a]; } } }
} @h = sort {
$a->[0] <=> $b->[0] or $a->[1] <=> $b->[1] or max(@$a[2,3,4]) <=> max(@$b[2,3,4])
} @h; printf "Primitive Heronian triangles with sides up to %d: %d\n", $maxside, scalar @h; print "First:\n"; show @h[0 .. $first - 1]; print "Area $witharea:\n"; show grep { $_->[0] == $witharea } @h;
}
&main();</lang>
- Output:
Primitive Heronian triangles with sides up to 200: 517 First: Area Perimeter Sides 6 12 3×4×5 12 16 5×5×6 12 18 5×5×8 24 32 4×13×15 30 30 5×12×13 36 36 9×10×17 36 54 3×25×26 42 42 7×15×20 60 36 10×13×13 60 40 8×15×17 Area 210: Area Perimeter Sides 210 70 17×25×28 210 70 20×21×29 210 84 12×35×37 210 84 17×28×39 210 140 7×65×68 210 300 3×148×149
Perl 6
<lang perl6>sub hero($a, $b, $c) {
my $s = ($a + $b + $c) / 2; my $a2 = $s * ($s - $a) * ($s - $b) * ($s - $c); $a2.sqrt;
}
sub heronian-area($a, $b, $c) {
$_ when Int given hero($a, $b, $c).narrow;
}
sub primitive-heronian-area($a, $b, $c) {
heronian-area $a, $b, $c if 1 == [gcd] $a, $b, $c;
}
sub show {
say " Area Perimeter Sides"; for @_ -> [$area, $perim, $c, $b, $a] {
printf "%6d %6d %12s\n", $area, $perim, "$a×$b×$c";
}
}
sub MAIN ($maxside = 200, $first = 10, $witharea = 210) {
my \h = sort gather for 1 .. $maxside -> $c { for 1 .. $c -> $b { for $c - $b + 1 .. $b -> $a { if primitive-heronian-area($a,$b,$c) -> $area { take [$area, $a+$b+$c, $c, $b, $a]; } } } }
say "Primitive Heronian triangles with sides up to $maxside: ", +h;
say "\nFirst $first:"; show h[^$first];
say "\nArea $witharea:"; show h.grep: *[0] == $witharea;
}</lang>
- Output:
Primitive Heronian triangles with sides up to 200: 517 First 10: Area Perimeter Sides 6 12 3×4×5 12 16 5×5×6 12 18 5×5×8 24 32 4×13×15 30 30 5×12×13 36 36 9×10×17 36 54 3×25×26 42 42 7×15×20 60 36 10×13×13 60 40 8×15×17 Area 210: Area Perimeter Sides 210 70 17×25×28 210 70 20×21×29 210 84 12×35×37 210 84 17×28×39 210 140 7×65×68 210 300 3×148×149
PowerShell
<lang powershell> function Get-Gcd($a, $b){
if($a -ge $b){ $dividend = $a $divisor = $b } else{ $dividend = $b $divisor = $a } $leftover = 1 while($leftover -ne 0){ $leftover = $dividend % $divisor if($leftover -ne 0){
$dividend = $divisor $divisor = $leftover }
} $divisor
} function Is-Heron($heronArea){
$heronArea -gt 0 -and $heronArea % 1 -eq 0
} function Get-HeronArea($a, $b, $c){
$s = ($a + $b + $c) / 2 [math]::Sqrt($s * ($s - $a) * ($s - $b) * ($s - $c))
} $result = @() foreach ($c in 1..200){
for($b = 1; $b -le $c; $b++){ for($a = 1; $a -le $b; $a++){ if((Get-Gcd $c (Get-Gcd $b $a)) -eq 1 -and (Is-Heron(Get-HeronArea $a $b $c))){ $result += @(,@($a, $b, $c,($a + $b + $c), (Get-HeronArea $a $b $c))) } } }
} $result = $result | sort-object @{Expression={$_[4]}}, @{Expression={$_[3]}}, @{Expression={$_[2]}} "Primitive Heronian triangles with sides up to 200: $($result.length)`nFirst ten when ordered by increasing area, then perimeter,then maximum sides:`nSides`t`t`t`tPerimeter`tArea" for($i = 0; $i -lt 10; $i++){ "$($result[$i][0])`t$($result[$i][1])`t$($result[$i][2])`t`t`t$($result[$i][3])`t`t`t$($result[$i][4])" } "`nArea = 210`nSides`t`t`t`tPerimeter`tArea" foreach($i in $result){
if($i[4] -eq 210){ "$($i[0])`t$($i[1])`t$($i[2])`t`t`t$($i[3])`t`t`t$($i[4])" }
} </lang>
- Output:
<lang> Primitive Heronian triangles with sides up to 200: 517
First ten when ordered by increasing area, then perimeter,then maximum sides: Sides Perimeter Area 3 4 5 12 6 5 5 6 16 12 5 5 8 18 12 4 13 15 32 24 5 12 13 30 30 9 10 17 36 36 3 25 26 54 36 7 15 20 42 42 10 13 13 36 60 8 15 17 40 60
Area = 210 Sides Perimeter Area 17 25 28 70 210 20 21 29 70 210 12 35 37 84 210 17 28 39 84 210 7 65 68 140 210 3 148 149 300 210 </lang>
Python
<lang python>from math import sqrt from fractions import gcd from itertools import product
def hero(a, b, c):
s = (a + b + c) / 2 a2 = s*(s-a)*(s-b)*(s-c) return sqrt(a2) if a2 > 0 else 0
def is_heronian(a, b, c):
a = hero(a, b, c) return a > 0 and a.is_integer()
def gcd3(x, y, z):
return gcd(gcd(x, y), z)
if __name__ == '__main__':
maxside = 200 h = [(a, b, c) for a,b,c in product(range(1, maxside + 1), repeat=3) if a <= b <= c and a + b > c and gcd3(a, b, c) == 1 and is_heronian(a, b, c)] h.sort(key = lambda x: (hero(*x), sum(x), x[::-1])) # By increasing area, perimeter, then sides print('Primitive Heronian triangles with sides up to %i:' % maxside, len(h)) print('\nFirst ten when ordered by increasing area, then perimeter,then maximum sides:') print('\n'.join(' %14r perim: %3i area: %i' % (sides, sum(sides), hero(*sides)) for sides in h[:10])) print('\nAll with area 210 subject to the previous ordering:') print('\n'.join(' %14r perim: %3i area: %i' % (sides, sum(sides), hero(*sides)) for sides in h if hero(*sides) == 210))</lang>
- Output:
Primitive Heronian triangles with sides up to 200: 517 First ten when ordered by increasing area, then perimeter,then maximum sides: (3, 4, 5) perim: 12 area: 6 (5, 5, 6) perim: 16 area: 12 (5, 5, 8) perim: 18 area: 12 (4, 13, 15) perim: 32 area: 24 (5, 12, 13) perim: 30 area: 30 (9, 10, 17) perim: 36 area: 36 (3, 25, 26) perim: 54 area: 36 (7, 15, 20) perim: 42 area: 42 (10, 13, 13) perim: 36 area: 60 (8, 15, 17) perim: 40 area: 60 All with area 210 subject to the previous ordering: (17, 25, 28) perim: 70 area: 210 (20, 21, 29) perim: 70 area: 210 (12, 35, 37) perim: 84 area: 210 (17, 28, 39) perim: 84 area: 210 (7, 65, 68) perim: 140 area: 210 (3, 148, 149) perim: 300 area: 210
Racket
<lang>#lang racket (require xml/xml data/order)
- Returns the area of triangle sides a, b, c
(define (A a b c)
(define s (/ (+ a b c) 2)) ; where s=\frac{a+b+c}{2}. (sqrt (* s (- s a) (- s b) (- s c)))) ; A = \sqrt{s(s-a)(s-b)(s-c)}
- Returns same as A iff a, b, c and A are integers; #f otherwise
(define (heronian?-area a b c)
(and (integer? a) (integer? b) (integer? c) (let ((h (A a b c))) (and (integer? h) h))))
- Returns same as heronian?-area, with the additional condition that (gcd a b c) = 1
(define (primitive-heronian?-area a b c)
(and (= 1 (gcd a b c)) (heronian?-area a b c)))
(define (generate-heronian-triangles max-side)
(for*/list ((a (in-range 1 (add1 max-side))) (b (in-range 1 (add1 a))) (c (in-range 1 (add1 b))) #:when (< a (+ b c)) (h (in-value (primitive-heronian?-area a b c))) #:when h) (define rv (vector h (+ a b c) (sort (list a b c) >))) ; datum-order can sort this for the tables rv))
- Order the triangles by first increasing area, then by increasing perimeter,
- then by increasing maximum side lengths
(define (tri<? t1 t2)
(eq? '< (datum-order t1 t2)))
(define triangle->tds (match-lambda [`#(,h ,p ,s) `((td ,(~a s)) (td ,(~a p)) (td ,(~a h)))]))
(define (triangles->table ts)
`(table (tr (th "#") (th "sides") (th "perimiter") (th "area")) "\n" ,@(for/list ((i (in-naturals 1)) (t ts)) `(tr (td ,(~a i)) ,@(triangle->tds t) "\n"))))
(define (sorted-triangles-table triangles)
(triangles->table (sort triangles tri<?)))
(module+ main
(define ts (generate-heronian-triangles 200)) (define div-out `(div (p "number of primitive triangles found with perimeter "le" 200 = " ,(~a (length ts))) "\n" ;; Show the first ten ordered triangles in a table of sides, perimeter, and area. ,(sorted-triangles-table (take (sort ts tri<?) 10)) "\n" ;; Show a similar ordered table for those triangles with area = 210 ,(sorted-triangles-table (sort (filter (match-lambda [(vector 210 _ _) #t] [_ #f]) ts) tri<?)))) (displayln (xexpr->string div-out)))</lang>
This program generates HTML, so the output is inline with the page, not in a <pre>
block.
- Output:
number of primitive triangles found with perimeter ≤ 200 = 517
Sides | Perimeter | Area |
---|---|---|
" + list[i][0] + " x " + list[i][1] + " x " + list[i][2] + " | " + list[i][3] + " | " + list[i][4] + " |
# | sides | perimiter | area |
---|---|---|---|
1 | (5 4 3) | 12 | 6 |
2 | (6 5 5) | 16 | 12 |
3 | (8 5 5) | 18 | 12 |
4 | (15 13 4) | 32 | 24 |
5 | (13 12 5) | 30 | 30 |
6 | (17 10 9) | 36 | 36 |
7 | (26 25 3) | 54 | 36 |
8 | (20 15 7) | 42 | 42 |
9 | (13 13 10) | 36 | 60 |
10 | (17 15 8) | 40 | 60 |
# | sides | perimiter | area |
---|---|---|---|
1 | (28 25 17) | 70 | 210 |
2 | (29 21 20) | 70 | 210 |
3 | (37 35 12) | 84 | 210 |
4 | (39 28 17) | 84 | 210 |
5 | (68 65 7) | 140 | 210 |
6 | (149 148 3) | 300 | 210 |
REXX
Programming notes:
The hGCD subroutine is a specialized version of a GCD routine in that it doesn't check for non-positive integers.
Also, a fair amount of code was added to optimize the speed (at the expense of program simplicity); by thoughtful ordering of
the "elimination" checks, and also the use of an integer version of a SQRT subroutine, the execution time was greatly reduced
(by a factor of six).
Note that the iSQRT subroutine doesn't use floating point.
The REXX statement (line 20) if pos(.,_)\==0 isn't normally used for a general-purpose check if a number is an integer (or not),
this version was used because it's faster than the usual statement: if \datatype(_,'Whole') and because the number is well-formed.
This REXX program doesn't need to explicitly sort the triangles. <lang rexx>/*REXX pgm generates primitive Heronian triangles by side length & area.*/ parse arg N first area . /*get optional N (sides). */ if N== | N==',' then N=200 /*maybe use the default. */ if first== | first==',' then first= 10 /* " " " " */ if area== | area==',' then area=210 /* " " " " */ numeric digits 99; numeric digits max(9, 1+length(N**5)) /*ensure 'nuff*/ call Heron /*invoke Heron subroutine. */ say # ' primitive Heronian triangles found with sides up to ' N " (inclusive)." call show , 'listing of the first ' first ' primitive Heronian triangles:' call show area, 'listing of the (above) found primitive Heronian triangles with an area of ' area exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────HERON subroutine────────────────────*/ Heron: @.=.; #=0; minP=9e9; maxP=0; minA=9e9; maxA=0; Ln=length(N)
#.=0; #.2=1 #.3=1; #.7=1; #.8=1 /*¬good √.*/ do a=3 to N /*start at a minimum side length.*/ ev= \ (a//2); inc=1+ev /*if A is even, B & C must be odd*/ do b=a+ev to N by inc; ab=a+b /*AB: is used for summing below.*/ do c=b to N by inc; p=ab+c; s=p/2 /*calc Perimeter, S*/ _=s*(s-a)*(s-b)*(s-c); if _<=0 then iterate /*_ isn't positive.*/ if pos(.,_)\==0 then iterate /*not an integer. */ parse var _ -1 q ; if #.q then iterate /*not good square. */ ar=iSQRT(_); if ar*ar\==_ then iterate /*area not integer.*/ if hGCD(a,b,c)\==1 then iterate /*GCD of sides ¬1. */ #=#+1 /*got prim. H. tri.*/ minP=min( p,minP); maxP=max( p,maxP); Lp=length(maxP) minA=min(ar,minA); maxA=max(ar,maxA); La=length(maxA); @.ar= if @.ar.p.0==. then @.ar.p.0=0; _=@.ar.p.0+1 /*bump triangle ctr*/ @.ar.p.0=_; @.ar.p._=right(a,Ln) right(b,Ln) right(c,Ln) /*unique*/ end /*c*/ /* [↑] keep each unique P items.*/ end /*b*/ end /*a*/
return # /*return # of Heronian triangles.*/ /*──────────────────────────────────HGCD subroutine─────────────────────*/ hGCD: procedure; parse arg x; do j=2 for 2 /*sub handles exactly 3 args*/
y=arg(j); do until _==0; _=x//y; x=y; y=_; end; end; return x
/*──────────────────────────────────ISQRT subroutine────────────────────*/ iSQRT: procedure; parse arg x; x=x%1; if x==0 | x==1 then return x; q=1
do while q<=x; q=q*4; end; r=0 /*Q will be > X at loop end.*/ do while q>1 ; q=q%4; _=x-r-q; r=r%2; if _>=0 then do;x=_;r=r+q;end; end
return r /* R is a postive integer. */ /*──────────────────────────────────SHOW subroutine─────────────────────*/ show: m=0; say; say; parse arg ae; say arg(2); if ae\== then first=9e9 say; y=left(,9) /* [↓] skip the nothings. */
do i=minA to maxA; if @.i==. then iterate if ae\== & i\==ae then iterate /*Area specified? Then check*/ do j=minP to maxP until m>=first /*only list FIRST entries.*/ if @.i.j.0==. then iterate /*Not defined? Then skip it.*/ do k=1 for @.i.j.0; m=m+1 /*visit each perimeter entry*/ say right(m,9) y'area:' right(i,La) y"perimeter:" right(j,Lp) y'sides:' @.i.j.k end /*k*/ end /*j*/ /* [↑] use known perimeters*/ end /*i*/ /* [↑] show found triangles*/
return</lang>
- Output:
517 primitive Heronian triangles found with sides up to 200 (inclusive). listing of the first 10 primitive Heronian triangles: 1 area: 6 perimeter: 12 sides: 3 4 5 2 area: 12 perimeter: 16 sides: 5 5 6 3 area: 12 perimeter: 18 sides: 5 5 8 4 area: 24 perimeter: 32 sides: 4 13 15 5 area: 30 perimeter: 30 sides: 5 12 13 6 area: 36 perimeter: 36 sides: 9 10 17 7 area: 36 perimeter: 54 sides: 3 25 26 8 area: 42 perimeter: 42 sides: 7 15 20 9 area: 60 perimeter: 36 sides: 10 13 13 10 area: 60 perimeter: 40 sides: 8 15 17 listing of the (above) found primitive Heronian triangles with an area of 210 1 area: 210 perimeter: 70 sides: 17 25 28 2 area: 210 perimeter: 70 sides: 20 21 29 3 area: 210 perimeter: 84 sides: 12 35 37 4 area: 210 perimeter: 84 sides: 17 28 39 5 area: 210 perimeter: 140 sides: 7 65 68 6 area: 210 perimeter: 300 sides: 3 148 149
Ruby
<lang ruby>class Triangle
def self.valid?(a,b,c) # class method short, middle, long = [a, b, c].sort short + middle > long end attr_reader :sides, :perimeter, :area def initialize(a,b,c) @sides = [a, b, c].sort @perimeter = a + b + c s = @perimeter / 2.0 @area = Math.sqrt(s * (s - a) * (s - b) * (s - c)) end def heronian? area == area.to_i end def <=>(other) [area, perimeter, sides] <=> [other.area, other.perimeter, other.sides] end def to_s "%-11s%6d%8.1f" % [sides.join('x'), perimeter, area] end
end
max, area = 200, 210 prim_triangles = [] 1.upto(max) do |a|
a.upto(max) do |b| b.upto(max) do |c| next if a.gcd(b).gcd(c) > 1 prim_triangles << Triangle.new(a, b, c) if Triangle.valid?(a, b, c) end end
end
sorted = prim_triangles.select(&:heronian?).sort
puts "Primitive heronian triangles with sides upto #{max}: #{sorted.size}" puts "\nsides perim. area" puts sorted.first(10).map(&:to_s) puts "\nTriangles with an area of: #{area}" sorted.each{|tr| puts tr if tr.area == area}</lang>
- Output:
Primitive heronian triangles with sides upto 200: 517 sides perim. area 3x4x5 12 6.0 5x5x6 16 12.0 5x5x8 18 12.0 4x13x15 32 24.0 5x12x13 30 30.0 9x10x17 36 36.0 3x25x26 54 36.0 7x15x20 42 42.0 10x13x13 36 60.0 8x15x17 40 60.0 Triangles with an area of: 210 17x25x28 70 210.0 20x21x29 70 210.0 12x35x37 84 210.0 17x28x39 84 210.0 7x65x68 140 210.0 3x148x149 300 210.0
zkl
<lang zkl>fcn hero(a,b,c){ //--> area (float)
s,a2:=(a + b + c).toFloat()/2, s*(s - a)*(s - b)*(s - c); (a2 > 0) and a2.sqrt() or 0.0
} fcn isHeronian(a,b,c){
A:=hero(a,b,c); (A>0) and A.modf()[1].closeTo(0.0,1.0e-6) and A //--> area or False
}</lang> <lang zkl>const MAX_SIDE=200; heros:=Sink(List); foreach a,b,c in ([1..MAX_SIDE],[a..MAX_SIDE],[b..MAX_SIDE]){
if(a.gcd(b).gcd(c)==1 and (h:=isHeronian(a,b,c))) heros.write(T(h,a+b+c,a,b,c));
} // sort by increasing area, perimeter, then sides heros=heros.close().sort(fcn([(h1,p1,_,_,c1)],[(h2,p2,_,_,c2)]){
if(h1!=h2) return(h1<h2); if(p1!=p2) return(p1<p2); c1<c2;
});
println("Primitive Heronian triangles with sides up to %d: ".fmt(MAX_SIDE),heros.len());
println("First ten when ordered by increasing area, then perimeter,then maximum sides:"); println("Area Perimeter Sides"); heros[0,10].pump(fcn(phabc){ "%3s %8d %3dx%dx%d".fmt(phabc.xplode()).println() });
println("\nAll with area 210 subject to the previous ordering:"); println("Area Perimeter Sides"); heros.filter(fcn([(h,_)]){ h==210 })
.pump(fcn(phabc){ "%3s %8d %3dx%dx%d".fmt(phabc.xplode()).println() });</lang>
- Output:
Primitive Heronian triangles with sides up to 200: 517 First ten when ordered by increasing area, then perimeter,then maximum sides: Area Perimeter Sides 6 12 3x4x5 12 16 5x5x6 12 18 5x5x8 24 32 4x13x15 30 30 5x12x13 36 36 9x10x17 36 54 3x25x26 42 42 7x15x20 60 36 10x13x13 60 40 8x15x17 All with area 210 subject to the previous ordering: Area Perimeter Sides 210 70 17x25x28 210 70 20x21x29 210 84 12x35x37 210 84 17x28x39 210 140 7x65x68 210 300 3x148x149