SoggyByte Ideas that aren't even half-baked…

Project Euler :: Problem #2

Continuing with the Project Euler problems, I’ll go over my solution to Problem #2.

Problem #2 says:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2 the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all of the even-valued terms in the sequence which do not exceed four million.

First, a little on the Fibonacci Numbers. Fibonacci Numbers are numbers in the Fibonacci Sequence. The down-and-dirty version of the sequence is that the numbers are the sum of the sequence of the last 2 numbers in the sequence. Wikipedia has this great little PNG definition explaining it clearly:

If the number we’re trying to find in the Fibonacci Number of is less than or equal to 1 then the Fibonacci Number is the original number itself. Integers greater than 1 is where things get interesting. You can see that the formula at that point becomes:

F_n = F_{n – 2} + F_{n – 1}

Yay, recursion! So each number greater than 1 we compute the Fibonacci Number for n – 2 and for n – 1 and then add them together. Lets try with a couple numbers:

F₄ = F_{4 – 2} + F_{4 – 1}
F₄ = F₂ + F₃
F₄ = (F_{2 – 2} + F_{2 – 1}) + (F_{3 – 2} + F_{3 – 1})
F₄ = (F₀ + F₁) + (F₁ + F₂)
F₄ = (0 + 1) + (1 + (F_{2 – 2} + F_{2 – 1}))
F₄ = (0 + 1) + (1 + (F₀ + F₁))
F₄ = (0 + 1) + (1 + (0 + 1))
F₄ = 0 + 1 + 1 + 0 + 1
F₄ = 3

Jeeeeeez, that’s a of work. Maybe we’ll skip “doing a couple” and just go right to the code. The problem says that we need to find the sum of all of the even terms in the Sequence below 4,000,000. So what we”ll do is iterate over a set of numbers adding the even terms to our holding variable until we reach our limit.

using System;

class Program
{
  public static void Main(string[] Args)
  {
    int l = (Args.Length > 0 ? Int32.Parse(Args[0]) : 4000000);
    int sumOfEvens = 0;

    for (int i = 0; ; i++)
    {
      int f = ComputeFib(i);

      if (f >= l)
        break;
      if (f % 2 == 0)
        sumOfEvens += f;
    }

    Console.WriteLine(sumOfEvens.ToString());
    Console.WriteLine("Done, press enter to quit...");
    Console.ReadLine();
  }

  public static int ComputeFib(int n)
  {
    if (n == 0 || n == 1)
      return n;

    return ComputeFib(n - 2) + ComputeFib(n - 1);
  }
}

Project Euler :: Problem #1

Project Euler, for those that don”t know, is a pretty neat little website that presents some fun questions that take some math skills and the ability to use the math you know in a programming language. There is no requirement or suggestion for what language to use, or anything like that. Just that you get the right answer to the question.

I’ve been doing these on and off for about two weeks now, and I have only finished the first 13 (there are a total of 235). On to Problem 1…

Problem #1 says:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

So there are a few things we have to do to solve this problem. We need to iterate up to 1000 while determining if each stop along the way is divisible by either 3 or 5, and if a number is divisible by either one then we need to add it to a running total. Also, please note I like to assign the “variable” parts of these problems via input from the command-line.

using System;
class Program
{
  public static void Main(string[] Args)
  {
    if (Args.Length < 1)
      Args = new string[] { "1000" };

    int s = 0;
    for (int i = 1; i < Int32.Parse(Args[0]); i++)
    {
      if (i % 3 == 0 || i % 5 == 0)
        s += i;
    }

    Console.WriteLine(s.ToString());
  }
}

There we go, that’s all there is to it.

System.Console.WriteLine(”Hello world!”);

Welcome one and all to what will probably be the most boring blog on the web.

I’m a developer living in Indianapolis, IN. I work for a small-ish company that writes software for Indiana-based school corporations. I focus on the business aspect (payroll, purchasing, invoicing, receipting, payments) of the corporations. I write most of my code in C# using the .NET Framework 2.0, with the occasional foray into the Progress 4GL when supporting “legacy” applications.

I expect to use this forum mostly to get some of my code “out there”, to share my solutions to some problems, and to discuss the aspects of programming languages that I am familiar with. There may also be random bitching, whining, and other such loveliness.

Welcome, and please continue to visit!