Project Euler with modern functional C++

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,\ldots,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 + \ldots + 10^2 = 385. \] TThe square of the sum of the first ten natural numbers is, \[ (1 + 2 + \ldots + 10)^2 = 55^2 = 3025. \] Hence 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 \(6\)th prime is \(13\). What is the \(10 0001\)st 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,\ldots) \).
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 \(100001\)st prime, we simply take the iterator to the first element and advance it \(10000\) times with ranges::next, then dereference it.