Bill Blogs in C# -- Euler

Tags:
C#
C# General
Euler
Linq
Technology

Created: 2/4/2010 8:48:00 PM

This is going to be fun. It’s a bit of LINQ, a bit of academic Computer Science, and a bit of meteorology.

Euler Problem 14 concerns a sequence referred to as hailstorm numbers.

Hailstorm number sequences are generated by applying one of two functions to a number in order to generate the next number. In this case, the sequence is:

n –> n / 2 (n is even)

n –> 3n + 1 (n is odd)

When n is even, the next number in the sequence is smaller. When n is odd, the next number in the sequence is larger

In all cases, it is believed that for every starting number, the sequence will oscillate for some time, and then eventually converge to some minimum number. (In this case, that minimum number is 1.)

These sequences are called hailstorm numbers because they (very simplistically) act like hail in a storm: oscillating up and down in a thunderhead before eventually falling to earth.

This particular problem asks you to find the sequence that has the longest chain, given input numbers less than 1 million.

The brute force method will take your computer a very long time to compute. The problem asks for the longest sequence, and you’ve got a million of them to compute.

Stack size is a related problem. You could write a method that computes the next value, and then finds the sequence size recursively:

1: private static long Generate(long n)

` 2: {`

3: if (n == 1) { return 1; }

` 4: var next = (n % 2 == 0) ? n / 2 : 3 * n + 1;`

5: return Generate(next) + 1;

` 6: }`

A LINQ query gives you the answer:

1: var answer = (from StartingValue in Enumerable.Range(1, 999999)

` 2: let SequenceSize = Generate(StartingValue)`

` 3: orderby SequenceSize descending`

4: select new { StartingValue, SequenceSize }).First();

This works, and does give the correct answer.

But I’m not really satisfied, because it takes more than 15 seconds (on my PDC laptop) to finish.

There are two steps to making this faster. The final version uses a technique called Memoization. Memoization enables you to avoid computing the same result more than once. Pure functions have a useful property in that the output depends on their inputs, and nothing else. Therefore, once you’ve computed the sequence length for, say 64, you should never need to compute it again. It’s always going to be the same.

Moemoization means to store the result for a computation and returned the stored result rather than do the work again. This can provide significant savings in a recursive algorithm like this. For example, memoization of the result for 64 (7) means saving the computations for 64, 32,16,8,4,2 and 1. Memoization of the results for longer sequences would mean correspondingly larger savings.

You could modify the Generate method to provide storage for previously computed results. Here’s how you would do that:

1: private static Dictionary<long, long> StoredResults = new Dictionary<long, long>();

` 2: `

3: private static long Generate(long n)

` 4: {`

5: if (StoredResults.ContainsKey(n))

6: return StoredResults[n];

7: if (n == 1)

` 8: { `

` 9: StoredResults[n] = 1;`

10: return 1;

` 11: }`

` 12: var next = (n % 2 == 0) ? n / 2 : 3 * n + 1;`

` 13: var answer = Generate(next) + 1;`

` 14: StoredResults[n] = answer;`

15: return answer;

` 16: }`

But, what’s the fun in that? There’s no reuse. It’s a one off solution.

I want to write a generic Memoize function that lets me memoize any function with one variable. Wes Dyer’s post explains this technique in detail. Memoize is a generic method that executes a function, abstracting away the types for both the parameter type and the result type:

1: public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> function)

` 2: {`

3: var previousResults = new Dictionary<T, TResult>();

` 4: `

5: // Important: This is a lamdba, not the result.

6: return (T arg) =>

` 7: {`

8: if (previousResults.ContainsKey(arg))

9: return previousResults[arg];

10: else

` 11: {`

` 12: TResult result = function(arg);`

` 13: previousResults.Add(arg, result);`

14: return result;

` 15: }`

` 16: };`

` 17: }`

The first question you may have is how the previous results actually works. It’s a local variable, not a static storage. How can it possible live beyond the scope of the method?

Welll, that’s the magic of a closure. Memoize doesn’t return a value, it returns some func that enables you to find the value later. That func contains the dictionary. I go into this technique in Items 33 and 40 in More Effective C#.

In order to use this, you need to move Generate() from a regular method to a lamdba expression (even if it is a multi-line lambda):

1: Func<long, long> GenerateSequenceSize = null;

2: GenerateSequenceSize = (long n) =>

` 3: {`

4: if (n == 1) { return 1; }

` 5: var next = (n % 2 == 0) ? n / 2 : 3 * n + 1;`

6: return GenerateSequenceSize(next) + 1;

` 7: };`

` 8: `

` 9: GenerateSequenceSize = GenerateSequenceSize.Memoize();`

Now, we have the generate function in a form we can memoize. The only trick here is that you have to set GenerateSequenceSize to null before you assign it in line 2. Otherwise, the compiler complains about using an unassigned value in line 6.

You can extend the Memoize function to methods with more than one input, but for now, I’ll leave that as an exercise for the reader.

Tags:
C#
C# General
Euler
Linq
Technology

Created: 8/26/2009 3:15:30 AM

Well, it’s been a long time since I’ve taken the time to solve and blog about one of the Euler problems. It was time to pick this up again.

Problem 13 says:

Work out the first 10 digits of the sum of the following one-hundred 50-digit numbers. <long list of numbers elided>

The key here is that you only need the first 10 digits of the answer. Therefore, you only need to add the first 11 digits for each of the 100 numbers. Here’s why: These numbers do not contain any 0’s in the first position. Therefore, the sum of all the first digits is at least 100. The first digit contributes at least 3 digits in the final answer. Once you get to the 11th digit, that number can’t be great than 900. (100 9’s). It won’t affect anything in the first 10 digits. That’s the end of the work.

That makes the final answer one LINQ query:

1: static void Main(string[] args)

` 2: {`

3: var finalAnswer = (from index in Enumerable.Range(0, 11)

4: from s in listOfDigits

5: select int.Parse(s[index].ToString()) *

6: (long)Math.Pow(10, 11 - index)).

` 7: Sum();`

` 8: Console.WriteLine(finalAnswer);`

` 9: }`

listOfDigits (elided) is a list of strings where each string contains the digits for one number.

The first line of the query creates an enumeration for the first 11 digits.

The next two lines select a single character from each string, parsing that character to create an integer.

Next, do a little math to move that single digit into the correct column for the sum.

Finally, sum all the integers.

Sweet, huh?

Tags:
C#
C# General
Euler
Technology

Created: 3/23/2009 5:18:00 PM

It’s been a long time since I have worked on any of the Euler problems. I simply haven’t had time. Well, it was time to spend a bit of time just exercising the math part of my mind, and solve another problem.

Problem 12 asks you to find the first triangle number that has more than 500 divisors.

Like my other C# solutions, it makes sense to decompose this problem into smaller sets. First, figure out how to generate the triangle numbers. Then, figure out the simplest way to determine how many divisors a number has.

Let’s start with the triangle numbers. The nth triangle number is the sum of all natural numbers less than or equal to N. You can think of them like the number of balls in a billiard rack with N rows: 1, (1+2), (1+2+3), (1+2+3+4), or, 1,3,6,10,15…

A little bit of math (or a quick search) will tell you that the Nth triangle number is [N * (N+1)]/2.

Now, all we need to do is compute the total number of divisors for each of these numbers. One simple answer is to take all number less than or equal to the triangle number. Any of those that divide into the triangle number is a divisor. But, that’s incredibly inefficient. Instead, you can stop at Sqrt(Number). That will give you exactly 1/2 the number of divisors. For example, if 128 is divisible by 2, you’ve found two divisors: 2, and 64. Therefore, this method tells me quickly how many divisors a number has:

1: static int CountDivisors(int n)

` 2: {`

3: var divisors = from val in Enumerable.Range(1, (int)Math.Sqrt(n))

4: where n % val == 0

` 5: select val;`

` 6: `

7: return divisors.Count()*2;

` 8: }`

This query (written in two parts) finds the answer. Remember that one of the keys to LINQ is deferred execution. Only the triangle numbers up to and including the answer are generated. The entire program runs in a few seconds:

1: var triangleNumbers = from n in Enumerable.Range(1, 100000)

` 2: let Value = (n * (n + 1)) / 2`

3: select new

` 4: {`

` 5: Number = Value,`

` 6: NumDivisors = CountDivisors(Value)`

` 7: };`

8: var answer = (from vals in triangleNumbers

9: where vals.NumDivisors > 500

` 10: select vals).First();`

It feels good to stretch the math muscles again.

Tags:
.NET General
C#
C# General
Euler
Linq
Technology

Created: 8/31/2008 5:05:00 PM

Patrick posted his solution earlier this week. I figure it was time to add mine.

Also, Octavio Hernandez pointed out in the comments to problem 8 that he had discussed similar code constructs in his blog a while back.

Problem 10 asks for the sum of all primes less than 2 million. It's also one line of LINQ code:

` 1: var number = Common.Primes.GeneraePrimes().TakeWhile((n) => n < 2000000).Sum();`

` 2: Console.WriteLine(number);`

As Patrick pointed out, this will cause an overflow unless you make some changes to the GeneratePrimes() method so that it returns a sequence of longs instead of a sequence of ints.

I also wasn't thrilled with the fact that it was taking a few minutes to finish instead of seconds. That needed some fixing.

George Byrkit pointed out that the math can be optimized by recognizing that the highest factor you need to check for any N is Sqrt(N).

Sadly, the current .NET Framework does not contain methods that do the check efficiently. George suggested using List<T>FindAll() to find only those numbers smaller than the target. That method is a member of List and creates a new List object. Yuck. Also, it doesn't perform lazy evaluation, and it checks the entire list.

But now that the numbers have gotten much larger, it's worth the work to create my own version of those methods that speed this up.

Here's the new version of IsPrime:

1: public static IEnumerable<long> GeneratePrimes()

` 2: {`

3: var range = Enumerable.Range(2, int.MaxValue-1);

4: var answers = from number in range

5: where number.IsPrime()

6: select (long)number;

` 7: `

8: return answers;

` 9: }`

The only change here is to cast the prime number to a long before returning.

IsPrime gets a slightly larger makeover:

1: private static bool IsPrime(thisint number)

` 2: {`

3: bool isPrime = knownPrimes.TakeWhile(n => n*n <= number).

` 4: TrueForAll(n => number % n != 0); `

5: if (isPrime)

` 6: knownPrimes.Add(number);`

7: return isPrime;

` 8: }`

The astute reader will immediately notice that I'm calling TrueForAll using an IEnumerable<int> instead of a List<int>. That's not supposed to compile. And in fact, it doesn't, until I write my own version of TrueForAll:

1: public static bool TrueForAll<T>(this IEnumerable<T> sequence, Predicate<T> test)

` 2: {`

3: foreach (T item in sequence)

4: if (!test(item))

5: return false;

6: return true;

` 7: }`

Note that this is typed for IEnumerable<T>, so the compiler will use this version on sequences that are not List<T>, but will still use the base framework version for all List<T> types.

And, now it produces the correct answers in under a minute.

Tags:
C#
C# General
Euler
Linq
Technology

Created: 8/28/2008 6:03:19 PM

I was going to wait a bit to post this, but Patrick Steele posted his solution, so I figured I should post mine.

Patrick took the straight out brute force approach. I decided to think a bit differently and use the some LINQ code to generate my answer.

The problem is to find the only Pythagorean triplet {a,b,c} for which a + b + c = 1000.

The first step was to find a sequence of all triples {a,b,c} where a+b+c added to 1000. To save a little computing time, I made use of two important facts. First, in order to be a Pythagorean triplet, c must be greater than both a and b. Second, different orders of a and b don't matter: {3,4,5} would be the same as {4,3,5}. Therefore, I made the assumption that a must be less than or equal to b.

From those possible answers, I needed to find the only triplet that is a Pythagorean triplet. Here's the code:

1: static void Main(string[] args)

` 2: {`

3: var possible = from A in Enumerable.Range(1, 333)

4: from B in Enumerable.Range(A, (1000 - A) / 2 - A)

` 5: let C = 1000 - A - B`

6: select new { A, B, C };

7: var answer = (from triple in possible

8: where triple.A * triple.A + triple.B * triple.B == triple.C * triple.C

` 9: select triple).Single();`

` 10: `

` 11: Console.WriteLine(answer);`

` 12: Console.WriteLine(answer.A * answer.B * answer.C);`

` 13: }`

There are two bits of LINQ goodness here that I haven't mentioned before.

First, there's the call to Single(). Single will throw an exception if the sequence does not contain exactly one answer. That helps me test: there must be exactly one.

Second, the C# compiler creates an override for ToString() in every anonymous type. That override writes the value of all the properties in the anonymous type. That's why I can simply use Console.Writeline(answer) to see the values of a,b,c.

It's just language goodness.

Tags:
C#
C# General
Euler
Technology

Created: 8/14/2008 1:30:35 PM

Yes, it's true that I've been very lax in working on these problems. It's been a combination of the day job, finishing all the editing tasks on "More Effective C#", and actually trying to keep the personal life intact.

The 7th problem is quite straightforward: find the 10,001st prime number. The main program is just two lines:

1: static void Main(string[] args)

` 2: {`

` 3: var numbers = Common.Primes.GeneratePrimes().Skip(10000).First();`

` 4: `

` 5: Console.WriteLine(numbers);`

` 6: }`

Simple LINQ stuff. The Skip() method skips the first N elements, and First() escapes the query and returns the first element.

Of course, the meat of the method is the GeneratePrimes() method:

1: private static List<int> knownPrimes = new List<int>();

` 2: `

3: private static bool IsPrime(thisint number)

` 4: {`

5: bool isPrime = knownPrimes.TrueForAll(n => number % n != 0);

6: if (isPrime)

` 7: knownPrimes.Add(number);`

8: return isPrime;

` 9: }`

` 10: `

11: public static IEnumerable<int> GeneratePrimes()

` 12: {`

13: var range = Enumerable.Range(2, int.MaxValue-1);

14: var answers = from number in range

15: where number.IsPrime()

` 16: select number;`

` 17: `

18: return answers;

` 19: }`

GeneratePrimes() returns the sequence of primes. It uses the IsPrime() method to determine if a number is prime. IsPrime() shows a couple of assumptions I've made to make this a reasonably simple method. First of all, it assumes that all primes up to the number being examine have been found. Therefore, if the number has no prime factors smaller than itself, it must be a prime number. That saves quite a bit of work, because the set of primes smaller than N is much smaller than the set of numbers less than N.

To make this work, note that when a prime is found, it is added to the list of known primes.

Tags:
C#
C# General
Euler
Linq
Technology

Created: 4/11/2008 7:24:00 PM

Euler Problem six asks you to find the difference between the sum of squares and the square of the sum for the natural numbers 1 through 100.

I took the easy route, and made a brute force implementation in C#. There are a couple new bits of LINQ syntax here. This query creates two different anonymous types. One for the number / square pair, the second is the aggregate answer for the sum and the sum of squares.

The important points are that this is done in a single iteration. It's pulling each value in from the initial sequence and doing all the calculations in one iteration of the sequence:

1 var aggregate = (from number inEnumerable.Range(1, 100)

2 selectnew { number, square = number * number }).

3 Aggregate(new { Sum = 0, SumOfSquares = 0 },

4 (sums, val) => new { Sum = sums.Sum+val.number,

5 SumOfSquares = sums.SumOfSquares + val.square});

6

7 int SquareOfSums = aggregate.Sum * aggregate.Sum;

8

9 Console.WriteLine("{0} - {1} = {2}", SquareOfSums, aggregate.SumOfSquares,

10 SquareOfSums - aggregate.SumOfSquares);

2 selectnew { number, square = number * number }).

3 Aggregate(new { Sum = 0, SumOfSquares = 0 },

4 (sums, val) => new { Sum = sums.Sum+val.number,

5 SumOfSquares = sums.SumOfSquares + val.square});

6

7 int SquareOfSums = aggregate.Sum * aggregate.Sum;

8

9 Console.WriteLine("{0} - {1} = {2}", SquareOfSums, aggregate.SumOfSquares,

10 SquareOfSums - aggregate.SumOfSquares);

There you go. Another simple bit of code.

Tags:
C#
C# General
Euler
Technology

Created: 4/8/2008 6:13:40 PM

Well, it's time to post another solution and look at how LINQ and C# 3.0 can create elegant code for these problems.

The fifth problem asks you to find the smallest number that is divisible by all the natural numbers from 1 through 20. You can trivially find the answer like this:

1 private static void BruteForce()

2 {

3 var divisible = ( from n in Enumerable .Range(1, int .MaxValue)

4 where (n % 2 == 0

5 && n % 3 == 0

6 && n % 4 == 0

7 && n % 5 == 0

8 && n % 6 == 0

9 && n % 7 == 0

10 && n % 8 == 0

11 && n % 9 == 0

12 && n % 10 == 0

13 && n % 11 == 0

14 && n % 12 == 0

15 && n % 13 == 0

16 && n % 14 == 0

17 && n % 15 == 0

18 && n % 16 == 0

19 && n % 17 == 0

20 && n % 18 == 0

21 && n % 19 == 0

22 && n % 20 == 0

23 )

24 select n).First();

25 Console .WriteLine(divisible);

26 }

But don't do that. It's very slow. Let's think a bit about the math, and the answer gets much easier. If you remember middle school math, you are being asked to find the greatest common divisor for all numbers 1-20. The unique factorization theorem is what you need here. It states that every number can be written in exactly one way as the product of prime numbers. The greatest common divisor can be found by multiplying the highest powers of each prime factor. In code, it's a little easier to turn the definition around and peel off prime factors from every number in the list. It's faster and simpler than finding all the prime factors.

You start with a list like this: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

1 really doesn't do much, so we'll start with 2. Keep the 2, and replace every number greater than 2 that is divisible by 2 with that number divided by 2:

1, 2, 3, 2, 5, 3, 7, 4, 9, 5

Move to the next number (3). Repeat:

1, 2, 3, 2, 5, 1, 7, 4, 3, 5

Move to the next number (another 2). Repeat:

1, 2, 3, 2, 5, 1, 7, 2, 3, 5

Continue until done:

1, 2, 3, 2, 5, 1, 7, 2, 1, 1

Multiply: 2520

That gives us this algorithm:

1 private static void Better()

2 {

3 var numbers = Enumerable .Range(1, 20).ToArray();

4 // remove common factors:

5 for ( int index = 0; index < numbers.Length; index++)

6 for ( int subIndex = index + 1; subIndex < numbers.Length; subIndex++)

7 if (numbers[subIndex] % numbers[index] == 0)

8 numbers[subIndex] /= numbers[index];

9

10 var answer = numbers.Aggregate(1, (product, number) => product * number);

11

12 Console .WriteLine(answer);

13 }

But you know what. I don't like those loops. I'd rather write methods that operate on a sequence. It's another rather simple example of tail recursion. For any sequence, peel off the first number. Then, return that number followed by the rest of the sequence divided by that first number, where possible. Pipe the remaining sequence back into the same function:

11 private static void Best()

12 {

13 var numbers = Enumerable .Range(1, 20);

14

15 var answer = numbers.LeastCommonFactor().Aggregate(1,

16 (product, number) => product * number);

17

18 Console .WriteLine(answer);

19 }

20

21 private static IEnumerable < int > LeastCommonFactor( this IEnumerable < int > list)

22 {

23 // Stop if the list is empty:

24 if (!list.Any())

25 yield break ;

26

27 int factor = list.First();

28 yield return factor;

29

30 var remaining = from item in list.Skip(1)

31 select (item % factor == 0) ? item / factor : item;

32 foreach ( int item in remaining.LeastCommonFactor())

33 yield return item;

34 }

Now that's a simple, elegant algorithm. And, it runs quite a bit faster than the brute force version. Stay tuned for more toward the end of the week.

Tags:
C# General
Euler
Linq
Technology

Created: 4/7/2008 2:37:39 AM

The fourth Euler problem asks you to find the largest palindrome number that is the product of two three digit numbers. For example, the number 919 is a palindrome: it's the same forward and backwards.

To solve this problem, we need to find the product of all combinations of three digit numbers. Well, if you remember your probability, this is a combinatorial problem. Order doesn't matter. That limits the number of combinations.

Next, we need to find palindromes. A little string conversion makes that simple. You can convert the number to a string, then see if the string is equal to its reverse. Strangely, there isn't a method in System.String that can reverse a string. But, there is a Reverse() extension method that's in scope.

Well, let's look at the code:

1 static void Main( string [] args)

2 {

3 var allProducts = from x in Enumerable .Range(100, 900)

4 from y in Enumerable .Range(100, 900)

5 where x <= y

6 let product = x * y

7 orderby product descending

8 select new { x, y, product };

9

10 var palindrome = ( from n in allProducts

11 let chars = n.product.ToString()

12 let reverse = new string (chars.Reverse().ToArray())

13 where chars == reverse

14 select n).First();

15 Console .WriteLine( "{0}, {1} => {2}" , palindrome.x, palindrome.y,

16 palindrome.product);

17

18 }

The first query is to generate all products of three digit numbers. Notice that the where clause removes permutations that are the same as two numbers. For example, 251*126 would have already been computed from 126*251. Next, notice the 'let' clause. That assigns a local variable in the query expression so that you don't have to compute the product more than once. While we're at it, we order the values by the products in descending order.

The next query finds the palindromes from all those products. As I said earlier, I do this by converting the product to a string, then comparing the string to its reverse. As with the earlier query, I use the let clause to cache some local results and avoid recomputing values.

You'll need to run the code yourself to see the answer.

Tags:
C# General
Euler
Technology

Created: 3/28/2008 7:28:00 PM

Here are my notes on the third Project Euler problem. The problem is "What is the largest prime factor of the number 600,851,475,143?"

Once again, this is a problem that is best solved creating some simple LINQ queries. From the outside, this query generates the list of all prime factors in the very large number:

long largeNumber = 600851475143;

var allPrimeFactors = from p in Primes.PrimeFactors(largeNumber)

orderby p descending

select p;

foreach (var f in allPrimeFactors)

Console.WriteLine(f);

As with the other first two problems, the query is fairly simple. Just grab the prime factors, and order them in descending order.

The work is in the Primes class. This class uses tail recursion to find all prime factors. It starts with the smallest prime number (2), and removes all copies of that number as a factor. Once all those are returned, it will look at the next larger factor and remove those.

A couple quick notes:

1. The algorithm, as written, must start with the smallest prime number. Otherwise, it will find non-prime factors.

2. It doesn't matter that MorePrimeFactors looks at possible factors that aren't prime. They won't appear because any smaller prime factors have already been removed. (for example, 6 won't appear because any factors of 2 or 3 have already been removed).

public static class Primes

{

// Find all prime factors.

public static IEnumerable<int> PrimeFactors(long number)

{

// Start by removing the lowest prime (2)

return MorePrimeFactors(number, 2);

}

// This recursive method finds all prime factors.

private static IEnumerable<int> MorePrimeFactors(long number, int factor)

{

// Find the next prime factor

while (number % factor != 0)

factor++;

// Return it.

yield return factor;

// look again...

if (number > factor)

// recursively look for this factor again, using Num/factor

// as the new big number

foreach (int factors in MorePrimeFactors(number / factor, factor))

yield return factors;

}

}

Note that the PrimeFactors algorithm is not linq based, but it does rely heavily on custom enumerators.

Tags:
C#
C# General
Euler
Technology

Created: 3/27/2008 2:20:00 PM

The second Euler problem asks you to find the sum of all even valued terms in the Fibonacci sequence which do not exceed 4,000,000.

Let's look at the solution from the outside in. Here's the query that finds the answer:

` ``var EvenFibNumbers = (from n in Enumerable.Range(1, MAX)`

let value = FibonacciSequence.Fibonacci(n)

where value % 2 == 0

select value).TakeWhile(n => n < MAX);

var answer = EvenFibNumbers.Sum();

There are a couple notes on the performance metrics used here:

The TakeWhile() method call does short circuit the query so that it does not continue calculating unneeded numbers. I could optimize this by trying to be very careful about which Fibonacci numbers I calculate, but it really doesn't matter. TakeWhile means I don't calculate them anyway. (Well, to be strictly accurate, I do calculate one more than I need, but that's no big.

Next, note the "let" statement in the query. I use that to avoid calculating the Nth Fibonacci number more than once. It just introduces a new local variable (value) and assigns it to the result of Fibonacci(n).

On this algorithm, there are some other interesting changes you could make. If you examine the Fibonacci sequence carefully, you'd see that every 3^{rd} Fibonacci number is even. You could, possibly, save some work by using that fact. Because of how the Fibonacci sequence is calculated, I don't think it matters. (Comment if you have a way to optimize it that I'm not seeing).

What's more interesting, to me, is how I wrote the Fibonacci sequence. I used a mix of Functional and Object Oriented techniques. (For a more functional approach, read Dustin Campbell's article on memorization: http://diditwith.net/PermaLink,guid,7191176b-c72a-49db-986e-466845665fa1.aspx)

` ``public static class FibonacciSequence`

{

// Store all Nth Fibonacci numbers that have been calculated.

private static Dictionary<int, long> FibnocciNumbers = new Dictionary<int, long>();

// Return the Nth Fibonacci number.

public static long Fibonacci(int n)

{

long answer;

// If it's already been calculated, just return it.

if (FibnocciNumbers.TryGetValue(n, out answer))

return answer;

// The first and 2nd numbers are 1.

if (n < 2)

answer = n;

else

// It's the sum of the previous two numbers.

answer = Fibonacci(n - 1) + Fibonacci(n - 2);

// Store...

FibnocciNumbers.Add(n, answer);

// return

return answer;

}

}

You'll note that this class uses a recursive method to calculate the Nth Fibonacci number. However, it will only calculate each number in the sequence at most once. Once a calculation has been performed, the answer is stored in a private dictionary for later use. Rather than try and twist your brain around many of the more advanced Functional programming concepts, using C# 3.0, you can mix good old fashioned oo programming with good old fashioned functional programming. Cool!

Stay tuned for more on Friday, when I write up the notes on problem 3.

Tags:
C#
Euler
Linq
Technology

Created: 3/26/2008 1:36:00 AM

I am starting a new series. A friend recently pointed me at the Project Euler problems. You can see the project here: http://projecteuler.net/

As I finish them, I'll post an explanation of the problem and the code here. I've also posted the code on MSDN Code Gallery. As I finish a week's worth of code, I'll post a new release of source code there.

A few ground rules:

- I'm not going for the 'best' or 'most efficient' solution. I'm using this to demonstrate significant C# 3.0 features. If you have a different preferred algorithm, post it yourself. In fact, you can register at Project Euler and post your own code.
- I will post blog entries more or less at the same time I update the code. You might see the code before I discuss it. If you don't want spoilers, don't do it.
- I will discuss the algorithms and the answers freely. If you want to figure out the problems yourself, don't read too far before you try it yourself. Or, once again, signup at Project Euler and try yourself before I post my answers.
- I will do the problems in order, so if you're interested in avoiding spoilers, you can work in order, and stay ahead of where I'm at. (The first three problems took me less than 2 hours from start to finish).

Ok, with that out of the way, here's the code for the first problem. (Really, it's not that hard. I'm not giving much away here). In the first problem, you need to find the sum of all natural numbers below 1000 that are multiple of 3 and 5.

It's one (or two) lines of code in C# 3.0:

`var nums = from n in`

Generators.NumberSequence(0, 1000)`where ((n % 3 == 0) || (n % 5 == 0))`

`select n;`

`var answer = nums.Sum();`

I should also show you the code for NumberSequence. I figure I'll need sequences of numbers fairly often in this projecxt, so I pulled that into a library:

`public static IEnumerable<int> NumberSequence(int from, int to)`

`{`

`do`

`{`

`yield return from++;`

`} while (from < to);`

`}`

Yes, this method assumes that from is less than to. Seems like a reasonable assumption at this time.

You can download the code for the first three problems here: http://code.msdn.microsoft.com/EulerCSharp

Note that I said 3 problems. I uploaded the code for the first three problems on Project Euler, so you may want to wait if you want to avoid spoilers.

I create content for .NET Core. My work appears in the .NET Core documentation site. I'm primarily responsible for the section that will help you learn C#.

All of these projects are Open Source (using the Creative Commons license for content, and the MIT license for code). If you would like to contribute, visit our GitHub Repository. Or, if you have questions, comments, or ideas for improvement, please create an issue for us.