Project Euler 1: Multiples of 3 and 5

This anecdote shows that there are two ways to solve this first problem. The smart method that Gauss used or the slow brute force method that his fellow pupils used. The brute force solution requires many steps to find the answer. The smart solution uses a one-step formula, such as the young Gauss and Aryabhata had figured out.

The most inefficient solution is to test whether all numbers between 1 and 999 are divisible by 3 or 5 and then add all these number. The R language provides several ways to step through a sequence of numbers.

The code below loops trough the numbers between 1 and 999.

  # Project Euler 1: Multiples of 3 and 5
  
  # Loop

  answer <- 0
  for (i in 1:999) {
    if (i %% 3 == 0 | i %% 5 == 0) {
      answer <- answer + i
      print(i)
    }
  }
  print(answer)

This first solution is elaborate. Using for-loops in R should always be a last resort in R coding because they are the slowest way to compute over a series of steps. The next two solutions solve this problem by using vector arithmetic. These methods are much faster because they run the loop directly in machine code instead of having to compile each step.

The solution for the first problem only requires one line of code when using vector arithmetic.

  # Vector aritmetic
  
  sum((1:999)[((1:999) %% 3 == 0) | ((1:999) %% 5 == 0)])

Although the vector arithmetic is much faster than the for-loop, it is still not as fast as using the methods discovered by Aryabhata and Gauss. The two brute-force solutions are very fast because of the low number of steps to find a solution. An analytical solution reduces the processing time significantly, as it only requires one step.

The problem involves arithmetic progressions, which are sequences of numbers with a constant difference. The sequence 1, 4, 7, 10, 13, … is an arithmetic progression with a common difference of three.

We can generalise the method discovered by Gauss. The sum of an arithmetic progression ($S_n$), where $n$ is the number of elements and $a_1$ and $a_n$ are the lowest and highest value, is:

$$S_n= \frac{n(a_{1} + a_n)}{2}$$

The numbers divisible by $n=3$ can be expressed as:

$$\mathrm{sum}_3(999)=3+6+9+12+ \ldots + 999 = 3(1+2+3+4+ \ldots + 333)$$

We can now calculate the sum of all divisors by combining the above progression with the formula for arithmetic progressions as expressed in the above code, where $m$ is the divisor and $n$ the extent of the sequence. $p$ is the highest number less than $n$ divisible by $m$. In the case of 5, this number is 995.

$$p = n \lfloor (m/n) \rfloor$$

Substitution gives:

$$\mathrm{sum}_m(n) = p \frac{1+(p/m)}{2}$$

  # Analytical solution
  
  SumDivBy <- function(m, n) {
      p <- floor(n / m) * m # Round to multiple of n
      return (p * (1 + (p / m)) / 2)
  }
  SumDivBy(3, 999) + SumDivBy(5, 999) - SumDivBy(15, 999)

As seen on R Bloggers