Its Friday~

Project Euler problem 9~

  1:  class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("There exists exactly one Pythagorean triplet for which a + b  + c = 1000, Find the product abc");
  8:             sw.Start();
  9:             var product1 = BruteForce();
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("plain loop brute force way(tick:{0}): {1}", sw.ElapsedTicks, product1));
 12: 
 13:             sw.Reset();
 14: 
 15:             Console.WriteLine("There exists exactly one Pythagorean triplet for which a + b  + c = 1000, Find the product abc");
 16:             sw.Start();
 17:             var product2 = ArithmeticWay();
 18:             sw.Stop();
 19:             Console.WriteLine(string.Format("Euclid's formula way, with k(tick:{0}): {1}", sw.ElapsedTicks, product2));
 20: 
 21: 
 22:             Console.WriteLine("Press any key to exit");
 23:             Console.ReadKey();
 24:         }
 25: 
 26:         /// <summary>
 27:         /// plain loop all possibilities way
 28:         /// a or b cannot exceed 500, so set that as bound
 29:         /// and since a+b+c has to be 1000, which makes c = (1000-a-b)
 30:         /// and a^2 + b^2 = c^2, so two nested loops are enough
 31:         /// </summary>
 32:         /// <returns></returns>
 33:         static int BruteForce()
 34:         {
 35:             for (int a = 1; a < 500; a++)
 36:             {
 37:                 for (int b = a + 1; b < 500; b++)
 38:                 {
 39:                     if (a * a + b * b == (1000 - a - b) * (1000 - a - b))
 40:                     {
 41:                         return a * b * (1000 - a - b);
 42:                     }
 43:                 }
 44:             }
 45: 
 46:             return 0;
 47:         }
 48: 
 49:         /// <summary>
 50:         /// using the Euclid's formula with k, see http://en.wikipedia.org/wiki/Pythagorean_triple
 51:         /// a = k * (m^2 - n^2)
 52:         /// b = k * (2mn)
 53:         /// c = k * (m^2 + n^2)
 54:         /// starting with k=1
 55:         /// (m^2 - n^2) + (2mn) + (m^2 + n^2) = 1000
 56:         /// (2m^2 + 2mn) = 1000
 57:         /// m^2 + mn = 500
 58:         /// since m and n has to be integer and non-zero
 59:         /// so 500 has to be divisible by k and
 60:         /// we can set the m_bound to be less or equal to Math.Sqrt(k_bound), since n cannot be zero
 61:         /// </summary>
 62:         /// <returns></returns>
 63:         static int ArithmeticWay()
 64:         {
 65:             int k_bound = 0;
 66:             int m_bound = 0;
 67:             for (int k = 1; k <= 500; k++)
 68:             {
 69:                 if (500 % k == 0)
 70:                 {
 71:                     k_bound = 500 / k;
 72:                     m_bound = (int)Math.Sqrt(k_bound);
 73: 
 74:                     for (int m = 1; m <= m_bound; m++)
 75:                     {
 76:                         if (k_bound % m == 0)
 77:                         {
 78:                             int n = k_bound / m - m;
 79:                             if (m > n)
 80:                                 return k * (m * m - n * n) * k * (2 * m * n) * k * (m * m + n * n);
 81:                         }
 82:                     }
 83:                 }
 84:             }
 85:             return 0;
 86:         }
 87:     }

Advertisements
This entry was posted in Programming. Bookmark the permalink.

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