Riddle 9: Special Pythagorean triplet

Riddle 9: Special Pythagorean triplet

Mia Temma's photo
Mia Temma
·Feb 15, 2022·

3 min read

The Task

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which a^2 + b^2 = c^2.

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.


Solution

This task is rather easy. We can simply go through all possible combinations where A<B<C and the sum of a, b, c is exactly 1000.

We start with A=1, B=2 and C=1000-A-B:

(de special_triplet 
   (let (A 1  B 2  C (- 1000 A B))

For each combination, we check if is a pythagorean triplet. Let's do it in a separate function:

(de pythagorean_triplet (A B C)
   (when
      (= (+ (* A A) (* B B)) (* C C))
      (prinl (* A B C) ) ) )

Now we construct all possible combinations for A, B and C: First B is increased as much as possible, i. e. until C is larger than B. For example, for A=1, the maximum possible combination is B=499, C=500.

Each time we generate a new combination, we check if it's a pythagorean triplet, then we increase B by one and re-define C.

(while (and (< A B) (< B C))
   (while (< B C)
      (pythagorean_triplet A B C)
      (setq C (- 1000 A (inc 'B))) )

If B can't be further increased, we increase A by one, setB to A+1 and repeat the whole process.

(setq B (inc (inc 'A)))
(setq C (- 1000 A B)) ) ) )

This is the final function:

(de pythagorean_triplet (A B C)
   (when
      (= (+ (* A A) (* B B)) (* C C))
      (prinl (* A B C) ) ) )

(de special_triplet (Limit)
   (let (A 1  B 2  C (- Limit A B))
      (while (and (< A B) (< B C))
         (while (< B C)
            (pythagorean_triplet A B C)
            (setq C (- Limit A (inc 'B))) )
         (setq B (inc (inc 'A)))
         (setq C (- Limit A B)) ) ) )

where Limit is the sum of A, B and C (in this case it should be 1000).


Further Inspiration

If you want to dig deeper, there is a very similar kind of task in the "Rosetta Code": List Comprehension:

A list comprehension is a special syntax in some programming languages to describe lists. It is similar to the way mathematicians describe sets, with a set comprehension, hence the name. Some attributes of a list comprehension are:

  • They should be distinct from (nested) for loops and the use of map and filter functions within the syntax of the language.
  • They should return either a list or an iterator (something that returns successive members of a collection, in order).
  • The syntax has parts corresponding to that of set-builder notation.

Task

Write a list comprehension that builds the list of all Pythagorean triples with elements between 1 and n.

If the language has multiple ways for expressing such a construct (for example, direct list comprehensions and generators), write one example for each.

PicoLisp doesn't have list comprehension, but the solution in the Rosetta Code lists four ways to solve this task:

  • Using a generator function,
  • Using a pipe,
  • Using a coroutine
  • Using the Prolog-engine "Pilog".

Some of these solutions refer to older versions of PicoLisp, but the concepts still apply to pil21.


You can find the code for the finished solution here.


Sources

 
Share this