Dirichlet卷积

Question

Dirichlet卷积是一种特殊的卷积，它是数论中一个非常有用的工具。它在一组算术函数上运行。

挑战

给出了两个算术函数f,g (即函数f,g: \mathbb N \to \mathbb R)计算Dirichlet卷积(f * g): \mathbb N \to \mathbb R的定义。

详细信息

• 我们使用约定0 \notin \mathbb N = \{1,2,3,\ldots \}。
• 两个算术函数f*g的Dirichlet卷积f,g又是一个算术函数，定义为(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). (这两个和都是等价的)。表达式d|n的意思是d \in \mathbb N除以n，因此求和是n的自然除法。同样，我们可以将i = \frac{n}{d} \in \mathbb N, j =d \in \mathbb N 代入，得到第二个等价的公式。如果您不习惯这种表示法，下面有一个逐步的例子。)只是详细说明一下(这与这一挑战没有直接关系)：定义来自计算Dirichlet级数：\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}的产品
• 输入作为两个黑箱函数给出。或者，您也可以使用无限列表、生成器、流或类似的东西来生成无限数量的值。
• 有两个输出方法:一个函数f*g被返回，或者您也可以接受一个附加的输入n \in \mathbb N并直接返回(f*g)(n)。
• 为了简单起见，您可以假设\mathbb N的每个元素都可以用正32位int表示。
• 为了简单起见，您还可以假设每个条目\mathbb R 都可以用一个真正的浮点数来表示。

示例

让我们首先定义几个函数。请注意，每个定义下面的数字列表表示该函数的前几个值。

• 乘法恒等式(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, ...
• 常单位函数(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, ...
• 恒等函数(A000027) id(n) = n \: \forall n 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...
• M bius函数(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, ...
• 欧拉函数(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, ...
• Liouville函数(A008836) \lambda (n) = (-1)^k ，其中k是用多重1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1, ...计数的n的素数
• 除数和函数(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, ...
• 除数计数函数(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, ...
• 平方数(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, ...的特征函数

然后，我们有以下例子：

\epsilon = \mathbb 1 * \mu

f = \epsilon * f \: \forall f

\epsilon = \lambda * \vert \mu \vert

\sigma = \varphi * \tau

• id = \sigma * \mu和\sigma = id * \mathbb 1
• sq = \lambda * \mathbb 1 和\lambda = \mu * sq
• \tau = \mathbb 1 * \mathbb 1和\mathbb 1 = \tau * \mu
• id = \varphi * \mathbb 1 和\varphi = id * \mu

最后一个for是M bius反演的结果:对于任何f,g，方程g = f * 1等价于f = g * \mu 。

一步一步示例

对于那些不熟悉定义中使用的表示法的人来说，这是一个逐步计算的示例。考虑一下函数f = \mu和g = \sigma。我们现在将评估他们的卷积\mu * \sigma在n=12。他们的前几个术语列于下表。

\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}

和迭代到除以d \in \mathbb N的所有自然数n=12，因此d假定n=12 = 2^2\cdot 3的所有自然除数。这些是d =1,2,3,4,6,12。在每个求和中，我们在d计算g= \sigma，并将它与在\frac{n}{d}计算的f = \mu相乘。现在我们可以得出结论

\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}

Answer 1

Wolfram语言(数学)，17字节

当然，Mathematica有一个内置的。它还碰巧知道许多示例函数。我列举了一些有用的例子。

DirichletConvolve

在网上试试！

Answer 2

Python 3，59字节

lambda f,g,n:sum(f(d)*g(n//d)for d in range(1,n+1)if 1>n%d)

在网上试试！

Answer 3

R，58字节

function(n,f,g){for(i in (1:n)[!n%%1:n])F=F+f(i)*g(n/i)
F}

在网上试试！

比如n，f和g。幸运的是，numbers包已经实现了许多功能。

如果可用矢量化版本(可以通过用Vectorize包装每个版本)，那么以下45字节版本是可能的：

R，45字节

function(n,f,g,x=1:n,i=x[!n%%x])f(i)%*%g(n/i)

在网上试试！