Elegant solution to Pythagorean Triplet problem

Every once in a while I come across something that makes me admire the elegance and simplicity of mathematics and mathematical proofs.

I was introduced to computer programming in 1992 and was pretty good at GW-BASIC. Advantage of GW-BASIC was that each line was self-explanatory. However, after high school I made a career choice to go into business school and left that hobby behind.

Three years ago when my finance career was going nowhere, decided to learn programming again. Found out a website known as Project Euler and tried using the challenges as a motivation. Decided on JAVA and bought the book Head First Java. Though I made good progress with it but the syntax of Java with its curly braces and cryptographic headers didn’t talk to me. Here is the simple Hello World program from Java’s own website

class HelloWorldApp {
    public static void main(String[] args) {
        System.out.println("Hello World!"); // Display the string.
    }
}

How is one supposed to learn a language when the first and second line one uses in writing the program is not explained fully till one reaches advanced stage. So after some time and coding a few programs, I gave up on it.

Then I came across Udacity and Coursera MOOC websites. Almost all of their courses talked about using Python language whenever some programming was involved. So I found out about Python and it seems so straightforward. It may not be as powerful as C++ or Java but for the hobbyist or amateur programmer like myself, it did the job. Best of all, its code need not start with a cryptographic header. Below is a code for printing “Hello World” in Python:

print("Hello World!")

So I started working on Project Euler problems from beginning this time coding in Python and it has been quite easy to pick up through self-study and online resources.

I came across this problem of find a Pythagorean triplet on Project Euler.

I didn’t know how to generate Pythagorean triplets or what algorithm to use. One way was to use brute force method and try every combination of say from like the below one:

for a in range(499):
   for b in range(499):
      for c in range(499):
          if a + b + c == 1000 :
              if a**2 + b**2 == c**2:
                   print (a*b*c)

I didn’t use the above program. Once I had found out the result through my own method, I came across the above on the forum as a brute force method used by someone. When I ran it, it took the computer almost 6-7 seconds to print the result which is a very long time.

I solved it without using a computer. I went to best available source of information i.e., Wikipedia (I know its user edited and not expert edited). It had this formula for coming up with Pythagorean triplets

Euclid’s formula[1] is a fundamental formula for generating Pythagorean triples given an arbitrary pair of positive integers m and n with m > n. The formula states that the integers

 a = m^2 - n^2 ,\ \, b = 2mn ,\ \, c = m^2 + n^2

form a Pythagorean triple.

Using paper and pen, I solved the following equation using the above information

a + b + c  = 1000

replacing a,b,c with m,n as given above
(m^2 – n^2) + (2mn) + (m^2 + n^2) = 1000

cancelling out n^2, we get
2m^+2mn = 1000

which is equal to
2m(m+n)=1000

Dividing both sides by 2 results in
m ( m + n ) = 500

First number that came into my mind was 25 x 20 = 500 meaning that m = 20, n = 5. And lo and behold, it produced the correct answer. Just for the heck of it, I tried different numbers of m and n by making a table in Excel and every time it produced a Pythagorean Triplet.

It is not ground breaking or anything, but using just a pen and paper to elegantly solve a computer programming problem without using brute force made me appreciate the beauty of mathematics again.

If you are interested and have grasp of high school mathematics, I seriously recommend reading Journey through Genius. It is one of those books that I refer back to again and again just for sheer delight.

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s