The Dirichlet convolution is a special kind of convolution that appears as a very useful tool in number theory. It operates on the set of arithmetic functions.
Challenge
Given two arithmetic functions \$f,g\$ (i.e. functions \$f,g: \mathbb N \to \mathbb R\$) compute the Dirichlet convolution \$(f * g): \mathbb N \to \mathbb R\$ as defined below.
Details
- We use the convention \$ 0 \notin \mathbb N = \{1,2,3,\ldots \}\$.
- The Dirichlet convolution \$f*g\$ of two arithmetic functions \$f,g\$ is again an arithmetic function, and it is defined as $$(f * g)(n) = \sum_\limits{d|n} f\left(\frac{n}{d}\right)\cdot g(d) = \sum_{i\cdot j = n} f(i)\cdot g(j).$$ (Both sums are equivalent. The expression \$d|n\$ means \$d \in \mathbb N\$ divides \$n\$, therefore the summation is over the natural divisors of \$n\$. Similarly we can subsitute \$ i = \frac{n}{d} \in \mathbb N, j =d \in \mathbb N \$ and we get the second equivalent formulation. If you're not used to this notation there is a step by step example at below.) Just to elaborate (this is not directly relevant for this challenge): The definition comes from computing the product of Dirichlet series: $$\left(\sum_{n\in\mathbb N}\frac{f(n)}{n^s}\right)\cdot \left(\sum_{n\in\mathbb N}\frac{g(n)}{n^s}\right) = \sum_{n\in\mathbb N}\frac{(f * g)(n)}{n^s}$$
- The input is given as two black box functions. Alternatively, you could also use an infinite list, a generator, a stream or something similar that could produce an unlimited number of values.
- There are two output methods: Either a function \$f*g\$ is returned, or alternatively you can take take an additional input \$n \in \mathbb N\$ and return \$(f*g)(n)\$ directly.
- For simplicity you can assume that every element of \$ \mathbb N\$ can be represented with e.g. a positive 32-bit int.
- For simplicity you can also assume that every entry \$ \mathbb R \$ can be represented by e.g. a single real floating point number.
Examples
Let us first define a few functions. Note that the list of numbers below each definition represents the first few values of that function.
- the multiplicative identity (A000007)
$$\epsilon(n) = \begin{cases}1 & n=1 \\ 0 & n>1 \end{cases}$$
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... - the constant unit function (A000012)$$ \mathbb 1(n) = 1 \: \forall n $$
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... - the identity function (A000027)
$$ id(n) = n \: \forall n $$
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ... - the Möbius function (A008683)
$$ \mu(n) = \begin{cases} (-1)^k & \text{ if } n \text{ is squarefree and } k \text{ is the number of Primefactors of } n \\ 0 & \text{ otherwise } \end{cases} $$
1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, ... - the Euler totient function (A000010)
$$ \varphi(n) = n\prod_{p|n} \left( 1 - \frac{1}{p}\right) $$
1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, ... - the Liouville function (A008836)
$$ \lambda (n) = (-1)^k $$ where \$k\$ is the number of prime factors of \$n\$ counted with multiplicity
1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1, ... - the divisor sum function (A000203)
$$\sigma(n) = \sum_{d | n} d $$
1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, ... - the divisor counting function (A000005)
$$\tau(n) = \sum_{d | n} 1 $$
1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, ... - the characteristic function of square numbers (A010052)
$$sq(n) = \begin{cases} 1 & \text{ if } n \text{ is a square number} \\ 0 & \text{otherwise}\end{cases}$$
1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...
Then we have following examples:
- \$ \epsilon = \mathbb 1 * \mu \$
- \$ f = \epsilon * f \: \forall f \$
- \$ \epsilon = \lambda * \vert \mu \vert \$
- \$ \sigma = \varphi * \tau \$
- \$ id = \sigma * \mu\$ and \$ \sigma = id * \mathbb 1\$
- \$ sq = \lambda * \mathbb 1 \$ and \$ \lambda = \mu * sq\$
- \$ \tau = \mathbb 1 * \mathbb 1\$ and \$ \mathbb 1 = \tau * \mu \$
- \$ id = \varphi * \mathbb 1 \$ and \$ \varphi = id * \mu \$
The last for are a consequence of the Möbius inversion: For any \$f,g\$ the equation \$ g = f * 1\$ is equivalent to \$f = g * \mu \$.
Step by Step Example
This is an example that is computed step by step for those not familiar with the notation used in the definition. Consider the functions \$f = \mu\$ and \$g = \sigma\$. We will now evaluate their convolution \$\mu * \sigma\$ at \$ n=12\$. Their first few terms are listed in the table below.
$$\begin{array}{c|ccccccccccccc} f & f(1) & f(2) & f(3) & f(4) & f(5) & f(6) & f(7) & f(8) & f(9) & f(10) & f(11) & f(12) \\ \hline \mu & 1 & -1 & -1 & 0 & -1 & 1 & -1 & 0 & 0 & 1 & -1 & 0 \\ \sigma & 1 & 3 & 4 & 7 & 6 & 12 & 8 & 15 & 13 & 18 & 12 & 28 \\ \end{array}$$
The sum iterates over all natural numbers \$ d \in \mathbb N\$ that divide \$n=12\$, thus \$d\$ assumes all the natural divisors of \$n=12 = 2^2\cdot 3\$. These are \$d =1,2,3,4,6,12\$. In each summand, we evaluate \$g= \sigma\$ at \$d\$ and multiply it with \$f = \mu\$ evaluated at \$\frac{n}{d}\$. Now we can conclude
$$\begin{array}{rlccccc} (\mu * \sigma)(12) &= \mu(12)\sigma(1) &+\mu(6)\sigma(2) &+\mu(4)\sigma(3) &+\mu(3)\sigma(4) &+\mu(2)\sigma(6) &+\mu(1)\sigma(12) \\ &= 0\cdot 1 &+ 1\cdot 3 &+ 0 \cdot 4 &+ (-1)\cdot 7 &+ (-1) \cdot 12 &+ 1 \cdot 28 \\ &= 0 & + 3 & 1 0 & -7 & - 12 & + 28 \\ &= 12 \\ & = id(12) \end{array}$$
