The Pythagorean Triplet Problem

The Inception

Pythagorean Triplets are the set of three numbers which satisfies the Pythagoras Theorem, for example, (3,4,5) is a Pythagorean Triplet – that is, 3^2+4^2=5^5.

This image was circulating in Facebook a few years ago. Interesting: They have a Pythagorean triplet, (8,15,17), which translates to August 15, 2017, two days before this article was written.

Made me wonder: Are there any other Pythagorean Triplets, such that a^2+ b^2=17^2?

And for it to translate to a date, we will need a\le12 , b\le31, since there are only 12 months and at most 31 days in a month.

Theoretical solutions are not too hard, I believe.

Brute Force Solution

I was tempted to try it the simplest way, called brute force. Brute Force technique is when we try apply all possible combination of values using some programs to see if there is any pair of values that satisfies the given hypothesis. Since a\le12 , b\le31, we know that we just need to check a finite number of values of a and b, hence we can use brute force algorithms.

It’s easy to write a simple program to achieve the target – in fact, you just need to find upper bounds for a, b and insert it in a nested for loop, no matter which language you are using (C or C++ or Java or Python).

Optimization

But in that case, there will be more loop runs than what is required to find the answer. For example, here, since 17^2 is odd, we can be sure that either a or b has to be odd and other even. Using that condition, we can simplify our for loops to run for lesser values, hence the algorithm or program will be faster. That is, we can find a more efficient algorithm which solves our problem.

Use functions like time_it in Python to observe how your new algorithm performs faster.

Sidenote: Brute Force Using Excel

Excel is a magical tool for such matters. You can also try impliment the logic in Excel using loops by creating Macros. Those who want to master Excel can try this.

If you need any help, you can always approach me.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.