Pythagorean Triplet
Find every Pythagorean triplet a < b < c with a² + b² = c² whose sides sum to a given number.
Adapted from Exercism’s problem specification (MIT). Listed under Numbers & Math.
// FILE: pythagorean_triplet.nomi
//# The Pythagorean triplets whose sides sum to a given number.
/// Every Pythagorean triplet `(a, b, c)`, with `a < b < c`, whose sides sum
/// to `n`, smallest `a` first.
pub fn triplets_with_sum(n: Int) -> List<(Int, Int, Int)>
1..n / 3
|> Iter.map(&triplet(n, &1))
|> Maybe.values()
|> Iter.to_list()
end
/// The triplet summing to `n` whose shortest side is `a`, if there is one.
/// With `c = n - a - b`, `a² + b² = c²` gives `b = (n² - 2na) / (2(n - a))`,
/// so `b` is whole or there is no such triplet.
fn triplet(n: Int, a: Int) -> Maybe<(Int, Int, Int)>
top = n * n - 2 * n * a
// `a` is below `n / 3`, so `n - a` is above 0.
bottom = PositiveInt.try_from(2 * (n - a))!
b = top / bottom
if top % bottom == 0 and a < b then Some((a, b, n - a - b)) else None
end
// FILE: pythagorean_triplet_test.nomi
import pythagorean_triplet
test "triplets with sum"
[
("triplets whose sum is 12", 12, [(3, 4, 5)]),
("triplets whose sum is 108", 108, [(27, 36, 45)]),
("triplets whose sum is 1000", 1000, [(200, 375, 425)]),
("no matching triplets for 1001", 1001, []),
("returns all matching triplets", 90, [(9, 40, 41), (15, 36, 39)]),
(
"several matching triplets",
840,
[
(40, 399, 401),
(56, 390, 394),
(105, 360, 375),
(120, 350, 370),
(140, 336, 364),
(168, 315, 357),
(210, 280, 350),
(240, 252, 348),
],
),
(
"triplets for large number",
30000,
[
(1200, 14375, 14425),
(1875, 14000, 14125),
(5000, 12000, 13000),
(6000, 11250, 12750),
(7500, 10000, 12500),
],
),
]
|> subtests (description, n, expected), description
assert pythagorean_triplet.triplets_with_sum(n) == expected
end
endok triplets with sum (7 cases)
test result: ok. 7 passed, 0 failed
How it’s written
Section titled “How it’s written”- A triplet is a tuple,
(a, b, c), and the answer aListof them, smallestafirst, as the canonical data lists them. The three sides are read together and never apart, so a struct would only name them. - The search runs over
aalone. Withc = n - a - b, the equation solves tob = (n² - 2na) / (2(n - a)), so eachahas at most one triplet, and it exists when that division is exact anda < b.ais belown / 3, so2(n - a)is above zero, whichPositiveInt.try_from(...)!states so/and%take it. That is one pass ofn / 3steps, which keeps the largest case (n = 30000) to 10,000 divisions instead of a nested loop overaandb. tripletanswers aMaybepera, andMaybe.valueskeeps the ones that exist. The derivation sits intriplet’s doc comment, so the arithmetic is explained where it is written.- The seven canonical cases are one
subteststable named by the description column.