Create a function that calculates the sum of all numbers dividable by 3 and 5 up to a specific value.

This is a task 1 of chapter 1 of the Modern C++ Challenge book written by Marius Bancila, which I bought a few weeks ago.

The task is quite simple and the easiest solution is to iterate over all numbers and sum up each which matches the condition.

The easy one

The book’s solution is quite similar to this:

size_t fizzbuzz_sum(size_t maxval) {
  size_t sum = 0;
  for(size_t i = 0; i < maxval; ++i) {
      sum += (i % 3 == 0 || i % 5 == 0) ? i : 0;
  }
  return sum;
}

Simply loop from 0 to given maximum and add each number dividable by 3 or 5 to the result.

Ranges solution

Using C++20 ranges is also possible (the book targets C++17, so this wasn’t an option there):

size_t fizzbuzz_sum(size_t maxval) {
  auto div3or5 = [](size_t val) {
    return val % 3 == 0 || val % 5 == 0;
  };
  auto r = std::ranges::iota_view((size_t)0, maxval)
    | std::views::filter(div3or5)
    | std::ranges::views::common;
  return std::accumulate(r.begin(), r.end(), (size_t)0);
}

std::ranges::iota_view((size_t)0, maxval) creates a range from 0 to given maximum (excluding).
This is filtered by all values matching the condition div3or5.
The std::ranges::views::common pipe is necessary for making the result usable in the algorithms requiring begin and end iterators of same type, such as the used std::accumulate which creates a sum of all values in the given range.

Even if usage of raw loops as in the first solution is a code smell, I would prefer that raw loop in this case -
a lot better readable und not even slower.

Two loops

A bit like the first solution, but fewer loop steps by using a step size matching to the filtering numbers:

size_t fizzbuzz_sum(size_t maxval) {
  size_t sum = 0;
  for(size_t i = 3; i < maxval; i+= 3)
    sum += i;
  for(size_t i = 5; i < maxval; i+= 5)
    sum += i % 3 ? i : 0;
  return sum;
}

The first loop simply sums up all numbers starting from 3 until the given maximum, but using a step of 3.
This saves the condition check.

The second loop does the same with 5, but has to check if the number hasn’t already summed up by the first loop.
I check this condition in this loop because it has less steps.

Mathematical solution

After a sleeping about it, I came up with a mathematical solution. Lets look what the algorithms above are dooing: they sum up a multiple of three or five:

3 + 6 + 9 + 12 + 15 + 18 + ..n

which is the same as

1*3 + 2*3 + 3*3 + 4*3 + 5*3 + 6*5 + ..n*3

after applying the distributive law:

3 * (1 + 2 + 3 + 4 + 5 + 6 + ..n)

Now we only have to find out how the value in brackets can be calculated.
Here the gaussian summary formula is what we need:

n * (n + 1) / 2

So the only thing we need is to calculate how often 3 or 5 fits into the defined range, put that into the gauss sum formula and multiply by 3 (or 5, respectivly).
Important: the given upper bound (here named maxval) isn’t part of the range, so it is decremented by one before using it.

n = (maxval - 1) / 3
(n * (n + 1) / 2) * 3

and

n = (maxval - 1) / 5
(n * (n + 1) / 2) * 5

There is only one problem left: when we add those both result, we get some values doubled: those where both 3 and 5 divide them:

To solve this, we simply use the upper formular with the product of 3 * 5 = 15 and subtract it.
(this is the same what is done in the two loops example when iterating with a step of 5).

Now we have created a fast algorithm with a constant time complexity O(1):

size_t fizzbuzz_sum(size_t maxval) {
  auto gauss_sum=[](size_t n) { return n * (n+1) / 2;};
  --maxval;
  return gauss_sum(maxval /  3) *  3
       + gauss_sum(maxval /  5) *  5
       - gauss_sum(maxval / 15) * 15;
}