- Three Monitors For Every User (Jeff Atwood)
- MVVM Light Toolkit V3 SP1 for Windows Phone 7 (Laurent Bugnion)
- Changing States using GoToStateAction (Kirupa Chinnathambi)
- Windows Phone: Frame/Page navigation and transitions using the TransitioningContentControl (Avi Pilosof)
- Rethinking Programming Language Tutorials
- Refactor This!
- Refactor This: Answers
- Paint With Light
- Programmer Tip: Trying To Be There When The Sky Is Falling Or You Are Needed
- Windows Phone development and design – ultimate guide
- Making the Most of the Reactive Extentions for .NET

Project Euler problem 29~

`1: class Program`

2: {3: static void Main(string[] args)4: {`5: Console.WriteLine("The total number of distinct terms are in the sequence:");`

6:7: TestBenchSetup();8: TestBenchLoader(construct_prime_factor_list_and_use_hashset_to_prevent_duplicate);9: TestBenchLoader(using_brain_power_to_find_pattern);10:`11: Console.WriteLine("Press any key to exit");`

12: Console.ReadKey();13: }14:15: static int construct_prime_factor_list_and_use_hashset_to_prevent_duplicate()16: {17: var len = 100;18: var primes = new int[] { 2, 3, 5, 7 };19: var sum = 0;20: var distinct_set = new HashSet<string>();21: var prime_factors = new Dictionary<int, int>();22: var count = 0;23: for (int i = 2; i <= len; i++)24: {25: sum = i;26: prime_factors.Clear();27: foreach (var prime in primes)28: {29: count = 0;`30: while (sum % prime == 0)`

31: {32: sum = sum / prime;33: ++count;34: }`35: if (count > 0)`

36: prime_factors.Add(prime, count);37: }`38: if (prime_factors.Count == 0 || sum != 1)`

39: prime_factors.Add(sum, 1);40:41: for (int power = 2; power <= len; power++)42: {`43: var factorList = new StringBuilder();`

44: foreach (var item in prime_factors)45: {46: factorList.Append(item.Key);47: factorList.Append('^');48: factorList.Append(item.Value * power);49: factorList.Append(' ');50: }51: distinct_set.Add(factorList.ToString());52: }53: }`54: return distinct_set.Count;`

55: }56:`57: /// <summary>`

`58: /// The non-brute-force way explained by jorgbrown(from this q's discussion post, the code is by qbtruk)`

`59: ///`

`60: /// C'mon guys, this is a pencil-and-paper problem, not a coding problem.`

`61: /// Euler probably could have done this one in under 5 minutes. While asleep.`

`62: ///`

`63: /// The total number of powers is 9801; really, we're just trying to find duplicates.`

`64: /// Specifically, let's think about, how many duplicates are there when a^b is a dupe of a`

`65: /// smaller a raised to a larger power b?`

`66: ///`

`67: /// Suppose a is a perfect square of the smaller a, but not a square of a square.`

`68: /// Then we have a duplicate when b is 2, 3, 4... up to 50. That is, 49 duplicates.`

`69: ///`

`70: /// Suppose a is a perfect cube of a smaller a. When b is 2 through 33, we have duplicates`

`71: /// of smaller a raised to the power b*3. When b is 34, 36, 38, 40, 42, 44, 46, 48, 50, 52,`

`72: /// 54, 56, 58, 60, 62, 64, 66, we have duplicates of a smaller a raised to the power (b/2)*3.`

`73: /// Total is 32 plus 17, or again, 49 duplicates.`

`74: ///`

`75: /// Suppose a is the square of the square of a smaller a. When b is 2 through 49, we have duplicates`

`76: /// of the square root of a raised to the power (b*2). When b is 51, 54, 57, 60, 63, 66, 69, 72, or 75,`

`77: /// we have dupes of a^(3/4) raised to the power (b*4/3). Total is 49 plus 9, or 58.`

`78: ///`

`79: /// Suppose a is the fifth power of a smaller a. We have dupes of fifth root of a raised to the power (b*5),`

`80: /// which covers b from 2 to 20. Then we have dupes of a^(2/5) raised to the power (b*5/2),`

`81: /// which covers b of 22, 24, 26, 28, 30, 32, 34, 36, 38, 40. Then we have dupes of a^(3/5) raised to the`

`82: /// power (b*5/3), which covers b of 21, 27, 33, 39, 42, 45, 48, 51, 54, 57, 60. Last, we have dupes`

`83: /// of a^(4/5) raised to the power (b*5/4), which covers b of 44, 52, 56, 64, 68, 72, 76, and 80. Total dupes: 48.`

`84: /// And the last power we have to worry about is 6. We have dupes of the square root of a raised`

`85: /// to power (b*2), which covers b from 2 to 50. Then we have dupes of the sixth root to the power (b*6/4),`

`86: /// which covers b of 52, 54, 56, 58, 60, 62, 64, 66. And last we have dupes of the sixth root to the power (b*6/5),`

`87: /// which covers b of 55, 65, 70, 75, and 80. Total dupes: 62.`

`88: ///`

`89: /// Now let's put it all together:`

`90: /// squares: 4, 9, 25, 36, 49, 100: These 6 squares have 49 dupes each, 6 * 49 = 294`

`91: /// cubes: 8, 27: These 3 cubes have 49 duplicates each: 2 * 49 = 98`

`92: /// 4th power: 16, 81. These 2 have 58 dupes each: 2 * 58 = 116`

`93: /// 5th power: 32. This has 48 dupes.`

`94: /// 6th power: 64: this has 62 dupes.`

`95: /// Total # dupes: 618. 9801-618 is 9183.`

`96: /// </summary>`

`97: /// <returns></returns>`

98: static int using_brain_power_to_find_pattern()99: {`100: int maxBase = 100;`

`101: int maxPower = 100;`

102:`103: int nonPowerCount = 85;`

`104: int nonPowerDistinct = 99;`

105:`106: int power2Count = 4;`

`107: int power2Distinct = 50;`

108:`109: int totalDistinct = nonPowerCount * nonPowerDistinct + power2Count * power2Distinct;`

110:111: bool[] pow2found = new bool[601];`112: int maxPow2 = 6;`

113:114: bool[] pow3found = new bool[401];`115: int maxPow3 = 4;`

116:117: for (int pow2 = 1; pow2 < maxPow2 + 1; pow2++)118: for (int power = 2; power < maxPower + 1; power++)`119: pow2found[power * pow2] = true;`

120:121: for (int pow3 = 1; pow3 < maxPow3 + 1; pow3++)122: for (int power = 2; power < maxPower + 1; power++)`123: pow3found[power * pow3] = true;`

124:125: for (int index = 0; index < pow2found.Length; index++)`126: if (pow2found[index])`

127: totalDistinct++;128:129: for (int index = 0; index < pow3found.Length; index++)`130: if (pow3found[index])`

131: totalDistinct++;132:`133: return totalDistinct;`

134: }135:136: static Stopwatch stopwatch = new Stopwatch();137: static void TestBenchSetup()138: {`139: // Uses the second Core or Processor for the Test`

`140: Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);`

`141: // Prevents "Normal" processes from interrupting Threads`

142: Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;`143: // Prevents "Normal" Threads from interrupting this thread`

144: Thread.CurrentThread.Priority = ThreadPriority.Highest;145: }`146: // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx`

147: static void TestBenchLoader(Func<int> test_method)148: {149: stopwatch.Reset();150: stopwatch.Start();151: var result = 0;`152: long avg_tick = 0;`

`153: long avg_ms = 0;`

154: while (stopwatch.ElapsedMilliseconds < 1200) // A Warmup of 1000-1500 ms`155: // stabilizes the CPU cache and pipeline.`

156: {`157: result = test_method(); // Warmup`

158: }159: stopwatch.Stop();160: for (int repeat = 0; repeat < 20; ++repeat)161: {162: stopwatch.Reset();163: stopwatch.Start();164: result = test_method();165: stopwatch.Stop();166: avg_tick += stopwatch.ElapsedTicks;167: avg_ms += stopwatch.ElapsedMilliseconds;168: }169: avg_tick = avg_tick / 20;170: avg_ms = avg_ms / 20;171: Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",172: test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));173: }174: }

Advertisements