Tuesday, 19 July 2011

Pythagorean Triplet

“The beauty of Math can only be understood if you think like an historian!!.. Without Math, there is no astronomy.. Mathematical reasoning is hugely used by historians.. Even pre historic humans had Math in them”

Introduction

   After a long time, I am happy to bootstrap this blog. :) It’s been a bit tough for me getting time till now. From now on, the articles will be small and simple. :)

The problems we are going to see from now on daily are going to be from programming competition sites. Without referencing the copyrighted questions, we will just discuss about those in a generalized way giving proper courtesy to the site. :)

Question

  Find the Pythagorean Triplet which satisfies this equation: a+b+c = 1000.

Brain storm

         Interesting to learn an 8th grade math. But we must be ready to relearn multiplication tables itself to get into hard core problem solving. :)

     Pythagoras theorem is a very popular and most hyped theorem whose formula is simply mugged up and remembered by even adults till now. :)

  Simply, its, a2 + b2 = c2

But there is many more interesting discoveries around Pythagoras theorem. :) Circles, Euclid Circle, plains.. Almost whole geometry is revolving around this simple formula. The above formula is for getting the length of the sides of a right angled triangle in a 2D plain. Only when the lengths adhere to the above formula, you get a right angled triangle.

  But there is an interesting property, when this (a,b,c) is represented as a triplet. It gives out lots of good properties related to odd & even numbers and the sum of there squares.

This article gives a really brief and clear understanding about Pythagorean triplet: http://www.mathsisfun.com/numbers/pythagorean-triples.html

  Selecting any number for a,b,c can form a Pythagorean triplet with the following properties followed strict

  • all numbers can be even or
  • any two numbers can be odd & at least one number is even.

For making this happen there is a Euclid’s formula with m,n give (m<n)

a = n*n – m*m

b = 2*n*m

c = n*n + m*m

Using these formulas, we can get near the sum which gives 1000.

Code

void main()
{
    int a=0,b=0,c=0;
    int m,n;
 
    for(m=1; m < 15; m++) {
        for(n=m+1; n<30;n++) {
            if( a+b+c != 1000 ) {
                a = n*n - m*m;
                b = 2*n*m;
                c = n*n + m*m;
                std::cout<<m<<","<<n<<" ("<<a<<","<<b<<","<<c<<")"<<"="<<a+b+c<<std::endl;
            } else
                break;
        }
    }
 
}

Problem 9: Project Euler