Project Euler with modern functional C++ [2024-04-10]

From the Project Euler website, “Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems”.

C++20 brought with it the ranges library, providing a slew of functional constructs. I have opted to use select early problems from Project Euler to demonstrate utilization of some these functional constructs, along with an explanation for each.

Problem 1

If we list all 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.

std::ranges::fold_left(std::views::iota(1, 1000)
    | std::views::filter([](auto n) { return n % 3 == 0 || n % 5 == 0; }),
    0, std::plus{});
  • ranges::fold_left(r, i, o) performs a left fold over the range r with an initial value i using operation o.
  • views::iota(n, m) creates a sequence n,n+1,...,m-2,m-1.
  • views::filter(p) creates an adaptor a with predicate p, which can then be applied to a range as r | a, resulting in a new view containing only the elements of r for which p holds.
  • plus is actually from the functional header, and is a function object performing binary addition. That is to say, it implements constexpr T operator()(T const& l, T const& r) const.

Using these constructs, solving the problem is trivial. We can construct the sequence of all natural numbers below 1000 with views::iota(1, 1000). Then, the sequence of all natural numbers below 1000 which are multiples of 3 or 5 can be attained by applying views::filter([](auto n) { return n % 3 == 0 || n % 5 == 0; }) to this range. Finally, to get the sum, we fold the range with addition and an initial value of 0.

Problem 6

The sum of the squares of the first ten natural numbers is 1^2+2^3+...+10^2=385The square of the sum of the first ten natural numbers is(1+2+...+10)^2=55^2=3025Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

auto sqr = [](auto n) { return n * n; };
return sqr(std::ranges::fold_left(std::views::iota(1, 101),
            0, std::plus{}))
    - std::ranges::fold_left(std::views::iota(1, 101)
            | std::views::transform(sqr), 0, std::plus{});
  • views::transform(f) provides a map operation. It creates an adaptor a with function f, which can then be applied to a range as r | a, resulting in a new view containing containing the elements of r each with f applied.

The sum of the first one hundred natural numbers can be found by folding over views::iota(1, 101) with plus; this can then be squared to achieve the square of the sum. To calculate the sum of squares, we can apply x * x to every element of views::iota(1, 101) before folding using views::transform.

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 0001st prime number?

*std::ranges::next(
    (std::views::iota(2)
    | std::views::filter([](auto n) {
        return std::ranges::none_of(
            std::views::iota(2, n == 2 ? 2 : n - 1),
            [n](auto m) { return n % m == 0; });
    })).begin(), 10000);
  • ranges::next(i, n) returns the iterator i advanced n times.
  • views::iota(n) creates a sequence (n,n+1,...).
  • ranges::none_of(r, p) returns true if none of the elements in range r satisfy predicate p, false otherwise.

A number is prime if it is not divisble by any smaller natural numbers (excluding 1; of course we can apply further optimizations here but it isn't necessary to understand the problem). The numbers to check by can be defined then as views::iota(2, n == 2 ? 2 : n - 1). Then, we can check if any of the numbers in this range divide n using ranges::none_of with a predicate n % m == 0. We now have a way to check if a number n is prime, and can use this as a predicate to filter a views::iota(2), resulting in a sequence of all prime numbers. To get the 100001st prime, we simply take the iterator to the first element and advance it 10000 times with ranges::next, then dereference it.