Cfrgtkky

up vote 19 down vote favorite 3 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} fleft(frac{n}{d}right)cdot g(d) = sum_{icdot 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