I am sure you know what Pythagorean triples are, in the extremely unlikely case that you don't know:
A Pythagorean triple consists of three positive integers a, b, and c, such that $$a^2 + b^2 = c^2$$
I have written four functions, the first one is a brute-force solution that gets all possible unique combinations of numbers within given limit, and check if the square root of the sum of the squares of the two numbers is an integer.
The second one uses the same idea, but in Pythagorean triples a and b can't be both odd, so it only checks combinations of odd numbers and even numbers, and unique combinations of even numbers.
The third one and fourth one both use Euclid's formula:
$$a = m^2 - n^2; b = 2mn; c = m^2 + n^2$$
The third one generates all possible triples that can be generated using Euclid's formula such that c <= limit.
The last one generates all primitive triples such that c <= limit.
With 100 as limit, the first one and second one both generate 63 triples. The third one generates 27 triples and the last one generates 16.
Out of the 100 triples generated by brute-force, 52 of them satisfy c <= 100, so the second method failed to generate 25 triples.
Code
function pythagorean_triple_v0(n) {
const triples = []
for (let a=1; a<=n; a++) {
for (let b=a+1; b<=n; b++) {
let c = (a**2 + b**2)**.5
if (Number.isInteger(c)) {
triples.push([a, b, parseInt(c)])
}
}
}
return triples
}
function pythagorean_triple_v1(n) {
const triples = []
lim = Math.round(n/2)
let odd = Array.from({length: n}, (x, i) => 1+2*i)
let even = Array.from({length: n}, (x, i) => (1+i)*2)
for (let i=0; i<lim; i++) {
let a = odd[i]
for (let j=0; j<lim; j++) {
let b = even[j]
let c = (a**2 + b**2)**.5
if (Number.isInteger(c)) {
triples.push([a, b, parseInt(c)])
}
}
}
for (let i=0; i<lim; i++) {
let a = even[i]
for (let j=i+1; j<lim; j++) {
let b = even[j]
let c = (a**2 + b**2)**.5
if (Number.isInteger(c)) {
triples.push([a, b, parseInt(c)])
}
}
}
return triples
}
function pythagorean_triple_v2(lim) {
const triples = []
let a, b, c = 0;
let m = 2;
while (c < lim) {
for(let n = 1; n < m; n++) {
a = m * m - n * n;
b = 2 * m * n;
c = m * m + n * n;
if (c > lim) {
break
}
triples.push([a, b, c])
}
m++;
}
return triples
}
function gcd(a,b) {
a = Math.abs(a);
b = Math.abs(b);
if (b > a) {
var c = a;
a = b;
b = c;
}
while (true) {
if (!b) {
return a
};
a %= b;
if (!a) {
return b
};
b %= a;
}
}
function pythagorean_triple_v3(lim) {
const triples = []
let n, m;
n = 1; m = 2
while (m * m + 1 < lim) {
if (n >= m) {
n = m%2
m = m+1
}
let z = m * m + n * n
if (z >= lim) {
n = m;
continue;
}
if (gcd(n,m) == 1) {
triples.push([m * m - n * n, 2 * m * n, z])
}
n += 2
}
return triples
}
function timeIt(func, lim) {
let start = Date.now()
for (let i = 0; i < 10000; i++) {
func(lim)
}
let end = Date.now()
console.log(func, lim, (end - start)/1e7)
}
console.log(pythagorean_triple_v0(100))
console.log(pythagorean_triple_v1(100))
console.log(pythagorean_triple_v2(100))
console.log(pythagorean_triple_v3(100))
timeIt(pythagorean_triple_v0, 100)
timeIt(pythagorean_triple_v1, 100)
timeIt(pythagorean_triple_v2, 100)
timeIt(pythagorean_triple_v3, 100)
pythagorean_triple_v0(100).length
pythagorean_triple_v1(100).length
pythagorean_triple_v2(100).length
pythagorean_triple_v3(100).length
var count = 0
for (let [a, b, c] of pythagorean_triple_v0(100)) {
if (c <= 100) {count += 1}
}
console.log(count - pythagorean_triple_v2(100).length)
Console output
> console.log(pythagorean_triple_v0(100))
[
[ 3, 4, 5 ], [ 5, 12, 13 ], [ 6, 8, 10 ],
[ 7, 24, 25 ], [ 8, 15, 17 ], [ 9, 12, 15 ],
[ 9, 40, 41 ], [ 10, 24, 26 ], [ 11, 60, 61 ],
[ 12, 16, 20 ], [ 12, 35, 37 ], [ 13, 84, 85 ],
[ 14, 48, 50 ], [ 15, 20, 25 ], [ 15, 36, 39 ],
[ 16, 30, 34 ], [ 16, 63, 65 ], [ 18, 24, 30 ],
[ 18, 80, 82 ], [ 20, 21, 29 ], [ 20, 48, 52 ],
[ 20, 99, 101 ], [ 21, 28, 35 ], [ 21, 72, 75 ],
[ 24, 32, 40 ], [ 24, 45, 51 ], [ 24, 70, 74 ],
[ 25, 60, 65 ], [ 27, 36, 45 ], [ 28, 45, 53 ],
[ 28, 96, 100 ], [ 30, 40, 50 ], [ 30, 72, 78 ],
[ 32, 60, 68 ], [ 33, 44, 55 ], [ 33, 56, 65 ],
[ 35, 84, 91 ], [ 36, 48, 60 ], [ 36, 77, 85 ],
[ 39, 52, 65 ], [ 39, 80, 89 ], [ 40, 42, 58 ],
[ 40, 75, 85 ], [ 40, 96, 104 ], [ 42, 56, 70 ],
[ 45, 60, 75 ], [ 48, 55, 73 ], [ 48, 64, 80 ],
[ 48, 90, 102 ], [ 51, 68, 85 ], [ 54, 72, 90 ],
[ 56, 90, 106 ], [ 57, 76, 95 ], [ 60, 63, 87 ],
[ 60, 80, 100 ], [ 60, 91, 109 ], [ 63, 84, 105 ],
[ 65, 72, 97 ], [ 66, 88, 110 ], [ 69, 92, 115 ],
[ 72, 96, 120 ], [ 75, 100, 125 ], [ 80, 84, 116 ]
]
undefined
> console.log(pythagorean_triple_v1(100))
[
[ 3, 4, 5 ], [ 5, 12, 13 ], [ 7, 24, 25 ],
[ 9, 12, 15 ], [ 9, 40, 41 ], [ 11, 60, 61 ],
[ 13, 84, 85 ], [ 15, 8, 17 ], [ 15, 20, 25 ],
[ 15, 36, 39 ], [ 21, 20, 29 ], [ 21, 28, 35 ],
[ 21, 72, 75 ], [ 25, 60, 65 ], [ 27, 36, 45 ],
[ 33, 44, 55 ], [ 33, 56, 65 ], [ 35, 12, 37 ],
[ 35, 84, 91 ], [ 39, 52, 65 ], [ 39, 80, 89 ],
[ 45, 24, 51 ], [ 45, 28, 53 ], [ 45, 60, 75 ],
[ 51, 68, 85 ], [ 55, 48, 73 ], [ 57, 76, 95 ],
[ 63, 16, 65 ], [ 63, 60, 87 ], [ 63, 84, 105 ],
[ 65, 72, 97 ], [ 69, 92, 115 ], [ 75, 40, 85 ],
[ 75, 100, 125 ], [ 77, 36, 85 ], [ 91, 60, 109 ],
[ 99, 20, 101 ], [ 6, 8, 10 ], [ 10, 24, 26 ],
[ 12, 16, 20 ], [ 14, 48, 50 ], [ 16, 30, 34 ],
[ 18, 24, 30 ], [ 18, 80, 82 ], [ 20, 48, 52 ],
[ 24, 32, 40 ], [ 24, 70, 74 ], [ 28, 96, 100 ],
[ 30, 40, 50 ], [ 30, 72, 78 ], [ 32, 60, 68 ],
[ 36, 48, 60 ], [ 40, 42, 58 ], [ 40, 96, 104 ],
[ 42, 56, 70 ], [ 48, 64, 80 ], [ 48, 90, 102 ],
[ 54, 72, 90 ], [ 56, 90, 106 ], [ 60, 80, 100 ],
[ 66, 88, 110 ], [ 72, 96, 120 ], [ 80, 84, 116 ]
]
undefined
> console.log(pythagorean_triple_v2(100))
[
[ 3, 4, 5 ], [ 8, 6, 10 ],
[ 5, 12, 13 ], [ 15, 8, 17 ],
[ 12, 16, 20 ], [ 7, 24, 25 ],
[ 24, 10, 26 ], [ 21, 20, 29 ],
[ 16, 30, 34 ], [ 9, 40, 41 ],
[ 35, 12, 37 ], [ 32, 24, 40 ],
[ 27, 36, 45 ], [ 20, 48, 52 ],
[ 11, 60, 61 ], [ 48, 14, 50 ],
[ 45, 28, 53 ], [ 40, 42, 58 ],
[ 33, 56, 65 ], [ 24, 70, 74 ],
[ 13, 84, 85 ], [ 63, 16, 65 ],
[ 60, 32, 68 ], [ 55, 48, 73 ],
[ 48, 64, 80 ], [ 39, 80, 89 ],
[ 28, 96, 100 ]
]
undefined
> console.log(pythagorean_triple_v3(100))
[
[ 3, 4, 5 ], [ 5, 12, 13 ],
[ 15, 8, 17 ], [ 7, 24, 25 ],
[ 21, 20, 29 ], [ 9, 40, 41 ],
[ 35, 12, 37 ], [ 11, 60, 61 ],
[ 45, 28, 53 ], [ 33, 56, 65 ],
[ 13, 84, 85 ], [ 63, 16, 65 ],
[ 55, 48, 73 ], [ 39, 80, 89 ],
[ 77, 36, 85 ], [ 65, 72, 97 ]
]
undefined
>
> timeIt(pythagorean_triple_v0, 100)
[Function: pythagorean_triple_v0] 100 0.0000388
undefined
> timeIt(pythagorean_triple_v1, 100)
[Function: pythagorean_triple_v1] 100 0.0000596
undefined
> timeIt(pythagorean_triple_v2, 100)
[Function: pythagorean_triple_v2] 100 9e-7
undefined
> timeIt(pythagorean_triple_v3, 100)
[Function: pythagorean_triple_v3] 100 0.0000011
undefined
>
> pythagorean_triple_v0(100).length
63
> pythagorean_triple_v1(100).length
63
> pythagorean_triple_v2(100).length
27
> pythagorean_triple_v3(100).length
16
>
> var count = 0
undefined
> for (let [a, b, c] of pythagorean_triple_v0(100)) {
... if (c <= 100) {count += 1}
... }
undefined
> console.log(count - pythagorean_triple_v2(100).length)
25
undefined
How can they be improved?
