tag:blogger.com,1999:blog-18014686127553092802024-02-20T00:18:21.146-08:00Andrew's Project Euler SolutionsAndrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.comBlogger33125tag:blogger.com,1999:blog-1801468612755309280.post-9499907218444401772014-11-03T16:46:00.000-08:002014-11-03T16:46:04.427-08:00Problem 32 - Pandigital products<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem: </b><br />
<br />
Please find the problem <a href="https://projecteuler.net/problem=32">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
My current solution is kind of slow - it runs through all permutations and all possible splits to check for the product formula, and when it does accumulate the results, it is that simple.<br />
<br />
It would be great if we could speed this up using some more constraints, but for now, this is good enough to produce and answer.<br />
<br />
It would be an interesting detour to discuss the permutation generating algorithm. In some sense it is simple, pick the head, recursively compute the permutation of remaining elements, and concat with the head. Note that we could have been faster if we optimize the permutation method to reuse the same buffer instead of creating new list for each recursive result!<br />
<br />
<b>Code:</b><br />
<br />
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">using</span> System.Numerics;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> available)
{
List<T> availableList = available.ToList();
<span class="kwrd" style="color: blue;">return</span> Permutations(availableList.Select(t => Pair<<span class="kwrd" style="color: blue;">bool</span>, T>.Create(<span class="kwrd" style="color: blue;">true</span>, t)).ToArray(), availableList.Count);
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> IEnumerable<IEnumerable<T>> Permutations<T>(Pair<<span class="kwrd" style="color: blue;">bool</span>, T>[] available, <span class="kwrd" style="color: blue;">int</span> count)
{
<span class="kwrd" style="color: blue;">if</span> (count == 0)
{
yield <span class="kwrd" style="color: blue;">return</span> <span class="kwrd" style="color: blue;">new</span> List<T> { };
}
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 0; i < available.Length; i++)
{
<span class="kwrd" style="color: blue;">if</span> (available[i].Item1)
{
available[i].Item1 = <span class="kwrd" style="color: blue;">false</span>;
<span class="kwrd" style="color: blue;">foreach</span> (IEnumerable<T> recursiveResult <span class="kwrd" style="color: blue;">in</span> Permutations(available, count - 1))
{
yield <span class="kwrd" style="color: blue;">return</span> <span class="kwrd" style="color: blue;">new</span> List<T> { available[i].Item2 }.Concat(recursiveResult);
}
available[i].Item1 = <span class="kwrd" style="color: blue;">true</span>;
}
}
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">class</span> Pair<T, U>
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> Pair<T, U> Create(T item1, U item2)
{
<span class="kwrd" style="color: blue;">return</span> <span class="kwrd" style="color: blue;">new</span> Pair<T, U>(item1, item2);
}
<span class="kwrd" style="color: blue;">private</span> Pair(T item1, U item2)
{
<span class="kwrd" style="color: blue;">this</span>.Item1 = item1;
<span class="kwrd" style="color: blue;">this</span>.Item2 = item2;
}
<span class="kwrd" style="color: blue;">public</span> T Item1 { <span class="kwrd" style="color: blue;">get</span>; <span class="kwrd" style="color: blue;">set</span>; }
<span class="kwrd" style="color: blue;">public</span> U Item2 { <span class="kwrd" style="color: blue;">get</span>; <span class="kwrd" style="color: blue;">set</span>; }
}
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem032()
{
HashSet<<span class="kwrd" style="color: blue;">int</span>> results = <span class="kwrd" style="color: blue;">new</span> HashSet<<span class="kwrd" style="color: blue;">int</span>>();
<span class="kwrd" style="color: blue;">foreach</span> (<span class="kwrd" style="color: blue;">var</span> permutation <span class="kwrd" style="color: blue;">in</span> Permutations(Enumerable.Range(1, 9).ToArray()))
{
<span class="rem" style="color: green;">// Break down the permutation into list of different partitions and check product formula</span>
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> firstPart = 1; firstPart < 9; firstPart++)
{
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> secondPart = 1; secondPart < 9; secondPart++)
{
<span class="kwrd" style="color: blue;">int</span> thirdPart = 9 - firstPart - secondPart;
<span class="kwrd" style="color: blue;">if</span> (thirdPart > 0)
{
<span class="kwrd" style="color: blue;">string</span> permutationString = permutation.Aggregate(<span class="str" style="color: #a31515;">""</span>, (s, x) => s + x);
<span class="kwrd" style="color: blue;">int</span> firstPartValue = <span class="kwrd" style="color: blue;">int</span>.Parse(permutationString.Substring(0, firstPart));
<span class="kwrd" style="color: blue;">int</span> secondPartValue = <span class="kwrd" style="color: blue;">int</span>.Parse(permutationString.Substring(firstPart, secondPart));
<span class="kwrd" style="color: blue;">int</span> thirdPartValue = <span class="kwrd" style="color: blue;">int</span>.Parse(permutationString.Substring(9 - thirdPart));
<span class="kwrd" style="color: blue;">if</span> (firstPartValue == secondPartValue * thirdPartValue)
{
results.Add(firstPartValue);
<span class="rem" style="color: green;">//Console.WriteLine("{0} = {1} x {2}", firstPartValue, secondPartValue, thirdPartValue);</span>
}
}
}
}
}
Console.WriteLine(results.Aggregate((x, y) => x + y));
}
}
}</pre>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-14320862648975026472014-11-03T16:28:00.002-08:002014-11-03T16:28:45.989-08:00Problem 31 - Coin Sum<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="https://projecteuler.net/problem=31">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
It is easier to think when the number is smaller.<br />
<br />
The number of ways to represent 15 using any number of coin is:<br />
<br />
number of ways to represent 15 using coins (1, 2, 5) [by choosing using 0 10 coin]<br />
+<br />
number of ways to represent 5 using coins (1, 2, 5) [by choosing using 1 10 coin]<br />
<br />
Similarly, the number of ways to represent 15 using coin (1, 2, 5) is:<br />
<br />
number of ways to represent 15 using coins (1, 2, 5) [by choosing using 0 5 coin]<br />
+<br />
number of ways to represent 10 using coins (1, 2) [by choosing using 1 5 coin]<br />
+<br />
number of ways to represent 5 using coins (1, 2) [by choosing using 2 5 coin]<br />
+<br />
number of ways to represent 0 using coins (1, 2) [by choosing using 3 5 coin]<br />
<br />
Of course the last term is 1, and now you get the idea how to use recursion to find the number of ways. The code do exactly that.<br />
<br />
<b>Code:</b><br />
<br />
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">using</span> System.Numerics;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem031()
{
<span class="rem" style="color: green;">// Count the number of using different coins</span>
<span class="kwrd" style="color: blue;">int</span>[] coinValues = <span class="kwrd" style="color: blue;">new</span> <span class="kwrd" style="color: blue;">int</span>[] { 1, 2, 5, 10, 20, 50, 100, 200 };
Console.WriteLine(Way(200, coinValues, coinValues.Length - 1));
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">int</span> Way(<span class="kwrd" style="color: blue;">int</span> value, <span class="kwrd" style="color: blue;">int</span>[] coinValues, <span class="kwrd" style="color: blue;">int</span> maxIndex)
{
<span class="rem" style="color: green;">// This is special because we know it is 1, the value is can always be represented as sum of 1 in only 1 way.</span>
<span class="kwrd" style="color: blue;">if</span> (maxIndex == 0)
{
<span class="kwrd" style="color: blue;">return</span> 1;
}
<span class="kwrd" style="color: blue;">int</span> maxValue = coinValues[maxIndex];
<span class="kwrd" style="color: blue;">return</span> Enumerable.Range(0, value / maxValue + 1).Select(t => Way(value - maxValue * t, coinValues, maxIndex - 1)).Aggregate((x, y) => x + y);
}
}
}</pre>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-28819075618191425592014-10-02T07:48:00.001-07:002014-10-02T07:48:31.158-07:00Problem 30 - Digit fifth powers<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="https://projecteuler.net/problem=30">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
The problem can be solved with brute force, just testing if the number matches the digit sum. The only problem is when do we stop the search.<br />
<br />
Observe that the right hand side, despite raised to high power, are relatively small in magnitude since it got broken down into digits. For a six digit number, the maximum possible right hand side is<br />
6x9<sup>5</sup> =354294, which is a 6 digit number, but 7x9<sup>5</sup> = 413343 is not a seven digit number. So all we need to do is to test the 6 digit numbers, in fact, only those less than 354294.<br />
<br />
The rest is trivial. Caching the fifth powers of the digit can help quite a bit.<br />
<br />
<b>Code:</b><br />
<br />
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">class</span> Solution030
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">void</span> Run()
{
Console.WriteLine(GetPowers().Aggregate((x, y) => x + y));
}
<span class="kwrd" style="color: blue;">private</span> IEnumerable<<span class="kwrd" style="color: blue;">int</span>> GetPowers()
{
<span class="kwrd" style="color: blue;">int</span> max = 9 * 9 * 9 * 9 * 9 * 6;
<span class="kwrd" style="color: blue;">int</span>[] powers = Enumerable.Range(0, 10).Select(x => x * x * x * x * x).ToArray();
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 1; i <= max; i++)
{
IEnumerable<<span class="kwrd" style="color: blue;">int</span>> digits = i.ToString().Select(c => c - <span class="str" style="color: #a31515;">'0'</span>);
<span class="kwrd" style="color: blue;">int</span> digitPowerSum = digits.Select(d => powers[d]).Aggregate((x, y) => x + y);
<span class="kwrd" style="color: blue;">if</span> (digitPowerSum == i && i != 1)
{
yield <span class="kwrd" style="color: blue;">return</span> i;
}
}
}
}
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem030()
{
<span class="kwrd" style="color: blue;">new</span> Solution030().Run();
}
}
}</pre>
<br />
In fact, listing the found sums numbers is also fun:<br />
<br />
4150 = 4<sup>5</sup> + 1<sup>5</sup> + 5<sup>5</sup> + 0<sup>5</sup><br />
4151 = 4<sup>5</sup> + 1<sup>5</sup> + 5<sup>5</sup> + 1<sup>5</sup><br />
54748 = 5<sup>5</sup> + 4<sup>5</sup> + 7<sup>5</sup> + 4<sup>5</sup> + 8<sup>5</sup><br />
92727 = 9<sup>5</sup> + 2<sup>5</sup> + 7<sup>5</sup> + 2<sup>5</sup> + 7<sup>5</sup><br />
93084 = 9<sup>5</sup> + 3<sup>5</sup> + 0<sup>5</sup> + 8<sup>5</sup> + 4<sup>5</sup><br />
194979 = 1<sup>5</sup> + 9<sup>5</sup> + 4<sup>5</sup> + 9<sup>5</sup> + 7<sup>5</sup> + 9<sup>5</sup><br />
<br />
<b>Answer: </b>443839</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-35711960993735021982014-10-02T07:25:00.000-07:002014-10-02T07:32:16.574-07:00Problem 29: Distinct Powers<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="https://projecteuler.net/problem=29">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
This is a counting problem. The elements can be big (e.g. 100<sup>100</sup>), but the number of elements is small, just at most 10,000 of them.<br />
<br />
First, note that the set of powers can intersect only if they have the same prime factors with same ratios. For example, power of 2 will intersect with power of 4, but it will never intersect with power of 6. Similarly, power of 6 will never intersect with power of 12.<br />
<br />
So we break the problem down to computing the count of union of some complicated disjoint sets.<br />
<br />
{power of 2 union power of 4 union .. } union ... union { power of 6 union power of 36 union ... } union ...<br />
<br />
As those sets are disjoint, the count of union is just the sum of counts. Now we focus on the compute the count of a particular term.<br />
<br />
To compute the size of a union of a set of sets, we can use the <a href="http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle">inclusion-exclusion principle</a>. In problem 1, we already applied the principle to compute the sum. This one is more complicated.<br />
<div>
<br /></div>
The hard part is to compute the size of an arbitrary intersection. For example, what is the size of {power of 2 union power of 4}?<br />
<br />
Taking logarithm (to base 2 in this case) on the values will make the problem look simpler. Now we have the compute the size of {2, 3, ..., 100}, {4, 6, ..., 200}, so that is just {4, 6, ... 100}, which is 49, easy to compute in this case, but what is the general rule?<br />
<br />
Abstractly, we are given sets of multiples and we wanted to find intersection. They are simply the common multiples. To compute the number of common multiples. We simply find the least common multiple, and then count how many multiple of that least common multiple can stay within the set.<br />
<br />
Last but not least, we have to apply the inclusion-exclusion principle formula. The formula itself look daunting when applied with arbitrary number of sets, but fortunately, the formula can be implemented using gray code enumeration.<br />
<br />
<a href="http://en.wikipedia.org/wiki/Gray_code">Gray code</a> is a specific sequence of binary strings such that adjacent element of the sequence differ by only one bit. A sample sequence of 3 element is shown below:<br />
<br />
000<br />
001<br />
011<br />
010<br />
110<br />
111<br />
101<br />
100<br />
<br />
By definition, the gray code flip one bit every time, so the parity of the sequence alternates (number of 1 is even -> number of 1 is odd -> ...) This is exactly what we need in the inclusion exclusion sum! So I simply adopted the gray code generation algorithm from <a href="http://www-cs-faculty.stanford.edu/~uno/taocp.html">The Art of Computer Programming</a>, and coded the formula.<br />
<br />
As an aside - reverse engineering this piece of code (written two years ago) to the description above isn't easy at all. I should really have written the blog by the time I coded it.<br />
<br />
<b>Code:</b><br />
<b><br /></b>
<br />
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">class</span> Solution029
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">void</span> Run()
{
<span class="kwrd" style="color: blue;">int</span> A = 100;
<span class="kwrd" style="color: blue;">int</span> B = 100;
<span class="kwrd" style="color: blue;">long</span> sum = 0;
<span class="kwrd" style="color: blue;">bool</span>[] processed = <span class="kwrd" style="color: blue;">new</span> <span class="kwrd" style="color: blue;">bool</span>[A + 1];
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> a = 2; a <= A; a++)
{
<span class="kwrd" style="color: blue;">if</span> (!processed[a])
{
<span class="kwrd" style="color: blue;">int</span> numberOfSets = (<span class="kwrd" style="color: blue;">int</span>)Math.Log(B, a);
<span class="kwrd" style="color: blue;">int</span> c = a;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 1; i <= numberOfSets; i++)
{
processed[c] = <span class="kwrd" style="color: blue;">true</span>;
c *= a;
}
IEnumerable<<span class="kwrd" style="color: blue;">long</span>> allPowers = Enumerable.Range(1, numberOfSets).Select(t => (<span class="kwrd" style="color: blue;">long</span>)t);
<span class="kwrd" style="color: blue;">foreach</span> (<span class="kwrd" style="color: blue;">var</span> code <span class="kwrd" style="color: blue;">in</span> Gray(numberOfSets))
{
<span class="kwrd" style="color: blue;">var</span> joined = Enumerable.Zip(allPowers, code.Item1, (x, y) => Tuple.Create(x, y));
<span class="kwrd" style="color: blue;">var</span> powers = joined.Where(t => t.Item2).Select(t => t.Item1);
<span class="kwrd" style="color: blue;">if</span> (powers.Count() == 0)
{
<span class="rem" style="color: green;">// Gray code generate this sequence - but this should simply be discarded since it make</span>
<span class="rem" style="color: green;">// no sense for having an intersection of no sets.</span>
<span class="rem" style="color: green;">// One could argue this is simply empty set and contribute 0 to sum, that's fine too.</span>
<span class="kwrd" style="color: blue;">continue</span>;
}
<span class="rem" style="color: green;">// The size of the intersection of a particular subset can be computed using this formula</span>
<span class="rem" style="color: green;">// min(powers) * B / lcm</span>
<span class="kwrd" style="color: blue;">var</span> lcm = powers.Aggregate((x, y) => CommonMultiple(x, y));
<span class="kwrd" style="color: blue;">var</span> min = powers.Min();
<span class="kwrd" style="color: blue;">var</span> intersectionSize = min * B / lcm;
<span class="kwrd" style="color: blue;">if</span> (powers.Contains(lcm))
{
intersectionSize--;
}
sum = sum + (code.Item2 ? -1 : 1) * intersectionSize;
}
}
}
Console.WriteLine(sum);
}
<span class="rem" style="color: green;">// From "The Art of Computer Programming, book 4"</span>
<span class="kwrd" style="color: blue;">private</span> IEnumerable<Tuple<List<<span class="kwrd" style="color: blue;">bool</span>>, <span class="kwrd" style="color: blue;">bool</span>>> Gray(<span class="kwrd" style="color: blue;">int</span> n)
{
<span class="kwrd" style="color: blue;">int</span> parity = 0;
<span class="kwrd" style="color: blue;">bool</span>[] bits = <span class="kwrd" style="color: blue;">new</span> <span class="kwrd" style="color: blue;">bool</span>[n];
<span class="kwrd" style="color: blue;">int</span> j = 0;
while (<span class="kwrd" style="color: blue;">true</span>)
{
<span class="rem" style="color: green;">// Iterating gray code and present the inclusion-exclusion sum</span>
yield <span class="kwrd" style="color: blue;">return</span> Tuple.Create(bits.ToList(), parity == 0);
parity = 1 - parity;
<span class="kwrd" style="color: blue;">if</span> (parity == 1)
{
j = 0;
}
<span class="kwrd" style="color: blue;">else</span>
{
<span class="kwrd" style="color: blue;">int</span> k = 0;
while (<span class="kwrd" style="color: blue;">true</span>)
{
<span class="kwrd" style="color: blue;">if</span> (bits[k])
{
<span class="kwrd" style="color: blue;">break</span>;
}
<span class="kwrd" style="color: blue;">else</span>
{
k++;
}
}
<span class="rem" style="color: green;">// Now we know bits[k] is true, and the minimal such k, then </span>
j = k + 1;
}
<span class="kwrd" style="color: blue;">if</span> (j == n)
{
yield <span class="kwrd" style="color: blue;">break</span>;
}
<span class="kwrd" style="color: blue;">else</span>
{
bits[j] = !bits[j];
}
}
}
}
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem029()
{
<span class="kwrd" style="color: blue;">new</span> Solution029().Run();
}
}
}</pre>
<b><br /></b>
<b>Answer: </b>9183</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-49113087321027766882014-09-23T07:28:00.000-07:002014-09-23T07:28:10.253-07:00Problem 28: Number spiral diagonals<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="https://projecteuler.net/problem=28">here</a>.<br />
<br />
<b>Solution:</b><br />
<b><br /></b>
Since 1001<sup>2</sup> is small, I could have just fill the spiral and compute the sum. In fact, that is how I got the answer accepted for the first time. But I decide this is a chance for me to do some math, and so I do.<br />
<span id="ctl00_ContentPlaceHolder1_output" style="background-color: white; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: x-small;"></span><span style="background-color: white; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: x-small;"></span><br />
<pre class="csharpcode" style="background-color: white; color: black; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"></pre>
<br />
First notice the spiral (except the initial 1) can be decomposed into "Shells", each shell starts with the upper right corner and ends with a perfect square at the upper left corner. The values at the corners forms an arithmetic progression with common difference 2 * i, where i is the shell number, starting from 1.<br />
<br />
With that observation, it is easy to translate that to the code below.<br />
<br />
Apparently, the code can be further simplified, but I am not doing that in the code for simplicity.<br />
<br />
Using Matlab, we can simplify this quickly using the commands below<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">clear</span><br />
<span style="font-family: Courier New, Courier, monospace;">syms i</span><br />
<span style="font-family: Courier New, Courier, monospace;">e = (2 * i + 1)^2</span><br />
<span style="font-family: Courier New, Courier, monospace;">d = 2 * i</span><br />
<span style="font-family: Courier New, Courier, monospace;">s = e - 3 * d</span><br />
<span style="font-family: Courier New, Courier, monospace;">t = (s + e) * 4 / 2</span><br />
<span style="font-family: Courier New, Courier, monospace;">expand(t)</span><br />
<b><br /></b>
Now t = 16i<sup>2</sup>+4i+4 is the term for summation, given the summation formula, we can even sum them up directly as follow<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">clear</span><br />
<span style="font-family: Courier New, Courier, monospace;">syms n</span><br />
<span style="font-family: Courier New, Courier, monospace;">q = n * (n + 1) * (2 * n + 1) / 6</span><br />
<span style="font-family: Courier New, Courier, monospace;">l = n * (n + 1) / 2</span><br />
<span style="font-family: Courier New, Courier, monospace;">o = 16 * q + 4 * l + 4 * n + 1</span><br />
<span style="font-family: Courier New, Courier, monospace;">expand(o)</span><br />
<br />
That gives the overall sum formula to be 16/3*n^3+10*n^2+26/3*n+1, an amazing simple cubic equation.<br />
<br />
<b>Code:</b><br />
<b><br /></b>
<span class="kwrd" style="color: blue; font-family: Consolas, 'Courier New', Courier, monospace; font-size: x-small;">namespace</span><span style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: x-small;"> Euler</span><br />
<pre class="csharpcode" style="background-color: white; color: black; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;">{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem028()
{
<span class="kwrd" style="color: blue;">long</span> sum = 1;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 1; i < (1001 + 1) / 2; i++)
{
<span class="kwrd" style="color: blue;">long</span> end = (2 * i + 1) * (2 * i + 1);
<span class="kwrd" style="color: blue;">long</span> diff = 2 * i;
<span class="kwrd" style="color: blue;">long</span> start = end - 3 * diff;
sum += (start + end) * 4 / 2;
}
Console.WriteLine(sum);
}
}
}
</pre>
<b><br /></b>
<b>Answer: </b>669171001</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-21573320744618316312014-09-05T09:27:00.002-07:002014-09-05T23:31:02.991-07:00Problem 27: Quadratic primes<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=27">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
There isn't much we could do with this one, just try them all and find the best. The only optimization I have done is cache the is prime check, and it is quick enough for now.<br />
<br />
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> Dictionary<<span class="kwrd" style="color: blue;">long</span>, <span class="kwrd" style="color: blue;">bool</span>> primeCache = <span class="kwrd" style="color: blue;">new</span> Dictionary<<span class="kwrd" style="color: blue;">long</span>, <span class="kwrd" style="color: blue;">bool</span>>();
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem027()
{
Tuple<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>> best = Tuple.Create(-1, -1);
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> a = -1000; a <= 1000; a++)
{
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> b = -1000; b <= 1000; b++)
{
<span class="kwrd" style="color: blue;">long</span> current = 0;
<span class="kwrd" style="color: blue;">int</span> length = 0;
while (<span class="kwrd" style="color: blue;">true</span>)
{
<span class="kwrd" style="color: blue;">long</span> value = current * current + a * current + b;
<span class="kwrd" style="color: blue;">if</span> (!IsPrime(value))
{
<span class="kwrd" style="color: blue;">break</span>;
}
length++;
current++;
}
<span class="kwrd" style="color: blue;">if</span> (length > best.Item1)
{
best = Tuple.Create(length, a * b);
}
};
};
Console.WriteLine(best.Item1);
Console.WriteLine(best.Item2);
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">bool</span> IsPrime(<span class="kwrd" style="color: blue;">long</span> x)
{
<span class="kwrd" style="color: blue;">if</span> (x < 0)
{
x = -x;
}
<span class="kwrd" style="color: blue;">bool</span> result;
<span class="kwrd" style="color: blue;">if</span> (primeCache.TryGetValue(x, <span class="kwrd" style="color: blue;">out</span> result))
{
<span class="kwrd" style="color: blue;">return</span> result;
}
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">long</span> y = 2; y < x; y++)
{
<span class="kwrd" style="color: blue;">if</span> (x % y == 0)
{
primeCache.Add(x, <span class="kwrd" style="color: blue;">false</span>);
<span class="kwrd" style="color: blue;">return</span> <span class="kwrd" style="color: blue;">false</span>;
}
}
primeCache.Add(x, <span class="kwrd" style="color: blue;">true</span>);
<span class="kwrd" style="color: blue;">return</span> <span class="kwrd" style="color: blue;">true</span>;
}
}
}</pre>
<br />
<b>Answer: -</b>59231<br />
<br />
Given the restriction - the best quadratic formula can only output 71 primes.</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-33878193199130895182014-09-05T07:43:00.002-07:002014-09-05T23:29:22.180-07:00Problem 26:Reciprocal cycles<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=26">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
The key for this problem is to find the recurring cycle. For human, finding the recurring cycle involve long division and finding repeating dividend. We can code exactly that by dividing, multiply the remainder by 10 (much like adding zero in long division), and divide again, until we see the same dividend again.<br />
<br />
<link href="csharp.css" rel="stylesheet" type="text/css"></link>
<br />
<pre class="csharpcode"><pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem026()
{
IEnumerable<Tuple<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>>> recurringPartLength = GetRecurringPartLengths();
<span class="kwrd" style="color: blue;">int</span> maxLength = recurringPartLength.Select(t => t.Item2).Max();
Console.WriteLine(recurringPartLength.Single(t => t.Item2 == maxLength).Item1);
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> IEnumerable<Tuple<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>>> GetRecurringPartLengths()
{
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> d = 2; d < 1000; d++)
{
Tuple<List<<span class="kwrd" style="color: blue;">int</span>>, <span class="kwrd" style="color: blue;">int</span>> decimalRepresentation = GetDecimalRepresentation(d);
<span class="kwrd" style="color: blue;">if</span> (decimalRepresentation != <span class="kwrd" style="color: blue;">null</span>)
{
IEnumerable<<span class="kwrd" style="color: blue;">int</span>> recurringPart = decimalRepresentation.Item1.Skip(decimalRepresentation.Item2 - 1);
yield <span class="kwrd" style="color: blue;">return</span> Tuple.Create(d, recurringPart.Count());
}
}
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> Tuple<List<<span class="kwrd" style="color: blue;">int</span>>, <span class="kwrd" style="color: blue;">int</span>> GetDecimalRepresentation(<span class="kwrd" style="color: blue;">int</span> d)
{
<span class="kwrd" style="color: blue;">int</span> n = 1;
List<<span class="kwrd" style="color: blue;">int</span>> quotients = <span class="kwrd" style="color: blue;">new</span> List<<span class="kwrd" style="color: blue;">int</span>>();
<span class="rem" style="color: green;">// We need to stop when we see the same number to divide - we already know what would happen</span>
Dictionary<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>> seen = <span class="kwrd" style="color: blue;">new</span> Dictionary<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>>();
<span class="kwrd" style="color: blue;">int</span> position = 0;
while (<span class="kwrd" style="color: blue;">true</span>)
{
n = n * 10;
position++;
<span class="kwrd" style="color: blue;">int</span> previousIndex;
<span class="kwrd" style="color: blue;">if</span> (seen.TryGetValue(n, <span class="kwrd" style="color: blue;">out</span> previousIndex))
{
<span class="kwrd" style="color: blue;">return</span> Tuple.Create(quotients, previousIndex);
}
<span class="kwrd" style="color: blue;">else</span>
{
seen.Add(n, position);
<span class="kwrd" style="color: blue;">int</span> quotient = n / d;
quotients.Add(quotient);
}
n = n % d;
<span class="kwrd" style="color: blue;">if</span> (n == 0)
{
<span class="kwrd" style="color: blue;">return</span> <span class="kwrd" style="color: blue;">null</span>;
}
}
}
}
}</pre>
</pre>
<br />
<b>Answer: </b>983</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-49066175943785104342014-09-04T09:09:00.001-07:002014-09-05T23:28:59.833-07:00Problem 25: 1000-digit Fibonacci number<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=25">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
It is not hard to find online the <a href="http://en.wikipedia.org/wiki/Jacques_Philippe_Marie_Binet">Binet formula</a> to compute Fibonacci number.<br />
$ F_n = (\frac{\sqrt{5} + 1}{2})^n + (\frac{\sqrt{5} - 1}{2})^n $
<br />
<br />
Note that the second term is an exponential of a number less than 1, that goes to 0 quickly, so let's just ignore that and we get a good approximation<br />
<br />
$
\begin{eqnarray*}
F_n & \simeq & (\frac{\sqrt{5} + 1}{2})^n \\
\log(F_n) & \simeq & n \log (\frac{\sqrt{5} + 1}{2})
\end{eqnarray*}
$
<br />
<br />
This gives us $ n \simeq 4785 $ when $ \log(F_n) \simeq 1000 $. That means if we use the trivial algorithm for computing Fibonacci number, it takes around 4785 additions and we will get the answer. However, since we know the answer will be approximately 4785, we have a much faster algorithm that allow us to compute $ F_{4785} $.<br />
<br />
The algorithm start with observing the matrix<br />
<br />
$
\begin{eqnarray*}
\left(\begin{matrix}1 & 1 \\ 1 & 0\end{matrix}\right)^n = \left(\begin{matrix}F_{n+1} & F_{n} \\ F_{n} & 0\end{matrix}\right)
\end{eqnarray*}
$
<br />
<br />
With that, we can easily compute $ F_n $ by <a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring">repeated squaring</a>. Observing the matrix is symmetric we can reduce some arithmetic operations as well.<br />
<br />
Once we get to the approximate solution, we need to walk to the solution. By some computation I know $ F_{4785} $ has 1,000 digits, so we need to walk backwards to see when it get started to become 999 digits, and that's when we can stop.<br />
<br />
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Numerics;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem025()
{
<span class="kwrd" style="color: blue;">new</span> Solution025().Execute();
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">class</span> Solution025
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">void</span> Execute()
{
FibMatrix one = <span class="kwrd" style="color: blue;">new</span> FibMatrix
{
a = 1,
b = 1,
d = 0
};
<span class="rem" style="color: green;">// By Binet formula approximation, we know the solution is around this</span>
<span class="kwrd" style="color: blue;">int</span> n = 4784;
FibMatrix m = Power(one, n, one, Multiply);
BigInteger big = m.a;
BigInteger small = m.b;
<span class="rem" style="color: green;">// small is the nth Fibonacci number</span>
<span class="rem" style="color: green;">// I already know small has 1000 digits by debugging, so I know I need to going backwards</span>
<span class="rem" style="color: green;">// in full generality I need to check if I need forward as well</span>
while (small.ToString().Length >= 1000)
{
BigInteger prev = big - small;
big = small;
small = prev;
n--;
<span class="rem" style="color: green;">// small is still the nth Fibonacci number after the line</span>
}
<span class="rem" style="color: green;">// Small has 999 digits, big has 1000 digit, so the answer is n + 1</span>
Console.WriteLine(n + 1);
}
<span class="kwrd" style="color: blue;">private</span> FibMatrix Multiply(FibMatrix p, FibMatrix q)
{
FibMatrix result = <span class="kwrd" style="color: blue;">new</span> FibMatrix();
result.a = p.a * q.a + p.b * q.b;
result.b = p.a * q.b + p.b * q.d;
result.d = p.b * q.b + p.d * q.d;
<span class="kwrd" style="color: blue;">return</span> result;
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">class</span> FibMatrix
{
<span class="kwrd" style="color: blue;">public</span> BigInteger a;
<span class="kwrd" style="color: blue;">public</span> BigInteger b;
<span class="kwrd" style="color: blue;">public</span> BigInteger d;
}
}
}
}</pre>
<br />
<b>Answer: </b>4782<br />
<br />
Note how close is it for our analytic approximation.</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-5157276800884474062014-09-03T09:00:00.000-07:002014-09-05T23:28:52.661-07:00Problem 24: Lexicographic permutations<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: justify;">
<div style="text-align: left;">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=24">here</a>.</div>
<div>
<br /></div>
</div>
<div style="text-align: justify;">
<b>Solution:</b></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
By dividing the set of permutations by the first digit into partitions, the set of all permutation of n digits can be divided into n partitions of size (n-1)!. The first thing to do is to determine which partition the kth permutation belongs to, it can easily computed to be floor((k - 1)/(n-1)!), that determine the first digit. Then, we know it is the (k-1) % (n-1)! permutation in the remaining digits, so we can just compute that recursively.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Once we have the analysis, the code came by really easily.</div>
<div style="text-align: justify;">
<br /></div>
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem024()
{
<span class="kwrd" style="color: blue;">int</span>[] factorials = <span class="kwrd" style="color: blue;">new</span> <span class="kwrd" style="color: blue;">int</span>[11];
factorials[0] = 1;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 1; i <= 10; i++)
{
factorials[i] = factorials[i - 1] * i;
}
<span class="rem" style="color: green;">// There are nine factorials number starts with 0</span>
<span class="rem" style="color: green;">// There are nine factorials number starts with 1, </span>
<span class="rem" style="color: green;">// ...</span>
<span class="kwrd" style="color: blue;">int</span> current = 1000000 - 1;
List<<span class="kwrd" style="color: blue;">int</span>> availableDigits = Enumerable.Range(0, 10).ToList();
while (availableDigits.Count > 0)
{
<span class="kwrd" style="color: blue;">int</span> partitionSize = factorials[availableDigits.Count - 1];
<span class="kwrd" style="color: blue;">int</span> quotient = current / partitionSize;
<span class="kwrd" style="color: blue;">int</span> remainder = current % partitionSize;
<span class="kwrd" style="color: blue;">int</span> partitionNumber = quotient + 1;
current = remainder;
Console.Write(availableDigits[partitionNumber - 1]);
availableDigits.RemoveAt(partitionNumber - 1);
}
Console.WriteLine();
}
}
}</pre>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>Answer: </b>2783915460</div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-80913459530834283942014-09-03T08:32:00.001-07:002014-09-05T23:28:41.659-07:00Problem 23: Non-abundant sums<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: justify;">
<div style="text-align: left;">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=23">here</a>.</div>
</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>Solution:</b><br />
<b><br /></b></div>
<div style="text-align: justify;">
As we have already explained in <a href="http://andrew-euler.blogspot.com/2014/09/problem-21-amicable-numbers.html">Problem 21</a>, it is easy to tell if a number is abundant by computing the sum of proper divisor function. Since we are given that every number larger than 28123 can be written as sum of two abundant numbers, so we don't have to consider any of the abundant numbers larger than that.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
So we first creating a set of all abundant numbers less than 28124 (turn out there are around 7,000 of them), then we create the set of all abundant number sums. Finally, we evaluate all the number below 28124 and test if they're sum of abundant number, that's all.</div>
<div style="text-align: justify;">
<br /></div>
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem023()
{
List<<span class="kwrd" style="color: blue;">int</span>> abundantNumbers = <span class="kwrd" style="color: blue;">new</span> List<<span class="kwrd" style="color: blue;">int</span>>();
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 2; i <= 28124; i++)
{
<span class="kwrd" style="color: blue;">if</span> (IsAbundantNumbers(i))
{
abundantNumbers.Add(i);
}
}
HashSet<<span class="kwrd" style="color: blue;">int</span>> abundantSums = <span class="kwrd" style="color: blue;">new</span> HashSet<<span class="kwrd" style="color: blue;">int</span>>();
<span class="kwrd" style="color: blue;">foreach</span> (<span class="kwrd" style="color: blue;">int</span> abundantNumber1 <span class="kwrd" style="color: blue;">in</span> abundantNumbers)
{
<span class="kwrd" style="color: blue;">foreach</span> (<span class="kwrd" style="color: blue;">int</span> abundantNumber2 <span class="kwrd" style="color: blue;">in</span> abundantNumbers)
{
abundantSums.Add(abundantNumber1 + abundantNumber2);
}
}</pre>
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"> <span class="kwrd" style="color: blue;">long</span> answer = (1 + 23) * 23 / 2;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 24; i < 28124; i++)
{
<span class="kwrd" style="color: blue;">if</span> (!abundantSums.Contains(i))
{
answer += i;
}
}
Console.WriteLine(answer);
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">bool</span> IsAbundantNumbers(<span class="kwrd" style="color: blue;">int</span> i)
{
<span class="kwrd" style="color: blue;">return</span> SumOfProperDivisor(i) > i;
}
}
}</pre>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Note that the code reused the SumOfProperDivisor function in <a href="http://andrew-euler.blogspot.com/2014/09/problem-21-amicable-numbers.html">Problem 21</a>.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>Answer: </b>4179871</div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-18626467959588903522014-09-01T19:19:00.001-07:002014-09-05T23:28:32.877-07:00Problem 22: Names scores<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=22">here</a>.<br />
<div>
<br /></div>
<b>Solution:</b><br />
<br />
Just compute all the scores and add them up. Nothing special, so I will just post the code.<br />
<br />
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><pre class="csharpcode" style="font-family: Consolas, 'Courier New', Courier, monospace;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem022()
{
<span class="kwrd" style="color: blue;">string</span>[] names = ReadResourceAsString(<span class="str" style="color: #a31515;">"Euler.Problem022.txt"</span>).Split(<span class="kwrd" style="color: blue;">new</span> <span class="kwrd" style="color: blue;">char</span>[] { <span class="str" style="color: #a31515;">'"'</span>, <span class="str" style="color: #a31515;">','</span> }, StringSplitOptions.RemoveEmptyEntries);
Array.Sort(names);
<span class="kwrd" style="color: blue;">var</span> nameValues = names.Select((s, i) => Tuple.Create(s, i + 1L)).Select(t => Tuple.Create(t.Item1, t.Item1.Select(c => c - <span class="str" style="color: #a31515;">'A'</span> + 1).Aggregate((x, y) => x + y), t.Item2));
Console.WriteLine(nameValues.Select(t => t.Item2 * t.Item3).Aggregate((x, y) => x + y));
}
}
}</pre>
<pre class="csharpcode" style="font-family: Consolas, 'Courier New', Courier, monospace;"></pre>
</pre>
<b>Answer: </b>871198282<br />
<br /></div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-86380880966689568062014-09-01T13:48:00.002-07:002014-09-05T23:28:21.226-07:00Problem 21: Amicable numbers<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=21">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
<div style="text-align: justify;">
Finally, we got another problem that feel like more number theoretic. A straightforward implementation would be checking, for each number i under 10000, if the SumOfProperDivisor(SumOfProperDivisor(i)) == i, and if so, add it to the sum, and that's all.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Therefore the problem becomes computing sum of proper divisor, turn out it is easier to consider the sum of divisor first. The sum of divisor, like the <a href="http://en.wikipedia.org/wiki/Divisor_function">divisor function</a> we encountered in <a href="http://andrew-euler.blogspot.com/2013/08/problem-12-highly-divisible-triangular.html">problem 12</a>, is <a href="http://en.wikipedia.org/wiki/Multiplicative_function">multiplicative</a>. Just like in proving the divisor function is multiplicative, we use the one to one correspondence between the a divisor of pq and the divisor of p, divisor of q pair. Now group the pairs by the first component we can see the sum and be factorized and we can see the sum of divisor function is multiplicative. The sum of divisor function for a prime power is simply a geometric series and is easily evaluated. </div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The last twist in the problem is the SumOfProperDivisor(SumOfProperDivisor(i)) part. Turn out SumOfProperDivisor(i) can be larger than i (which are called <a href="http://en.wikipedia.org/wiki/Abundant_number">abundant numbers</a>), so we need to evaluate more SumOfProperDivisor(i) to its max to make sure we don't index out of bound.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Without further ado, here is the code:</div>
<div style="text-align: justify;">
<br /></div>
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem021()
{
Dictionary<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>> d = <span class="kwrd" style="color: blue;">new</span> Dictionary<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>>();
d.Add(1, 0);
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 2; i <= 10000; i++)
{
d.Add(i, SumOfProperDivisor(i));
}
<span class="kwrd" style="color: blue;">long</span> maxSumOfDivisorWithin10000 = d.Values.Max();
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 10001; i <= maxSumOfDivisorWithin10000; i++)
{
d.Add(i, SumOfProperDivisor(i));
}
Console.WriteLine(AmicableNumbers(d).Aggregate((x, y) => x + y));
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> IEnumerable<<span class="kwrd" style="color: blue;">int</span>> AmicableNumbers(Dictionary<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>> d)
{
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 2; i <= 10000; i++)
{
<span class="kwrd" style="color: blue;">if</span> (d[d[i]] == i & i != d[i])
{
yield <span class="kwrd" style="color: blue;">return</span> i;
}
}
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">int</span> SumOfProperDivisor(<span class="kwrd" style="color: blue;">int</span> i)
{
<span class="kwrd" style="color: blue;">return</span> SumOfDivisor(i) - i;
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">int</span> SumOfDivisor(<span class="kwrd" style="color: blue;">int</span> i)
{
<span class="kwrd" style="color: blue;">var</span> groupedFactors = BruteForceFactor(i).ToList();
<span class="kwrd" style="color: blue;">return</span> groupedFactors.Select(kvp => (Power(kvp.Item1, kvp.Item2 + 1) - 1) / (kvp.Item1 - 1)).Aggregate((x, y) => x * y);
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">int</span> Power(<span class="kwrd" style="color: blue;">int</span> x, <span class="kwrd" style="color: blue;">int</span> y)
{
<span class="kwrd" style="color: blue;">if</span> (y == 0)
{
<span class="kwrd" style="color: blue;">return</span> 1;
}
<span class="kwrd" style="color: blue;">else</span> <span class="kwrd" style="color: blue;">if</span> (y == 1)
{
<span class="kwrd" style="color: blue;">return</span> x;
}
<span class="kwrd" style="color: blue;">else</span>
{
<span class="kwrd" style="color: blue;">int</span> r = Power(x, y / 2);
<span class="kwrd" style="color: blue;">return</span> y % 2 == 0 ? r * r : r * r * x;
}
}
}
}</pre>
<br />
We could have optimized the factoring by eliminating trials using the <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve_of_Eratosthenes</a>. The idea is, instead of crossing out the number, we compute the power and store the information along. So at the end of the sieve, we got all factorizations we will need. It don't bother me to optimize right now as the performance of the previous code is fine.<br />
<br />
Note that we reused the BruteForceFactor routine from <a href="http://andrew-euler.blogspot.com/2013/08/problem-12-highly-divisible-triangular.html">problem 12</a>.<br />
<br />
<b>Answer: </b>31626</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-8477890130759687012014-08-31T13:08:00.000-07:002014-09-05T23:32:08.533-07:00Problem 20: Factorial digit sum<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=20">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
It is well known that we can use <a href="http://en.wikipedia.org/wiki/Stirling's_approximation">Strling's approximation</a> to approximate factorial, let see what we'll get from it. First of all, we have<br />
$
\begin{eqnarray*}
\sqrt{2 \pi} n^{n+\frac{1}{2}} e^{-n} \leq n! \leq e n^{n+\frac{1}{2}} e^{-n}
\end{eqnarray*}
$
<br />
<br />
Only the term $n^{n+\frac{1}{2}}e^{-n}$ matters, the rest are small. That gives us 100! is approximately $ 1.01 \times 10^{158} $.<br />
<br />
This number is not small, but it is manageable to just compute 100! I don't have other solution to compute the sum of the digits anyway. Here is the code<br />
<br />
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">using</span> System.Numerics;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem020()
{
BigInteger prod = <span class="kwrd" style="color: blue;">new</span> BigInteger(1);
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 2; i <= 100; i++)
{
prod = BigInteger.Multiply(prod, <span class="kwrd" style="color: blue;">new</span> BigInteger(i));
}
Console.WriteLine(prod.ToString().Select(i => i - <span class="str" style="color: #a31515;">'0'</span>).Aggregate((x, y) => x + y));
}
}
}</pre>
<br />
<b>Answer: </b>648<br />
<br />
The value of 100! is actually<br />
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000<br />
<div>
<br /></div>
<div>
It has 159 digits, so the Stirling approximation above is pretty close.</div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-45568008336549997282014-08-31T12:50:00.001-07:002014-09-05T23:21:25.225-07:00Problem 19: Counting Sundays<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=19">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
We might be able to compute it by the description, but it is much easier to use the built-in calendar. Here is the code:<br />
<br />
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Problem019
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Main(<span class="kwrd" style="color: blue;">string</span>[] args)
{
<span class="kwrd" style="color: blue;">int</span> sum = 0;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> year = 1901; year <= 2000; year++)
{
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> month = 1; month <= 12; month++)
{
<span class="kwrd" style="color: blue;">if</span> (<span class="kwrd" style="color: blue;">new</span> DateTime(year, month, 1).DayOfWeek == DayOfWeek.Sunday)
{
sum++;
}
}
}
Console.WriteLine(sum);
}
}
}</pre>
<br />
<b>Answer: </b>171</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-8376315536040247942013-12-20T13:08:00.000-08:002014-09-05T23:21:09.617-07:00Problem 18: Maximum Path Sum I<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=18">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
Instead of solving it by brute force, I think it is easier to solve it with <a href="http://en.wikipedia.org/wiki/Dynamic_programming">dynamic programming</a>. First, let generalize the problem by asking the question - what is the maximum route from an arbitrary node to bottom? The base case is really simple. If you are trying to go from the bottom row to the bottom row, there is only one route with one node, and therefore the maximum total is the node value itself. Now, if we want to reach the node 2 (1st in the 3rd row) in the first triangle, we will pick the left route because 2 + 8 has a bigger sum than 2 + 5. The rule generally applies. If we want to go to 7 (the 1st in the 2nd row), we pick from its children the one with maximum total.<br />
<br />
That translate to a dynamic programming algorithm as follow:<br />
<br />
maximum_total_cost(last_row) = last_row value<br />
maximum_total_cost(any node n ) = n + max(maximum_total_cost(left_child) + maximum_total_cost(right_child)).<br />
<br />
Without further ado, here is the code for the problem:<br />
<br />
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">using</span> System.Numerics;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem018()
{
<span class="kwrd" style="color: blue;">string</span> input = ReadResourceAsString(<span class="str" style="color: #a31515;">"Euler.Problem018.txt"</span>);
<span class="kwrd" style="color: blue;">int</span>[] inputParsed = input.Replace(<span class="str" style="color: #a31515;">'\r'</span>, <span class="str" style="color: #a31515;">' '</span>).Replace(<span class="str" style="color: #a31515;">'\n'</span>, <span class="str" style="color: #a31515;">' '</span>).Split(<span class="kwrd" style="color: blue;">new</span> <span class="kwrd" style="color: blue;">char</span>[] { <span class="str" style="color: #a31515;">' '</span> }, StringSplitOptions.RemoveEmptyEntries).Select(x => Int32.Parse(x)).ToArray();
<span class="kwrd" style="color: blue;">int</span> numRows = 15;
<span class="rem" style="color: green;">// answer(row, column) = data[row, column] + max(answer(row + 1, column), answer(row + 1, column + 1));</span>
<span class="kwrd" style="color: blue;">int</span>[,] answer = <span class="kwrd" style="color: blue;">new</span> <span class="kwrd" style="color: blue;">int</span>[numRows, numRows];
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 1; i <= numRows; i++)
{
answer[i - 1, numRows - 1] = inputParsed[i + numRows * (numRows - 1) / 2 - 1];
}
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> currentRow = numRows - 1; currentRow > 0; currentRow--)
{
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> currentColumn = 1; currentColumn <= currentRow; currentColumn++)
{
<span class="kwrd" style="color: blue;">int</span> currentValue = inputParsed[currentColumn + currentRow * (currentRow - 1) / 2 - 1];
answer[currentColumn - 1, currentRow - 1] = currentValue + Math.Max(answer[currentColumn - 1, currentRow + 1 - 1], answer[currentColumn + 1 - 1, currentRow + 1 - 1]);
}
}
Console.WriteLine(answer[0, 0]);
}
}
}</pre>
<br />
<b>Answer: </b>1074</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-45090239084293333212013-12-20T12:56:00.002-08:002014-09-05T23:20:55.970-07:00Problem 17: Number letter counts<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=17">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
Just implement the rules - nothing special about this problem, here is the code. Note that ToEnglishString() works only if the input is between 1 to 1000, which is enough for the purpose.<br />
<br />
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem017()
{
Console.WriteLine(Enumerable.Range(1, 1000).Select(i => ToEnglishString(i).Replace(<span class="str" style="color: #a31515;">" "</span>, <span class="kwrd" style="color: blue;">string</span>.Empty).Length).Aggregate((x, y) => x + y));
}
<span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">string</span> ToEnglishString(<span class="kwrd" style="color: blue;">int</span> i)
{
<span class="kwrd" style="color: blue;">string</span> ONE = <span class="str" style="color: #a31515;">"one"</span>;
<span class="kwrd" style="color: blue;">string</span> TWO = <span class="str" style="color: #a31515;">"two"</span>;
<span class="kwrd" style="color: blue;">string</span> THREE = <span class="str" style="color: #a31515;">"three"</span>;
<span class="kwrd" style="color: blue;">string</span> FOUR = <span class="str" style="color: #a31515;">"four"</span>;
<span class="kwrd" style="color: blue;">string</span> FIVE = <span class="str" style="color: #a31515;">"five"</span>;
<span class="kwrd" style="color: blue;">string</span> SIX = <span class="str" style="color: #a31515;">"six"</span>;
<span class="kwrd" style="color: blue;">string</span> SEVEN = <span class="str" style="color: #a31515;">"seven"</span>;
<span class="kwrd" style="color: blue;">string</span> EIGHT = <span class="str" style="color: #a31515;">"eight"</span>;
<span class="kwrd" style="color: blue;">string</span> NINE = <span class="str" style="color: #a31515;">"nine"</span>;
<span class="kwrd" style="color: blue;">string</span> TEN = <span class="str" style="color: #a31515;">"ten"</span>;
<span class="kwrd" style="color: blue;">string</span> ELEVEN = <span class="str" style="color: #a31515;">"eleven"</span>;
<span class="kwrd" style="color: blue;">string</span> TWELVE = <span class="str" style="color: #a31515;">"twelve "</span>;
<span class="kwrd" style="color: blue;">string</span> THIRTEEN = <span class="str" style="color: #a31515;">"thirteen"</span>;
<span class="kwrd" style="color: blue;">string</span> FOURTEEN = <span class="str" style="color: #a31515;">"fourteen"</span>;
<span class="kwrd" style="color: blue;">string</span> FIFTEEN = <span class="str" style="color: #a31515;">"fifteen"</span>;
<span class="kwrd" style="color: blue;">string</span> SIXTEEN = <span class="str" style="color: #a31515;">"sixteen"</span>;
<span class="kwrd" style="color: blue;">string</span> SEVENTEEN = <span class="str" style="color: #a31515;">"seventeen"</span>;
<span class="kwrd" style="color: blue;">string</span> EIGHTEEN = <span class="str" style="color: #a31515;">"eighteen"</span>;
<span class="kwrd" style="color: blue;">string</span> NINETEEN = <span class="str" style="color: #a31515;">"nineteen"</span>;
<span class="kwrd" style="color: blue;">string</span> TWENTY = <span class="str" style="color: #a31515;">"twenty"</span>;
<span class="kwrd" style="color: blue;">string</span> THIRTY = <span class="str" style="color: #a31515;">"thirty"</span>;
<span class="kwrd" style="color: blue;">string</span> FORTY = <span class="str" style="color: #a31515;">"forty"</span>;
<span class="kwrd" style="color: blue;">string</span> FIFTY = <span class="str" style="color: #a31515;">"fifty"</span>;
<span class="kwrd" style="color: blue;">string</span> SIXTY = <span class="str" style="color: #a31515;">"sixty"</span>;
<span class="kwrd" style="color: blue;">string</span> SEVENTY = <span class="str" style="color: #a31515;">"seventy"</span>;
<span class="kwrd" style="color: blue;">string</span> EIGHTY = <span class="str" style="color: #a31515;">"eighty"</span>;
<span class="kwrd" style="color: blue;">string</span> NINETY = <span class="str" style="color: #a31515;">"ninety"</span>;
<span class="kwrd" style="color: blue;">string</span> HUNDRED = <span class="str" style="color: #a31515;">"hundred"</span>;
<span class="kwrd" style="color: blue;">string</span> THOUSAND = <span class="str" style="color: #a31515;">"thousand"</span>;
<span class="kwrd" style="color: blue;">switch</span> (i)
{
<span class="kwrd" style="color: blue;">case</span> 1000: <span class="kwrd" style="color: blue;">return</span> ONE + <span class="str" style="color: #a31515;">" "</span> + THOUSAND;
<span class="kwrd" style="color: blue;">case</span> 1: <span class="kwrd" style="color: blue;">return</span> ONE;
<span class="kwrd" style="color: blue;">case</span> 2: <span class="kwrd" style="color: blue;">return</span> TWO;
<span class="kwrd" style="color: blue;">case</span> 3: <span class="kwrd" style="color: blue;">return</span> THREE;
<span class="kwrd" style="color: blue;">case</span> 4: <span class="kwrd" style="color: blue;">return</span> FOUR;
<span class="kwrd" style="color: blue;">case</span> 5: <span class="kwrd" style="color: blue;">return</span> FIVE;
<span class="kwrd" style="color: blue;">case</span> 6: <span class="kwrd" style="color: blue;">return</span> SIX;
<span class="kwrd" style="color: blue;">case</span> 7: <span class="kwrd" style="color: blue;">return</span> SEVEN;
<span class="kwrd" style="color: blue;">case</span> 8: <span class="kwrd" style="color: blue;">return</span> EIGHT;
<span class="kwrd" style="color: blue;">case</span> 9: <span class="kwrd" style="color: blue;">return</span> NINE;
<span class="kwrd" style="color: blue;">case</span> 10: <span class="kwrd" style="color: blue;">return</span> TEN;
<span class="kwrd" style="color: blue;">case</span> 11: <span class="kwrd" style="color: blue;">return</span> ELEVEN;
<span class="kwrd" style="color: blue;">case</span> 12: <span class="kwrd" style="color: blue;">return</span> TWELVE;
<span class="kwrd" style="color: blue;">case</span> 13: <span class="kwrd" style="color: blue;">return</span> THIRTEEN;
<span class="kwrd" style="color: blue;">case</span> 14: <span class="kwrd" style="color: blue;">return</span> FOURTEEN;
<span class="kwrd" style="color: blue;">case</span> 15: <span class="kwrd" style="color: blue;">return</span> FIFTEEN;
<span class="kwrd" style="color: blue;">case</span> 16: <span class="kwrd" style="color: blue;">return</span> SIXTEEN;
<span class="kwrd" style="color: blue;">case</span> 17: <span class="kwrd" style="color: blue;">return</span> SEVENTEEN;
<span class="kwrd" style="color: blue;">case</span> 18: <span class="kwrd" style="color: blue;">return</span> EIGHTEEN;
<span class="kwrd" style="color: blue;">case</span> 19: <span class="kwrd" style="color: blue;">return</span> NINETEEN;
<span class="kwrd" style="color: blue;">case</span> 20: <span class="kwrd" style="color: blue;">return</span> TWENTY;
<span class="kwrd" style="color: blue;">default</span>:
<span class="kwrd" style="color: blue;">string</span> result = <span class="kwrd" style="color: blue;">string</span>.Empty;
<span class="kwrd" style="color: blue;">int</span> remaining;
<span class="kwrd" style="color: blue;">int</span> hundredthDigit = i / 100;
remaining = i - hundredthDigit * 100;
<span class="kwrd" style="color: blue;">if</span> (hundredthDigit != 0)
{
result += ToEnglishString(hundredthDigit) + <span class="str" style="color: #a31515;">" "</span> + HUNDRED;
<span class="kwrd" style="color: blue;">if</span> (remaining == 0)
{
<span class="kwrd" style="color: blue;">return</span> result;
}
<span class="kwrd" style="color: blue;">else</span>
{
result = result + <span class="str" style="color: #a31515;">" and "</span>;
}
}
<span class="kwrd" style="color: blue;">int</span> tenthDigit = remaining / 10;
remaining = remaining - tenthDigit * 10;
<span class="kwrd" style="color: blue;">switch</span> (tenthDigit)
{
<span class="kwrd" style="color: blue;">case</span> 1:
<span class="kwrd" style="color: blue;">switch</span> (remaining)
{
<span class="kwrd" style="color: blue;">case</span> 0: result = result + TEN; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 1: result = result + ELEVEN; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 2: result = result + TWELVE; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 3: result = result + THIRTEEN; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 4: result = result + FOURTEEN; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 5: result = result + FIFTEEN; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 6: result = result + SIXTEEN; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 7: result = result + SEVENTEEN; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 8: result = result + EIGHTEEN; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 9: result = result + NINETEEN; <span class="kwrd" style="color: blue;">break</span>;
};
remaining = 0;
<span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 2: result = result + TWENTY; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 3: result = result + THIRTY; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 4: result = result + FORTY; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 5: result = result + FIFTY; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 6: result = result + SIXTY; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 7: result = result + SEVENTY; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 8: result = result + EIGHTY; <span class="kwrd" style="color: blue;">break</span>;
<span class="kwrd" style="color: blue;">case</span> 9: result = result + NINETY; <span class="kwrd" style="color: blue;">break</span>;
}
<span class="kwrd" style="color: blue;">if</span> (tenthDigit != 0)
{
result = result + <span class="str" style="color: #a31515;">" "</span>;
}
<span class="kwrd" style="color: blue;">if</span> (remaining != 0)
{
result = result + ToEnglishString(remaining);
}
<span class="kwrd" style="color: blue;">return</span> result;
}
}
}
}</pre>
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"></pre>
<b><br /></b>
<b>Answer: </b>21224</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-38360429220522827782013-12-20T12:43:00.001-08:002014-09-05T23:32:42.819-07:00Problem 16: Power Digit Sum<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=16">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
Just compute it with BigInteger in C#. Here is the code:<br />
<br />
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">using</span> System.Numerics;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem016()
{
BigInteger p = BigInteger.Pow(<span class="kwrd" style="color: blue;">new</span> BigInteger(2), 1000);
Console.WriteLine(p.ToString().Select(x => x - <span class="str" style="color: #a31515;">'0'</span>).Aggregate((x, y) => (x + y)));
}
}
}</pre>
<br />
<b>Answer: </b>1366</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-33616849582805719932013-08-28T17:06:00.000-07:002014-09-05T23:16:13.143-07:00Problem 15: Lattice paths<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=15">here</a>.<br />
<div>
<br /></div>
<b>Solution:</b><br />
<br />
The key observation here is that the number of way to reach a particular point is the number of ways to reach the point above it plus the number of way to reach the point on the left of it. <br />
<br />
If you rotate the diagram by 45 degree clockwise, the recursion will look familar, it is simply the <a href="http://en.wikipedia.org/wiki/Pascal's_triangle">pascal triangle</a>. On the wiki, this problem is sited as one of the picture!<br />
<br />
Computing a pascal triangle is trivial, here is the code!<br />
<br />
<!-- code formatted by http://manoli.net/csharpformat/ -->
<br />
<pre class="csharpcode"><pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Numerics;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem015()
{
Console.WriteLine(BinomialCoefficient(40, 20));
}
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> BigInteger BinomialCoefficient(<span class="kwrd" style="color: blue;">long</span> n, <span class="kwrd" style="color: blue;">long</span> c)
{
<span class="kwrd" style="color: blue;">return</span> BinomialCoefficient(n, c, BuildPascalTriangle(n));
}
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> BigInteger BinomialCoefficient(<span class="kwrd" style="color: blue;">long</span> n, <span class="kwrd" style="color: blue;">long</span> c, BigInteger[,] pascalTriangle)
{
<span class="kwrd" style="color: blue;">return</span> pascalTriangle[n - 1, c];
}
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> BigInteger[,] BuildPascalTriangle(<span class="kwrd" style="color: blue;">long</span> n)
{
BigInteger[,] content = <span class="kwrd" style="color: blue;">new</span> BigInteger[n, n + 1];
content[0, 0] = BigInteger.One;
content[0, 1] = BigInteger.One;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">long</span> i = 1; i < n; i++)
{
content[i, 0] = 1;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">long</span> j = 1; j < i + 2; j++)
{
content[i, j] = content[i - 1, j - 1] + content[i - 1, j];
}
content[i, i + 1] = 1;
}
<span class="kwrd" style="color: blue;">return</span> content;
}
}
}</pre>
</pre>
<br />
<b>Answer: </b>137846528820<br />
<br />
An amazing large number of possibilities.</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-20211608470280183112013-08-28T16:53:00.002-07:002014-09-05T23:33:00.125-07:00Problem 14: Longest Collatz sequence<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=14">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
Given the sequence is so random, I am not hoping to be able to count it without going through it. Going through all sequences, however, is going to take long time. Therefore, we need to find a trick to improve it.<br />
<br />
The key idea is after going through 1 chain, we will know the length of all elements in the chain. In the example, we know 13 has a length of 10, but we also know 40 has a length of 9, and so on.<br />
<br />
Suppose we have another sequence that have k → 40 → ... , we know k is going to have a length 10. Optimization like that save a lot of time because repeated checking of the same sequences is eliminated, and in practice the problem involve many repeated sequences.<br />
<br />
This trick is generally called memoization (NOTE: Don't be confused this work with memorization, they spell differently). The code is pretty simple.<br />
<div>
<div style="font-weight: bold;">
<br /></div>
<div style="font-weight: bold;">
<pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small; font-weight: normal;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem014()
{
<span class="kwrd" style="color: blue;">var</span> lengths = <span class="kwrd" style="color: blue;">new</span> Dictionary<<span class="kwrd" style="color: blue;">long</span>, <span class="kwrd" style="color: blue;">long</span>>();
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">long</span> i = 1; i <= 1000000; i++)
{
Length(i, lengths);
}
<span class="kwrd" style="color: blue;">var</span> lengthSorted = lengths.ToList();
lengthSorted.Sort((x, y) => (x.Value < y.Value) ? 1 : ((x.Value == y.Value) ? 0 : -1));
Console.WriteLine(lengthSorted[0].Key);
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">long</span> Length(<span class="kwrd" style="color: blue;">long</span> x, Dictionary<<span class="kwrd" style="color: blue;">long</span>, <span class="kwrd" style="color: blue;">long</span>> lengths)
{
<span class="kwrd" style="color: blue;">if</span> (x == 1)
{
<span class="kwrd" style="color: blue;">return</span> 1;
}
<span class="kwrd" style="color: blue;">else</span>
{
<span class="kwrd" style="color: blue;">long</span> result;
<span class="kwrd" style="color: blue;">if</span> (lengths.TryGetValue(x, <span class="kwrd" style="color: blue;">out</span> result))
{
<span class="kwrd" style="color: blue;">return</span> result;
}
<span class="kwrd" style="color: blue;">else</span>
{
<span class="kwrd" style="color: blue;">long</span> next = x % 2 == 0 ? x / 2 : (3 * x + 1);
result = 1 + Length(next, lengths);
lengths.Add(x, result);
<span class="kwrd" style="color: blue;">return</span> result;
}
}
}
}
}</pre>
</div>
<div style="font-weight: bold;">
<br /></div>
<div>
<b>Answer: </b>837799</div>
</div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-4285577506741895282013-08-28T16:33:00.000-07:002014-09-05T23:15:14.468-07:00Problem 13: Large sum<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=13">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
Welcome to the world of BigInteger. With BigIntegers, you can do arbitrary precision arithmetic at ease. Here is the code, real no brainer, just computing sum.<br />
<br />
<pre class="csharpcode"><pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><pre class="csharpcode" style="font-family: Consolas, 'Courier New', Courier, monospace;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">using</span> System.Numerics;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem013()
{
<span class="kwrd" style="color: blue;">var</span> text = ReadResourceAsString(<span class="str" style="color: #a31515;">"Euler.Problem013.txt"</span>).Split(<span class="kwrd" style="color: blue;">new</span> <span class="kwrd" style="color: blue;">char</span>[] { <span class="str" style="color: #a31515;">'\r'</span>, <span class="str" style="color: #a31515;">'\n'</span> }, StringSplitOptions.RemoveEmptyEntries);
<span class="kwrd" style="color: blue;">var</span> data = text.Select(t => BigInteger.Parse(t));
Console.WriteLine(data.Aggregate((a, b) => BigInteger.Add(a, b)).ToString().Substring(0, 10));
}
}
}</pre>
</pre>
</pre>
<br />
<b>Answer: </b>5537376230</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-76647708564909257782013-08-28T13:28:00.001-07:002014-09-05T23:13:40.711-07:00Problem 12: Highly divisible triangular number<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=12">here</a>.<br />
<br />
<strong>Solution</strong><br />
<br />
It is easy to generate triangle number, what is not easy is to count the number of divisors. Here we should say something about the <a href="http://en.wikipedia.org/wiki/Divisor_function">divisor function</a>. Simply put, the divisor function, denoted by $ \sigma(n) $ of a positive integer $ n $ counts the number of positive factors (including 1 and n) a number has. For example, we have $ \sigma(3) = 2 $ because 1 and 3 are the only factors for 3.<br />
<br />
A key property of the divisor function is that it is <a href="http://en.wikipedia.org/wiki/Multiplicative_function">multiplicative</a>. That is to say, if GCD(p, q) = 1, then $ \sigma(p \times q) = \sigma(p) \times \sigma(q) $. This can be proved by creating a bijection between a factor of $ p \times q $ and the pair of factors of $ p $ and $ q $.<br />
<br />
The divisor function value of a prime power is particularly easy. Suppose $ p $ is prime, then $ \sigma(p^n) = n + 1$ because the only factors are 1, $ p $, $ p^2 $, ..., $ p^n $.<br />
<br />
Now we know how to compute the divisor function by completely factorize the number into prime powers, and leverage the multiplicative property.<br />
<br />
Last but not least, it is easy to see the n<sup>th</sup> triangular number is simply $ \frac{n(n+1)}{2} $. We will simply compute a factorization of it by brute force. The following is the code.<br />
<br />
<!-- code formatted by http://manoli.net/csharpformat/ -->
<br />
<pre class="csharpcode"><pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem012()
{
<span class="kwrd" style="color: blue;">long</span> n = 1;
while (<span class="kwrd" style="color: blue;">true</span>)
{
<span class="kwrd" style="color: blue;">long</span> t = n * (n + 1) / 2;
<span class="kwrd" style="color: blue;">int</span> numberOfDivisors = BruteForceFactor(t).Select(p => p.Item2 + 1).Aggregate((x, y) => x * y);
<span class="kwrd" style="color: blue;">if</span> (numberOfDivisors > 500)
{
Console.WriteLine(t);
<span class="kwrd" style="color: blue;">break</span>;
}
n++;
}
}
<span class="rem" style="color: green;">// Brute-force factoring </span>
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> IEnumerable<Tuple<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>>> BruteForceFactor(<span class="kwrd" style="color: blue;">long</span> n)
{
<span class="kwrd" style="color: blue;">if</span> (n == 1)
{
yield <span class="kwrd" style="color: blue;">return</span> Tuple.Create(1, 1);
}
<span class="kwrd" style="color: blue;">else</span>
{
<span class="kwrd" style="color: blue;">int</span> i = 2;
while (n > 1)
{
<span class="kwrd" style="color: blue;">if</span> (n % i == 0)
{
<span class="kwrd" style="color: blue;">int</span> index = 0;
while (n % i == 0)
{
index++;
n /= i;
}
yield <span class="kwrd" style="color: blue;">return</span> Tuple.Create(i, index);
}
i++;
}
}
}
}
}</pre>
</pre>
<br />
<strong>Answer</strong>: 76576500</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-62360892910181978532013-08-28T13:24:00.001-07:002014-09-05T23:13:17.877-07:00Problem 11: Largest product in a grid<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=11">here</a>.<br />
<br />
<b>Solution:</b><br />
<br />
To find the maximum, we need to go through all of them, a simple set of for loop will do:<br />
<br />
<pre class="csharpcode"><pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><pre class="csharpcode" style="font-family: Consolas, 'Courier New', Courier, monospace;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem011()
{
<span class="kwrd" style="color: blue;">string</span> input = ReadResourceAsString(<span class="str" style="color: #a31515;">"Euler.Problem011.txt"</span>);
<span class="kwrd" style="color: blue;">int</span>[] inputFlatten = input.Split(<span class="kwrd" style="color: blue;">new</span> <span class="kwrd" style="color: blue;">char</span>[] { <span class="str" style="color: #a31515;">' '</span>, <span class="str" style="color: #a31515;">'\r'</span>, <span class="str" style="color: #a31515;">'n'</span> }, StringSplitOptions.RemoveEmptyEntries).Select(s => Int32.Parse(s)).ToArray();
<span class="kwrd" style="color: blue;">int</span>[,] inputArray = <span class="kwrd" style="color: blue;">new</span> <span class="kwrd" style="color: blue;">int</span>[20, 20];
<span class="kwrd" style="color: blue;">int</span> p = 0;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 0; i < 20; i++)
{
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> j = 0; j < 20; j++)
{
inputArray[i, j] = inputFlatten[p++];
}
}
<span class="kwrd" style="color: blue;">int</span> max = -1;
<span class="rem" style="color: green;">// Try all horizontal lines</span>
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 0; i < 17; i++)
{
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> j = 0; j < 20; j++)
{
<span class="kwrd" style="color: blue;">int</span> prod = 1;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> k = i; k < i + 4; k++)
{
prod *= inputArray[k, j];
}
<span class="kwrd" style="color: blue;">if</span> (prod > max)
{
max = prod;
}
}
}
<span class="rem" style="color: green;">// Vertical lines</span>
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 0; i < 20; i++)
{
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> j = 0; j < 17; j++)
{
<span class="kwrd" style="color: blue;">int</span> prod = 1;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> k = j; k < j + 4; k++)
{
prod *= inputArray[i, k];
}
<span class="kwrd" style="color: blue;">if</span> (prod > max)
{
max = prod;
}
}
}
<span class="rem" style="color: green;">// Slash </span>
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 0; i < 17; i++)
{
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> j = 0; j < 17; j++)
{
<span class="kwrd" style="color: blue;">int</span> prod = 1;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> k = 0; k < 4; k++)
{
prod *= inputArray[i + k, j + k];
}
<span class="kwrd" style="color: blue;">if</span> (prod > max)
{
max = prod;
}
}
}
<span class="rem" style="color: green;">// Backslash</span>
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 3; i < 20; i++)
{
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> j = 0; j < 17; j++)
{
<span class="kwrd" style="color: blue;">int</span> prod = 1;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> k = 0; k < 4; k++)
{
prod *= inputArray[i - k, j + k];
}
<span class="kwrd" style="color: blue;">if</span> (prod > max)
{
max = prod;
}
}
}
Console.WriteLine(max);
}
}
}</pre>
</pre>
</pre>
<br />
<b>Answer: </b>70600674</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-24520850123695718082013-08-27T15:19:00.000-07:002014-09-05T23:12:50.103-07:00Problem 10: Summation of primes<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=10">here</a>.<br />
<br />
<strong>Solution:</strong><br />
<br />
<span dir="auto">To find all primes under a certain limit, <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of Eratosthenes</a> is great. While the name of it sound foreign, this is probably one of the simplest algorithms for finding primes. The wiki have tons on information about the algorithm and I am not going to repeat it here.</span><br />
<span dir="auto"></span><br />
<span dir="auto"><span dir="auto"><a href="http://en.wikipedia.org/wiki/The_Devil_is_in_the_details">The Devil is in the details</a>! To scale this algorithm up, using the standard collection is going to limit the scalability quite significantly. Notice all you need is a single bit to represent whether a number is crossed out or not, one should use a <a href="http://en.wikipedia.org/wiki/Bit_array">Bitmap</a>. Fortunately, we have <a href="http://msdn.microsoft.com/en-us/library/system.collections.bitarray.aspx">BitArray</a> in the .NET framework we can just use, and avoiding the even numbers altogether can give us a big memory saving. Here is the code for my sieve:</span></span><br />
<span dir="auto"><span dir="auto"><br /></span></span>
<!-- code formatted by http://manoli.net/csharpformat/ -->
<br />
<pre class="csharpcode"><pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Collections;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">using</span> System.Threading.Tasks;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem010()
{
Console.WriteLine(Primes(2000000).Select(t => (<span class="kwrd" style="color: blue;">long</span>)t).Sum());
}
<span class="kwrd" style="color: blue;">private</span> <span class="kwrd" style="color: blue;">static</span> IEnumerable<<span class="kwrd" style="color: blue;">int</span>> Primes(<span class="kwrd" style="color: blue;">int</span> max)
{
<span class="kwrd" style="color: blue;">if</span> (max >= 2)
{
yield <span class="kwrd" style="color: blue;">return</span> 2;
}
<span class="rem" style="color: green;">// sieve[i] represents 2i + 3; [So sieve[0] = 3, sieve[1] = 5] ...</span>
BitArray sieve = <span class="kwrd" style="color: blue;">new</span> BitArray(max / 2);
<span class="kwrd" style="color: blue;">int</span> i = 0;
while (<span class="kwrd" style="color: blue;">true</span>)
{
<span class="kwrd" style="color: blue;">int</span> num = (2 * i) + 3;
<span class="kwrd" style="color: blue;">int</span> current_i = i;
<span class="kwrd" style="color: blue;">var</span> indexes = Enumerable.Range(1, (sieve.Length - 1 - current_i) / num).Select(t => (t * num) + current_i).ToList();
Parallel.ForEach<<span class="kwrd" style="color: blue;">int</span>>(indexes, <span class="kwrd" style="color: blue;">delegate</span>(<span class="kwrd" style="color: blue;">int</span> index) { sieve[index] = <span class="kwrd" style="color: blue;">true</span>; });
sieve[i] = <span class="kwrd" style="color: blue;">false</span>;
i++;
while (i < sieve.Length && sieve[i])
{
i++;
}
<span class="kwrd" style="color: blue;">if</span> (i >= sieve.Length)
{
<span class="kwrd" style="color: blue;">break</span>;
}
}
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> j = 0; j < sieve.Length; j++)
{
<span class="kwrd" style="color: blue;">if</span> (!sieve[j])
{
<span class="kwrd" style="color: blue;">int</span> num = (2 * j) + 3;
<span class="kwrd" style="color: blue;">if</span> (num <= max)
{
yield <span class="kwrd" style="color: blue;">return</span> num;
}
}
}
}
}
}</pre>
</pre>
<br />
Note the use of Parallel.ForEach - that speed the crossing up significantly. A careful reader might notice this code is not cache friendly. Yes, it is not, and a cache friendly version can be found online <a href="http://code.google.com/p/primesieve/">here</a>. The code is not really meant for blazing fast, but just good enough to get the problem solved.<br />
<br />
<b>Answer: </b>142913828922</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-35116863584847025062013-08-27T13:57:00.001-07:002014-09-05T23:11:52.678-07:00Problem 9: Special Pythagorean triplet<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=9">here</a>.<br />
<br />
<strong>Solution:</strong><br />
<br />
Along our usual line-of-thought, we would think about brute force again. But this time brute force is not so easy anymore since we need to find out a good pair that work. We can still try all possible pairs, but that will spend a lot of time on the unnecessary search. Turn out, iterating through the list of all Pythagorean triplet is not hard at all, as we can see shortly.<br />
<br />
First, let's define primitive Pythagorean triplet be the Pythagorean triplet which is relatively prime. (i.e. GCD(a, b, c) = 1). Suppose we have a non-primitive Pythagorean triplet, we can divide every number by their GCD to obtain one. In some sense, primitive Pythagorean triplet spans the Pythagorean triplets.<br />
<br />
The set of primitive Pythagorean triplet can be enumerated through the tree of primitive Pythagorean triplet found in <a href="http://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples">wiki</a>. What is not mentioned in the wiki is that the sum of the Pythagorean triplet must be increasing when we descend down the tree as we will show here:<br />
<br />
The sum of the three numbers can be obtained by pre-multiplying the row vector (1, 1, 1). Thus the child node's sum can be obtained as:<br />
(1,1,1)(d, e, f)' = (1,1,1)A(a,b,c) = 5a-5b+7c<br />
<br />
Now we know a^2 + b^2 = c^2. Therefore c = sqrt(a^2 + b^2) > b. 5a - 5b + 7c > 5a - 5b + 6b + c = 5a + b + c> a + b + c.<br />
<br />
So we know the child sum is greater than the parent sum.<br />
<br />
We can prove the other two matrices similarly. With that, we can be sure that we have found all primitive Pythagorean triples by doing a simple Breadth First Search on the tree and stop descending when sum exceed 1,000. With that we can check whether a particular triple works or not. The code will look like this.<br />
<br />
<!-- code formatted by http://manoli.net/csharpformat/ -->
<br />
<pre class="csharpcode"><pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem009()
{
<span class="kwrd" style="color: blue;">foreach</span> (<span class="kwrd" style="color: blue;">var</span> triple <span class="kwrd" style="color: blue;">in</span> GetPrimitivePythTriples(1000))
{
<span class="kwrd" style="color: blue;">int</span> tripleSum = triple.Item1 + triple.Item2 + triple.Item3;
<span class="kwrd" style="color: blue;">if</span> (1000 % tripleSum == 0)
{
<span class="kwrd" style="color: blue;">int</span> scale = 1000 / tripleSum;
Console.WriteLine(scale * scale * scale * triple.Item1 * triple.Item2 * triple.Item3);
<span class="kwrd" style="color: blue;">return</span>;
}
}
}
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> IEnumerable<Tuple<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>>> GetPrimitivePythTriples(<span class="kwrd" style="color: blue;">int</span> sumMax)
{
<span class="kwrd" style="color: blue;">var</span> root = <span class="kwrd" style="color: blue;">new</span> Tuple<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>>(3, 4, 5);
Queue<Tuple<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>>> bfsQueue = <span class="kwrd" style="color: blue;">new</span> Queue<Tuple<<span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>, <span class="kwrd" style="color: blue;">int</span>>>();
bfsQueue.Enqueue(root);
while (bfsQueue.Count > 0)
{
<span class="kwrd" style="color: blue;">var</span> visiting = bfsQueue.Dequeue();
<span class="kwrd" style="color: blue;">int</span> a = visiting.Item1;
<span class="kwrd" style="color: blue;">int</span> b = visiting.Item2;
<span class="kwrd" style="color: blue;">int</span> c = visiting.Item3;
<span class="kwrd" style="color: blue;">if</span> (a + b + c <= sumMax)
{
yield <span class="kwrd" style="color: blue;">return</span> visiting;
bfsQueue.Enqueue(Tuple.Create(
1 * a - 2 * b + 2 * c,
2 * a - 1 * b + 2 * c,
2 * a - 2 * b + 3 * c));
bfsQueue.Enqueue(Tuple.Create(
1 * a + 2 * b + 2 * c,
2 * a + 1 * b + 2 * c,
2 * a + 2 * b + 3 * c));
bfsQueue.Enqueue(Tuple.Create(
-1 * a + 2 * b + 2 * c,
-2 * a + 1 * b + 2 * c,
-2 * a + 2 * b + 3 * c));
}
}
}
}
}</pre>
</pre>
<br />
Note the use of yield return. This is a very powerful construct in C# that allow a method the sequence generating function a to become an iterator object with all the state keeping work done by the compiler. The best explanation of the yield feature (not necessarily the most precise, but the most understandable one) is found <a href="http://www.dotnetperls.com/yield">here</a>. <br />
<br />
Great feature comes with great responsibility when using it, you can trip yourselves up if you are not careful - typical mistake is iterating the sequence twice, you will do all the computation twice. Caching them in a list or array if you need to iterate more than once.<br />
<br />
<b>Answer: </b>31875000</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-1801468612755309280.post-42424124974554731552013-08-27T09:42:00.000-07:002014-09-05T23:11:31.473-07:00Problem 8: Largest product in a series<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Please find the problem <a href="http://projecteuler.net/problem=8">here</a>.<br />
<br />
<strong>Solution:</strong><br />
<strong></strong><br />
There are just 1000 - 5 + 1 = 996 cases to consider. The maximum possible value is $ 9 \times 9 \times 9 \times 9 \times 9 = 59049 $ so using a 32 bit integer is good enough.<br />
<br />
Here is the code:<br />
<br />
<!-- code formatted by http://manoli.net/csharpformat/ -->
<br />
<pre class="csharpcode"><pre class="csharpcode" style="background-color: white; font-family: Consolas, 'Courier New', Courier, monospace; font-size: small;"><span class="kwrd" style="color: blue;">namespace</span> Euler
{
<span class="kwrd" style="color: blue;">using</span> System;
<span class="kwrd" style="color: blue;">using</span> System.Collections.Generic;
<span class="kwrd" style="color: blue;">using</span> System.Linq;
<span class="kwrd" style="color: blue;">internal</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">partial</span> <span class="kwrd" style="color: blue;">class</span> Program
{
<span class="kwrd" style="color: blue;">public</span> <span class="kwrd" style="color: blue;">static</span> <span class="kwrd" style="color: blue;">void</span> Problem008()
{
<span class="kwrd" style="color: blue;">string</span> n = ReadResourceAsString(<span class="str" style="color: #a31515;">"Euler.Problem008.txt"</span>);
n = n.Replace(<span class="str" style="color: #a31515;">"\n"</span>, <span class="kwrd" style="color: blue;">string</span>.Empty);
n = n.Replace(<span class="str" style="color: #a31515;">"\r"</span>, <span class="kwrd" style="color: blue;">string</span>.Empty);
<span class="kwrd" style="color: blue;">int</span>[] d = n.ToCharArray().Select(c => c - <span class="str" style="color: #a31515;">'0'</span>).ToArray();
<span class="kwrd" style="color: blue;">int</span> max = -1;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> i = 0; i < 1000 - 5; i++)
{
<span class="kwrd" style="color: blue;">int</span> p = 1;
<span class="kwrd" style="color: blue;">for</span> (<span class="kwrd" style="color: blue;">int</span> j = i; j < i + 5; j++)
{
p *= d[j];
}
<span class="kwrd" style="color: blue;">if</span> (p > max)
{
max = p;
}
}
Console.WriteLine(max);
}
}
}</pre>
</pre>
<br />
This problem is truly trivial, because it runs so quickly it doesn't worth to optimize it in any sense (one can imagine the next product can be obtained easily by division, or any product involve zero can quickly skip, ...)<br />
<br />
<b>Answer: </b>40824.</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0