Project Euler: Problem 1 (Possible refactorings and run time optimizations)

Question

I have been hearing a lot about Project Euler so I thought I solve one of the problems in C#. The problem as stated on the website is as follows:

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.

I wrote my code as follows:

  class EulerProblem1
    {
        public static void Main()
        {
            var totalNum = 1000;
            var counter = 1;
            var sum = 0;

            while (counter < totalNum)
            {
                if (DivisibleByThreeOrFive(counter))
                    sum += counter;

                counter++;
            }

            Console.WriteLine("Total Sum: {0}", sum);
            Console.ReadKey();
        }

        private static bool DivisibleByThreeOrFive(int counter)
        {
            return ((counter % 3 == 0) || (counter % 5 == 0));

        }
    } 

It will be great to get some ideas on alternate implementations with less verbosity/cleaner syntax and better optimizations. The ideas may vary from quick and dirty to bringing out the cannon to annihilate the mosquito. The purpose is to explore the depths of computer science while trying to improve this particularly trivial code snippet.

Thanks

Answer 1

That's basically the same way I did that problem. I know there were other solutions (probably more efficient ones too) on the forums for project-euler.

Once you input your answer going back to the question gives you the option to go to the forum for that problem. You may want to look there!

Answer 2

Updated to not double count numbers that are multiples of both 3 and 5:

int EulerProblem(int totalNum)
{
   int a = (totalNum-1)/3;
   int b = (totalNum-1)/5;
   int c = (totalNum-1)/15;
   int d = a*(a+1)/2;
   int e = b*(b+1)/2;
   int f = c*(c+1)/2;
   return 3*d + 5*e - 15*f;
}

Answer 3

The code in DivisibleByThreeOrFive would be slightly faster if you would state it as follows:

return ((counter % 3 == 0) || (counter % 5 == 0));

And if you do not want to rely on the compiler to inline the function call, you could do this yourself by putting this code into the Main routine.

Answer 4

You can come up with a closed form solution for this. The trick is to look for patterns. Try listing out the terms in the sum up to say ten, or twenty and then using algebra to group them. By making appropriate substitutions you can generalize that to numbers other than ten. Just be careful about edge cases.

Answer 5

Here's a transliteration of my original F# solution into C#. Edited: It's basically mbeckish's solution as a loop rather than a function (and I remove the double count). I like mbeckish's better.

static int Euler1 ()
{
  int sum = 0;

  for (int i=3; i<1000; i+=3) sum+=i;
  for (int i=5; i<1000; i+=5) sum+=i;
  for (int i=15; i<1000; i+=15) sum-=i;

  return sum;
}

Here's the original:

let euler1 d0 d1 n =
  (seq {d0..d0..n}       |> Seq.sum) +
  (seq {d1..d1..n}       |> Seq.sum) -
  (seq {d0*d1..d0*d1..n} |> Seq.sum)

let result = euler1 3 5 (1000-1)

Answer 6

With LINQ (updated as suggested in comments)

static void Main(string[] args)
{
    var total = Enumerable.Range(0,1000)
                    .Where(counter => (counter%3 == 0) || (counter%5 == 0))
                    .Sum();

    Console.WriteLine(total);
    Console.ReadKey();
}

Answer 7

I like technielogys idea, here's my idea of a modification

static int Euler1 () 
{ 
  int sum = 0; 

  for (int i=3; i<1000; i+=3) 
  {
    if (i % 5 == 0) continue;
    sum+=i; 
  }
  for (int i=5; i<1000; i+=5) sum+=i; 

  return sum; 
} 

Though also comes to mind is maybe a minor heuristic, does this make any improvement?

static int Euler1 () 
{ 
  int sum = 0; 

  for (int i=3; i<1000; i+=3) 
  {
    if (i % 5 == 0) continue;
    sum+=i; 
  }
  for (int i=5; i<250; i+=5)
  {
    sum+=i;
  }
  for (int i=250; i<500; i+=5)
  {
    sum+=i;
    sum+=i*2;
    sum+=(i*2)+5;
  }

  return sum; 
} 

Answer 8

I haven't written any Java in a while, but this should solve it in constant time with little overhead:

public class EulerProblem1
{
    private static final int EULER1 = 233168;
    // Equal to the sum of all natural numbers less than 1000
    // which are multiples of 3 or 5, inclusive.

    public static void main(String[] args)
    {
        System.out.println(EULER1);
    }
}

EDIT: Here's a C implementation, if every instruction counts:

#define STDOUT     1
#define OUT_LENGTH 8

int main (int argc, char **argv)
{
    const char out[OUT_LENGTH] = "233168\n";
    write(STDOUT, out, OUT_LENGTH);
}

Notes:

• There's no error handling on the call to write. If true robustness is needed, a more sophisticated error handling strategy must be employed. Whether the added complexity is worth greater reliability depends on the needs of the user.
• If you have memory constraints, you may be able to save a byte by using a straight char array rather than a string terminated by a superfluous null character. In practice, however, out would almost certainly be padded to 8 bytes anyway.
• Although the declaration of the out variable could be avoided by placing the string inline in the write call, any real compiler willoptimize away the declaration.
• The write syscall is used in preference to puts or similar to avoid the additional overhead. Theoretically, you could invoke the system call directly, perhaps saving a few cycles, but this would raise significant portability issues. Your mileage may vary regarding whether this is an acceptable tradeoff.

Answer 9

Try this, in C. It's constant time, and there's only one division (two if the compiler doesn't optimize the div/mod, which it should). I'm sure it's possible to make it a bit more obvious, but this should work.

It basically divides the sum into two parts. The greater part (for N >= 15) is a simple quadratic function that divides N into exact blocks of 15. The lesser part is the last bit that doesn't fit into a block. The latter bit is messier, but there are only a few possibilities, so a LUT will solve it in no time.

const unsigned long N = 1000 - 1;
const unsigned long q = N / 15;
const unsigned long r = N % 15;
const unsigned long rc = N - r;

unsigned long sum = ((q * 105 + 15) * q) >> 1;

switch (r) {
    case 3  : sum += 3  + 1*rc ; break;
    case 4  : sum += 3  + 1*rc ; break;
    case 5  : sum += 8  + 2*rc ; break;
    case 6  : sum += 14 + 3*rc ; break;
    case 7  : sum += 14 + 3*rc ; break;
    case 8  : sum += 14 + 3*rc ; break;
    case 9  : sum += 23 + 4*rc ; break;
    case 10 : sum += 33 + 5*rc ; break;
    case 11 : sum += 33 + 5*rc ; break;
    case 12 : sum += 45 + 6*rc ; break;
    case 13 : sum += 45 + 6*rc ; break;
    case 14 : sum += 45 + 6*rc ; break;
}

Answer 10

You can do something like this:

Func<int,int> Euler = total=> 
    new List<int>() {3,5}
        .Select(m => ((int) (total-1) / m) * m * (((int) (total-1) / m) + 1) / 2)
        .Aggregate( (T, m) => T+=m);

You still have the double counting problem. I'll think about this a little more.

Edit:

Here is a working (if slightly inelegant) solution in LINQ:

        var li = new List<int>() { 3, 5 };
        Func<int, int, int> Summation = (total, m) => 
           ((int) (total-1) / m) * m * (((int) (total-1) / m) + 1) / 2;

        Func<int,int> Euler = total=> 
            li
                .Select(m => Summation(total, m))
                .Aggregate((T, m) => T+=m)
            - Summation(total, li.Aggregate((T, m) => T*=m));

Can any of you guys improve on this?

Explanation:

Remember the summation formula for a linear progression is n(n+1)/2. In the first case where you have multiples of 3,5 < 10, you want Sum(3+6+9,5). Setting total=10, you make a sequence of the integers 1 .. (int) (total-1)/3, and then sum the sequence and multiply by 3. You can easily see that we're just setting n=(int) (total-1)/3, then using the summation formula and multiplying by 3. A little algebra gives us the formula for the Summation functor.

Answer 11

Refactoring @mbeckish's very clever solution:

public int eulerProblem(int max) {
    int t1 = f(max, 3);
    int t2 = f(max, 5);
    int t3 = f(max, 3 * 5);
    return t1 + t2 - t3;
}

private int f(int max, int n) {
    int a = (max - 1) / n;
    return n * a * (a + 1) / 2;
}