WPF/WinPhone7/and more….

Project Euler problem 23~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("The sum of all the positive integers which cannot be written as the sum of two abundant numbers");
  8:             sw.Start();
  9:             var sum1 = test1(28124);
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("construct all divisor map and find all combo way(ms:{0}): {1}", sw.ElapsedMilliseconds, sum1));
 12: 
 13:             sw.Reset();
 14: 
 15:             Console.WriteLine("The sum of all the positive integers which cannot be written as the sum of two abundant numbers");
 16:             sw.Start();
 17:             var sum2 = test2(28124);
 18:             sw.Stop();
 19:             Console.WriteLine(string.Format("construct all divisor map and with filtered combo way(ms:{0}): {1}", sw.ElapsedMilliseconds, sum2));
 20: 
 21:             Console.WriteLine("Press any key to exit");
 22:             Console.ReadKey();
 23:         }
 24:         static int loop_counter = 0;
 25:         /// <summary>
 26:         /// basically construct a map containing all divisor of each number up to ceiling
 27:         /// find the abundant numbers and save to a list
 28:         /// create a boolean map with number as index and bool as value(true = sum of 2 abundant numbers)
 29:         /// using 2 nested to find out all possible combination of 2 abundant number within range(huge loop counts 😦
 30:         /// </summary>
 31:         /// <param name="ceiling"></param>
 32:         /// <returns></returns>
 33:         static int test1(int ceiling)
 34:         {
 35:             loop_counter = 0;
 36:             var map = new List<int>[ceiling + 1];
 37:             var div = 0;
 38:             int bound = (int)Math.Sqrt(ceiling);
 39:             for (int i = 1; i <= bound; i++)
 40:             {
 41:                 for (int j = i * i; j <= ceiling; j += i)
 42:                 {
 43:                     if (map[j] == null)
 44:                         map[j] = new List<int>();
 45: 
 46:                     map[j].Add(i);
 47:                     div = j / i;
 48: 
 49:                     if (div < j && map[j].Any(l => l == div) == false)
 50:                         map[j].Add(div);
 51: 
 52:                     loop_counter++;
 53:                 }
 54:             }
 55:             Console.WriteLine("loop counter for building divisor map: " + loop_counter);
 56:             var abundant = new List<int>();
 57:             for (int i = 2; i < ceiling; i++)
 58:             {
 59:                 if (map[i].Sum() > i)
 60:                     abundant.Add(i);
 61:             }
 62:             var map2 = new bool[ceiling];
 63:             var len = abundant.Count;
 64:             int num = 0;
 65:             loop_counter = 0;
 66:             for (int i = 0; i < len; i++)
 67:             {
 68:                 for (int j = i; j < len - 1; j++)
 69:                 {
 70:                     num = abundant[i] + abundant[j];
 71:                     if (num < ceiling)
 72:                         map2[num] = true;
 73: 
 74:                     loop_counter++;
 75:                 }
 76:             }
 77:             Console.WriteLine("loop counter for building abundant map: " + loop_counter);
 78:             var sum = 0;
 79:             for (int i = 0; i < ceiling; i++)
 80:             {
 81:                 if (map2[i] == false)
 82:                     sum += i;
 83:             }
 84:             return sum;
 85:         }
 86:         /// <summary>
 87:         /// using the knowledge from http://tafakuri.net/?p=71
 88:         /// 1.The upper bound for numbers that cannot be expressed as the sum of 
 89:         ///   two numbers is actually 20161 not 28123 (as shown here).
 90:         /// 2.All even numbers greater than 48 can be written as the sum of two 
 91:         ///   abundant numbers (also shown in the article here).
 92:         /// </summary>
 93:         /// <param name="ceiling"></param>
 94:         /// <returns></returns>
 95:         static int test2(int ceiling)
 96:         {
 97:             var map = new List<int>[ceiling + 1];
 98:             var div = 0;
 99:             int bound = (int)Math.Sqrt(ceiling);
100:             for (int i = 1; i <= bound; i++)
101:             {
102:                 for (int j = i * i; j <= ceiling; j += i)
103:                 {
104:                     if (map[j] == null)
105:                         map[j] = new List<int>();
106: 
107:                     map[j].Add(i);
108:                     div = j / i;
109: 
110:                     if (div < j && map[j].Any(l => l == div) == false)
111:                         map[j].Add(div);
112:                 }
113:             }
114:             
115:             var even = new List<int>();
116:             var odd = new List<int>();
117:             for (int i = 2; i < ceiling; i++)
118:             {
119:                 if (map[i].Sum() > i)
120:                 {
121:                     if(i % 2 == 0)
122:                         even.Add(i);
123:                     else
124:                         odd.Add(i);
125:                 }
126:             }
127: 
128:             var map2 = new bool[ceiling];
129:             map2[24] = true;
130:             map2[30] = true;
131:             map2[32] = true;
132:             map2[36] = true;
133:             map2[38] = true;
134:             map2[40] = true;
135:             map2[42] = true;
136:             map2[44] = true;
137:             map2[48] = true;
138:             var num = 0;
139:             loop_counter = 0;
140:             for (int i = 0; i < odd.Count; i++)
141:             {
142:                 for (int j = 0; j < even.Count; j++)
143:                 {
144:                     num = odd[i] + even[j];
145:                     if (num < ceiling)
146:                         map2[num] = true;
147: 
148:                     loop_counter++;
149:                 }
150:             }
151:             Console.WriteLine("loop counter for building abundant map: " + loop_counter);
152:             var sum = 0;
153:             for (int i = 0; i < ceiling; i++)
154:             {
155:                 if (i > 48 && i % 2 == 0)
156:                     map2[i] = true;
157: 
158:                 if (map2[i] == false)
159:                     sum += i;
160:             }
161:             return sum;
162:         }
163:     }

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