Project Euler #0001: Multiples of 3 and 5

Problem Description

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.

Simple Solution

The simplest solution is to iterate over all numbers up to the limit. If any of these numbers is a multiple of one of the factors then it is included in the summation.

public static ulong SumFactorMultiplesBelowLimit(int limit, params int[] factors)
{
    if (factors == null
        || !factors.Any())
    {
        throw new System.ArgumentException("Invalid factors.", nameof(factors));
    }

    ulong sum = 0;

    for (int i = 0; i < limit; i++)
    {
        foreach (int factor in factors)
        {
            if (i % factor == 0)
            {
                sum += (ulong)i;
                break;
            }
        }
    }

    return sum;
}

Timing the operation yields:

Minimum Elapsed: 00:00:00.0000114 Average Elapsed: 00:00:00.0000545 Maximum Elapsed: 00:00:00.0004331

Pretty quick, but that is most likely because the problem space is small. If the limit is increased, or if more factors are introduced the number of operations performed is increased. In big-o notation, this approach is $$ O(n * m) $$.

Asynchronous Simple Solution

Note, this particular approach is not recommended for the problem as it is laid out in the description but is included to compare results and as a thought experiment. This solution could be viable if the number of factors used increased and there was a mechanism to reduce the amount of duplicated iterative work performed.

Another possible way to structure a solution to the problem is by giving each factor provided a thread to calculate the multiples up to the limit it has. Once each thread has been completed, the resulting multiples are compared for matching numbers that are used to generate a sum:

public static async Task<int> SimpleSumFactorMultiplesBelowLimitAsync(int limit, params int[] factors)
{
    if (factors == null
        || !factors.Any())
    {
        throw new System.ArgumentException("Invalid factors.", nameof(factors));
    }

    IList<Task<ICollection<int>>> taskCollection =
        new List<Task<ICollection<int>>>();

    foreach (int factor in factors)
    {
        taskCollection.Add(GetFactorMultiplesBelowLimitAsync(limit, factor));
    }

    await Task.WhenAll(taskCollection);

    ICollection<int> factorMultiples =
        new HashSet<int>(await taskCollection.First());

    for (int i = 1; i < taskCollection.Count; i++)
    {
        ICollection<int> factorMultiplesResults = await taskCollection[i];
        foreach (int factorMultiple in factorMultiplesResults)
        {
            factorMultiples.Add(factorMultiple);
        }
    }

    return factorMultiples.Sum();
}

The iterative work for this solution was extracted to a helper method to parallelize it:

public static async Task<ICollection<int>> GetFactorMultiplesBelowLimitAsync(int limit, int factor)
{
    ICollection<int> factorMultiples = new HashSet<int>();

    for (int i = 0; i < limit; i++)
    {
        if (i % factor == 0)
        {
            factorMultiples.Add(i);
        }
    }

    return factorMultiples;
}

This is not the prettiest solution by any stretch and yields slightly worse results than the Simple Solution:

Minimum Elapsed: 00:00:00.0000317 Average Elapsed: 00:00:00.0002025 Maximum Elapsed: 00:00:00.0017206

The results are not surprising because of how the work is performed. There are two or more loops iterating over all of the numbers - duplicating the number of operations and comparisons that must be done.

One possible improvement for this solution could be to have a single shared collection of possible numbers that would be updated to reduce the number of iterations that are performed by each thread instead of joining the results after they have all been completed. This could also introduce a race condition so a thread-safe data structure is recommended if this approach is taken.

Another possible improvement would be to start with the largest factor from the available factors so that the initial set of numbers is the smallest starting point that it could be to iterate over.

As stated before, this is not a recommended solution when the number of factors is small since the iterative work is duplicated. The only redeeming factor of this approach is that the work is done on multiple threads so if two threads are available at the same time the solution may be the same as the Synchronous Simple Solution. This can be seen in the Minimum Elapsed Time measurement being comparable to the Average Elapsed Time in the previous results.

Simple LINQ Solution

The Simple Solution can be converted into a more fluent LINQ syntax - at the cost of some performance:

public static ulong SimpleLinqSumFactorMultiplesBelowLimit(int limit, params int[] factors)
{
    if (factors == null
        || !factors.Any())
    {
        throw new System.ArgumentException("Invalid factors.", nameof(factors));
    }

    return (ulong)Enumerable.Range(1, limit - 1)
        .Where(number => factors.Any(factor => number % factor == 0))
        .Sum();
}

The type cast is necessary to convert the Sum() operation to the return type. This could cause a little performance degradation but was not significant in the measurements.

This solution reads a little easier to read and possibly understand since it reads like a sentence.

The results of this solution are:

Minimum Elapsed: 00:00:00.0000574 Average Elapsed: 00:00:00.0001152 Maximum Elapsed: 00:00:00.0006285

As expected, this is slower than the simple solution but still fast. The tradeoff could be worth it for the improved readability.

Surprisingly, this solution is slower than the asynchronous solution in some scenarios - seen by comparing the Minimum Elapsed Time of the two results.

Algorithmic Solution

The simple solution satisfies the criteria to generate an answer, but the performance can be improved by looking for an algorithmic solution instead of a brute-force solution. Conveniently, the problem is asking for a solution to a Finite Arithmetic Progression, specifically an Arithmetic Series which has an algorithmic solution.

… a sequence of numbers such that the difference between the consecutive terms is constant. … The sum of the members of a finite arithmetic progression is called an arithmetic series. … [The] sum can be found quickly by taking the number n of terms being added, multiplying by the sum of the first and last number in the progression, and dividing by 2:

The equation for solving this kind of problem is:

$$\begin{equation} n(a_1+a_n)\over2 \end{equation}$$

In this equation:

• $$ n $$ is the number of terms being added.
• $$ a_1 $$ is the initial term.
• $$ a_n $$ is the last number in the progression.

Using the value 3 from the problem description’s example in this manner yields the following progression:

$$ 3 + 6 + 9 $$

The $$ n $$ in the algorithm can be solved by taking the limit and dividing it by the starting term in the progression and discarding any remainder.

When substituting values into the equation it becomes the following:

$$\begin{eqnarray} 3(3 + 9)\over2 &=& 3(12)\over2 &=& 36\over2 &=& 18 \end{eqnarray}$$

With this algorithm, the sum for each specified multiple can be calculated. Keep in mind that all shared multiples for all factors must be subtracted. In the problem description this would be $$ 5 * 3 = 15 $$ if the limit was larger than the multiple (15 in this case).

Synchronous Algorithmic Solution

A synchronous solution for this problem with only two factors could look something like this:

public static async Task<int> AlgorithmicSumFactorMultiplesBelowLimit(int limit, params int[] factors)
{
    if (factors == null
        || !factors.Any())
    {
        throw new System.ArgumentException("Invalid factors.", nameof(factors));
    }

    int sum = 0;
    ICollection<int> factorLookup = new HashSet<int>(factors);
    ICollection<int> multiples = new HashSet<int>();

    for(int i = 0; i < factors.Length; i++)
    {
        int factor = factors[i];
        sum += AlgorithmicSumFactorBelowLimit(limit, factor);

        for (int j = i + 1; j < factors.Length; j++)
        {
            int multiple = factor * factors[j];

            if (!factorLookup.Contains(multiple)
                && limit > multiple
                && !multiples.Contains(multiple))
            {
                multiples.Add(multiple);
                sum -= AlgorithmicSumFactorBelowLimit(limit, multiple);
            }
        }
    }

    return sum;
}

The AlgorithmicSumFactorBelowLimit method looks like this:

private static int AlgorithmicSumFactorBelowLimit(int limit, int factor)
{
    int n = (limit - 1) / factor;
    int a1 = factor;
    int an = n * a1;

    return n * (a1 + an) / 2;
}

The limit is subtracted by one when calculating $$ n $$ so that factors that evenly divide the limit do not generate an off-by-one error.

The performance of this solution is:

Minimum Elapsed: 00:00:00.0000007 Average Elapsed: 00:00:00.0000011 Maximum Elapsed: 00:00:00.0000045

Initially, I had the algorithmic method asynchronous to share code but wanted to ensure there was not any skewing of results that may have occurred from .GetAwaiter().GetResult(). Spoiler alert, the results were approximately the same in both - meaning there probably would not have been any perceptible difference in the results.

Asynchronous Algorithmic Solution

public static async Task<int> AlgorithmicSumFactorMultiplesBelowLimitAsync(int limit, params int[] factors)
{
    if (factors == null
        || !factors.Any())
    {
        throw new System.ArgumentException("Invalid factors.", nameof(factors));
    }

    int sum = 0;
    ICollection<int> factorLookup = new HashSet<int>(factors);
    ICollection<int> multiples = new HashSet<int>();

    for (int i = 0; i < factors.Length; i++)
    {
        int factor = factors[i];
        sum += AlgorithmicSumFactorBelowLimit(limit, factor);

        for (int j = i + 1; j < factors.Length; j++)
        {
            int multiple = factor * factors[j];

            if (!factorLookup.Contains(multiple)
                && limit > multiple
                && !multiples.Contains(multiple))
            {
                multiples.Add(multiple);
                sum -= AlgorithmicSumFactorBelowLimit(limit, multiple);
            }
        }
    }

    return sum;
}

And updating the algorithm to be asynchronous as well:

private static async Task<int> AlgorithmicSumFactorBelowLimitAsync(int limit, int factor)
{
    int n = (limit - 1) / factor;
    int a1 = factor;
    int an = n * a1;

    return n * (a1 + an) / 2;
}

Measuring the performance of this solution generated:

Minimum Elapsed: 00:00:00.0000006 Average Elapsed: 00:00:00.0000010 Maximum Elapsed: 00:00:00.0000022

In this case, the asynchronous solution impacts the performance results positively because each thread can contribute to solving the problem without duplicating any of the work.

Because each thread can do work in isolation, this solution will scale well even as the number of factors increases - as long as there are threads available to do the processing work.