Dirichlet Convolution
up vote
19
down vote
favorite
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 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_{ninmathbb N}frac{f(n)}{n^s}right)cdot left(sum_{ninmathbb N}frac{g(n)}{n^s}right) = sum_{ninmathbb 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) = nprod_{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^2cdot 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)
\
&= 0cdot 1 &+ 1cdot 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}$$
code-golf math arithmetic number-theory functional-programming
add a comment |
up vote
19
down vote
favorite
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 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_{ninmathbb N}frac{f(n)}{n^s}right)cdot left(sum_{ninmathbb N}frac{g(n)}{n^s}right) = sum_{ninmathbb 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) = nprod_{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^2cdot 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)
\
&= 0cdot 1 &+ 1cdot 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}$$
code-golf math arithmetic number-theory functional-programming
@ngn oops, I think I originally wanted to add a corresponding example, but you're right, right now it is completely useless.
– flawr
Nov 17 at 19:07
add a comment |
up vote
19
down vote
favorite
up vote
19
down vote
favorite
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 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_{ninmathbb N}frac{f(n)}{n^s}right)cdot left(sum_{ninmathbb N}frac{g(n)}{n^s}right) = sum_{ninmathbb 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) = nprod_{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^2cdot 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)
\
&= 0cdot 1 &+ 1cdot 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}$$
code-golf math arithmetic number-theory functional-programming
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 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_{ninmathbb N}frac{f(n)}{n^s}right)cdot left(sum_{ninmathbb N}frac{g(n)}{n^s}right) = sum_{ninmathbb 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) = nprod_{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^2cdot 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)
\
&= 0cdot 1 &+ 1cdot 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}$$
code-golf math arithmetic number-theory functional-programming
code-golf math arithmetic number-theory functional-programming
edited Nov 17 at 19:34
asked Nov 16 at 19:33
flawr
26.3k662184
26.3k662184
@ngn oops, I think I originally wanted to add a corresponding example, but you're right, right now it is completely useless.
– flawr
Nov 17 at 19:07
add a comment |
@ngn oops, I think I originally wanted to add a corresponding example, but you're right, right now it is completely useless.
– flawr
Nov 17 at 19:07
@ngn oops, I think I originally wanted to add a corresponding example, but you're right, right now it is completely useless.
– flawr
Nov 17 at 19:07
@ngn oops, I think I originally wanted to add a corresponding example, but you're right, right now it is completely useless.
– flawr
Nov 17 at 19:07
add a comment |
13 Answers
13
active
oldest
votes
up vote
4
down vote
Lean, 108 100 95 78 75 bytes
def d(f g:_->int)(n):=(list.iota n).foldr(λd s,ite(n%d=0)(s+f d*g(n/d))s)0
Try it online!
More testcases with all of the functions.
is lambda really more expensive than four bytes forfun
?
– Mario Carneiro
Nov 16 at 21:50
lambda is three bytes, I suppose
– Leaky Nun
Nov 16 at 21:50
I think it's two in UTF8 (greek is pretty low unicode)
– Mario Carneiro
Nov 16 at 21:53
You're right. I also golfed the import
– Leaky Nun
Nov 16 at 21:57
I also usedcond
to save 5 bytes
– Leaky Nun
Nov 16 at 22:00
|
show 9 more comments
up vote
4
down vote
Haskell, 46 bytes
(f!g)n=sum[f i*g(div n i)|i<-[1..n],mod n i<1]
Try it online!
Thanks to flawr for -6 bytes and a great challenge! And thanks to H.PWiz for another -6!
Simpler is shorter here
– H.PWiz
Nov 17 at 3:04
@H.PWiz That's pretty clever - I didn't even think of doing it that way!
– Mego♦
Nov 17 at 4:19
add a comment |
up vote
3
down vote
Python 3, 59 bytes
lambda f,g,n:sum(f(d)*g(n//d)for d in range(1,n+1)if 1>n%d)
Try it online!
Is//
really needed instead of/
?
– Mr. Xcoder
Nov 16 at 20:08
/
would produce floats right?
– Leaky Nun
Nov 16 at 20:09
Becaused
is a divisor ofn
by definition, the fractional part ofn/d
is zero, so there shouldn't be any issues with floating point arithmetic. Floats with fractional part zero are close enough to ints for Pythonic purposes, and the output of the function is a real number, so doingn/d
instead ofn//d
should be fine.
– Mego♦
Nov 17 at 4:28
add a comment |
up vote
3
down vote
Wolfram Language (Mathematica), 17 bytes
Of course Mathematica has a built-in. It also happens to know many of the example functions. I've included some working examples.
DirichletConvolve
Try it online!
add a comment |
up vote
2
down vote
Add++, 51 bytes
D,g,@~,$z€¦~¦*
D,f,@@@,@b[VdF#B]dbRzGb]$dbL$@*z€g¦+
Try it online!
Takes two pre-defined functions as arguments, plus $n$, and outputs $(f * g)(n)$
How it works
D,g, ; Define a helper function, $g
@~, ; $g takes a single argument, an array, and splats that array to the stack
; $g takes the argument e.g. [[τ(x) φ(x)] [3 4]]
; STACK : [[τ(x) φ(x)] [3 4]]
$z ; Swap and zip: [[3 τ(x)] [4 φ(x)]]
€¦~ ; Reduce each by execution: [[τ(3) φ(4)]]
¦* ; Take the product and return: τ(3)⋅φ(4) = 4
D,f, ; Define the main function, $f
@@@, ; $f takes three arguments: φ(x), τ(x) and n (Let n = 12)
; STACK: [φ(x) τ(x) 12]
@ ; Reverse the stack: [12 τ(x) φ(x)]
b[V ; Pair and save: [12] Saved: [τ(x) φ(x)]
dF#B] ; List of factors: [[1 2 3 4 6 12]]
dbR ; Copy and reverse: [[1 2 3 4 6 12] [12 6 4 3 2 1]]
z ; Zip together: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]]]
Gb] ; Push Saved: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)]]]
$dbL ; Number of dividors: [[[τ(x) φ(x)]] [[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] 6]
$@* ; Repeat: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)]]]
z ; Zip: [[[τ(x) φ(x)] [1 12]] [[τ(x) φ(x)] [2 6]] [[τ(x) φ(x)] [3 4]] [[τ(x) φ(x)] [4 3]] [[τ(x) φ(x)] [6 2]] [[τ(x) φ(x)] [12 1]]]
€g ; Run $g over each subarray: [[4 4 4 6 4 6]]
¦+ ; Take the sum and return: 28
add a comment |
up vote
1
down vote
Jelly, 9 bytes
ÆDṚÇ€ḋÑ€Ʋ
Try it online!
Line at the top is the main line of $f$, line at the bottom is the main line of $g$. $n$ is passed as an argument to this function.
add a comment |
up vote
1
down vote
Swift 4, 74 70 54 bytes
{n in(1...n).map{n%$0<1 ?f(n/$0)*g($0):0}.reduce(0,+)}
Try it online!
add a comment |
up vote
1
down vote
R, 58 bytes
function(n,f,g){for(i in (1:n)[!n%%1:n])F=F+f(i)*g(n/i)
F}
Try it online!
Takes n
, f
, and g
. Luckily the numbers
package has quite a few of the functions implemented already.
If vectorized versions were available, which is possible by wrapping each with Vectorize
, then the following 45 byte version is possible:
R, 45 bytes
function(n,f,g,x=1:n,i=x[!n%%x])f(i)%*%g(n/i)
Try it online!
add a comment |
up vote
1
down vote
JavaScript (ES6), 47 bytes
Takes input as (f)(g)(n)
.
f=>g=>h=(n,d=n)=>d&&!(n%d)*f(n/d)*g(d)+h(n,d-1)
Try it online!
Examples
liouville =
n => (-1) ** (D = (n, k = 2) => k > n ? 0 : (n % k ? D(n, k + 1) : 1 + D(n / k, k)))(n)
mobius =
n => (M = (n, k = 1) => n % ++k ? k > n || M(n, k) : n / k % k && -M(n / k, k))(n)
sq =
n => +!((n ** 0.5) % 1)
identity =
n => 1
// sq = liouville * identity
console.log([...Array(25)].map((_, n) => F(liouville)(identity)(n + 1)))
// liouville = mobius * sq
console.log([...Array(20)].map((_, n) => F(mobius)(sq)(n + 1)))
add a comment |
up vote
1
down vote
APL (Dyalog Classic), 20 bytes
{(⍺⍺¨∘⌽+.×⍵⍵¨)∪⍵∨⍳⍵}
with ⎕IO←1
Try it online!
Easy to solve, hard to test - generally not my type of challenge. Yet, I enjoyed this one very much!
{
}
defines a dyadic operator whose operands ⍺⍺
and ⍵⍵
are the two functions being convolved; ⍵
is the numeric argument
∪⍵∨⍳⍵
are the divisors of ⍵
in ascending order, i.e. unique (∪
) of the LCMs (∨
) of ⍵
with all natural numbers up to it (⍳
)
⍵⍵¨
apply the right operand to each
⍺⍺¨∘⌽
apply the left operand to each in reverse
+.×
inner product - multiply corresponding elements and sum
The same in ngn/apl looks better because of Unicode identifiers, but takes 2 additional bytes because of 1-indexing.
Pretty sure it takes 27 additional bytes in ngn/apl...
– Erik the Outgolfer
Nov 17 at 11:42
add a comment |
up vote
1
down vote
C (gcc), 108 bytes
#define F float
F c(F(*f)(int),F(*g)(int),int n){F s=0;for(int d=0;d++<n;)if(n%d<1)s+=f(n/d)*g(d);return s;}
Straightforward implementation, shamelessly stolen from Leaky Nun's Python answer.
Ungolfed:
float c(float (*f)(int), float (*g)(int), int n) {
float s = 0;
for(int d = 1; d <= n;++d) {
if(n % d == 0) {
s += f(n / d) * g(d);
}
}
return s;
}
Try it online!
add a comment |
up vote
1
down vote
F#, 72 bytes
let x f g n=Seq.filter(fun d->n%d=0){1..n}|>Seq.sumBy(fun d->f(n/d)*g d)
Takes the two functions f
and g
and a natural number n
. Filters out the values of d
that do not naturally divide into n
. Then evaluates f(n/d)
and g(d)
, multiples them together, and sums the results.
add a comment |
up vote
0
down vote
Pari/GP, 32 bytes
(f,g,n)->sumdiv(n,d,f(n/d)*g(d))
Try it online!
There is a built-in dirmul
function, but it only supports finite sequences.
add a comment |
13 Answers
13
active
oldest
votes
13 Answers
13
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
Lean, 108 100 95 78 75 bytes
def d(f g:_->int)(n):=(list.iota n).foldr(λd s,ite(n%d=0)(s+f d*g(n/d))s)0
Try it online!
More testcases with all of the functions.
is lambda really more expensive than four bytes forfun
?
– Mario Carneiro
Nov 16 at 21:50
lambda is three bytes, I suppose
– Leaky Nun
Nov 16 at 21:50
I think it's two in UTF8 (greek is pretty low unicode)
– Mario Carneiro
Nov 16 at 21:53
You're right. I also golfed the import
– Leaky Nun
Nov 16 at 21:57
I also usedcond
to save 5 bytes
– Leaky Nun
Nov 16 at 22:00
|
show 9 more comments
up vote
4
down vote
Lean, 108 100 95 78 75 bytes
def d(f g:_->int)(n):=(list.iota n).foldr(λd s,ite(n%d=0)(s+f d*g(n/d))s)0
Try it online!
More testcases with all of the functions.
is lambda really more expensive than four bytes forfun
?
– Mario Carneiro
Nov 16 at 21:50
lambda is three bytes, I suppose
– Leaky Nun
Nov 16 at 21:50
I think it's two in UTF8 (greek is pretty low unicode)
– Mario Carneiro
Nov 16 at 21:53
You're right. I also golfed the import
– Leaky Nun
Nov 16 at 21:57
I also usedcond
to save 5 bytes
– Leaky Nun
Nov 16 at 22:00
|
show 9 more comments
up vote
4
down vote
up vote
4
down vote
Lean, 108 100 95 78 75 bytes
def d(f g:_->int)(n):=(list.iota n).foldr(λd s,ite(n%d=0)(s+f d*g(n/d))s)0
Try it online!
More testcases with all of the functions.
Lean, 108 100 95 78 75 bytes
def d(f g:_->int)(n):=(list.iota n).foldr(λd s,ite(n%d=0)(s+f d*g(n/d))s)0
Try it online!
More testcases with all of the functions.
edited Nov 16 at 22:23
answered Nov 16 at 21:11
Leaky Nun
39.4k484254
39.4k484254
is lambda really more expensive than four bytes forfun
?
– Mario Carneiro
Nov 16 at 21:50
lambda is three bytes, I suppose
– Leaky Nun
Nov 16 at 21:50
I think it's two in UTF8 (greek is pretty low unicode)
– Mario Carneiro
Nov 16 at 21:53
You're right. I also golfed the import
– Leaky Nun
Nov 16 at 21:57
I also usedcond
to save 5 bytes
– Leaky Nun
Nov 16 at 22:00
|
show 9 more comments
is lambda really more expensive than four bytes forfun
?
– Mario Carneiro
Nov 16 at 21:50
lambda is three bytes, I suppose
– Leaky Nun
Nov 16 at 21:50
I think it's two in UTF8 (greek is pretty low unicode)
– Mario Carneiro
Nov 16 at 21:53
You're right. I also golfed the import
– Leaky Nun
Nov 16 at 21:57
I also usedcond
to save 5 bytes
– Leaky Nun
Nov 16 at 22:00
is lambda really more expensive than four bytes for
fun
?– Mario Carneiro
Nov 16 at 21:50
is lambda really more expensive than four bytes for
fun
?– Mario Carneiro
Nov 16 at 21:50
lambda is three bytes, I suppose
– Leaky Nun
Nov 16 at 21:50
lambda is three bytes, I suppose
– Leaky Nun
Nov 16 at 21:50
I think it's two in UTF8 (greek is pretty low unicode)
– Mario Carneiro
Nov 16 at 21:53
I think it's two in UTF8 (greek is pretty low unicode)
– Mario Carneiro
Nov 16 at 21:53
You're right. I also golfed the import
– Leaky Nun
Nov 16 at 21:57
You're right. I also golfed the import
– Leaky Nun
Nov 16 at 21:57
I also used
cond
to save 5 bytes– Leaky Nun
Nov 16 at 22:00
I also used
cond
to save 5 bytes– Leaky Nun
Nov 16 at 22:00
|
show 9 more comments
up vote
4
down vote
Haskell, 46 bytes
(f!g)n=sum[f i*g(div n i)|i<-[1..n],mod n i<1]
Try it online!
Thanks to flawr for -6 bytes and a great challenge! And thanks to H.PWiz for another -6!
Simpler is shorter here
– H.PWiz
Nov 17 at 3:04
@H.PWiz That's pretty clever - I didn't even think of doing it that way!
– Mego♦
Nov 17 at 4:19
add a comment |
up vote
4
down vote
Haskell, 46 bytes
(f!g)n=sum[f i*g(div n i)|i<-[1..n],mod n i<1]
Try it online!
Thanks to flawr for -6 bytes and a great challenge! And thanks to H.PWiz for another -6!
Simpler is shorter here
– H.PWiz
Nov 17 at 3:04
@H.PWiz That's pretty clever - I didn't even think of doing it that way!
– Mego♦
Nov 17 at 4:19
add a comment |
up vote
4
down vote
up vote
4
down vote
Haskell, 46 bytes
(f!g)n=sum[f i*g(div n i)|i<-[1..n],mod n i<1]
Try it online!
Thanks to flawr for -6 bytes and a great challenge! And thanks to H.PWiz for another -6!
Haskell, 46 bytes
(f!g)n=sum[f i*g(div n i)|i<-[1..n],mod n i<1]
Try it online!
Thanks to flawr for -6 bytes and a great challenge! And thanks to H.PWiz for another -6!
edited Nov 17 at 4:19
answered Nov 16 at 21:01
Mego♦
25.8k653186
25.8k653186
Simpler is shorter here
– H.PWiz
Nov 17 at 3:04
@H.PWiz That's pretty clever - I didn't even think of doing it that way!
– Mego♦
Nov 17 at 4:19
add a comment |
Simpler is shorter here
– H.PWiz
Nov 17 at 3:04
@H.PWiz That's pretty clever - I didn't even think of doing it that way!
– Mego♦
Nov 17 at 4:19
Simpler is shorter here
– H.PWiz
Nov 17 at 3:04
Simpler is shorter here
– H.PWiz
Nov 17 at 3:04
@H.PWiz That's pretty clever - I didn't even think of doing it that way!
– Mego♦
Nov 17 at 4:19
@H.PWiz That's pretty clever - I didn't even think of doing it that way!
– Mego♦
Nov 17 at 4:19
add a comment |
up vote
3
down vote
Python 3, 59 bytes
lambda f,g,n:sum(f(d)*g(n//d)for d in range(1,n+1)if 1>n%d)
Try it online!
Is//
really needed instead of/
?
– Mr. Xcoder
Nov 16 at 20:08
/
would produce floats right?
– Leaky Nun
Nov 16 at 20:09
Becaused
is a divisor ofn
by definition, the fractional part ofn/d
is zero, so there shouldn't be any issues with floating point arithmetic. Floats with fractional part zero are close enough to ints for Pythonic purposes, and the output of the function is a real number, so doingn/d
instead ofn//d
should be fine.
– Mego♦
Nov 17 at 4:28
add a comment |
up vote
3
down vote
Python 3, 59 bytes
lambda f,g,n:sum(f(d)*g(n//d)for d in range(1,n+1)if 1>n%d)
Try it online!
Is//
really needed instead of/
?
– Mr. Xcoder
Nov 16 at 20:08
/
would produce floats right?
– Leaky Nun
Nov 16 at 20:09
Becaused
is a divisor ofn
by definition, the fractional part ofn/d
is zero, so there shouldn't be any issues with floating point arithmetic. Floats with fractional part zero are close enough to ints for Pythonic purposes, and the output of the function is a real number, so doingn/d
instead ofn//d
should be fine.
– Mego♦
Nov 17 at 4:28
add a comment |
up vote
3
down vote
up vote
3
down vote
Python 3, 59 bytes
lambda f,g,n:sum(f(d)*g(n//d)for d in range(1,n+1)if 1>n%d)
Try it online!
Python 3, 59 bytes
lambda f,g,n:sum(f(d)*g(n//d)for d in range(1,n+1)if 1>n%d)
Try it online!
answered Nov 16 at 20:02
Leaky Nun
39.4k484254
39.4k484254
Is//
really needed instead of/
?
– Mr. Xcoder
Nov 16 at 20:08
/
would produce floats right?
– Leaky Nun
Nov 16 at 20:09
Becaused
is a divisor ofn
by definition, the fractional part ofn/d
is zero, so there shouldn't be any issues with floating point arithmetic. Floats with fractional part zero are close enough to ints for Pythonic purposes, and the output of the function is a real number, so doingn/d
instead ofn//d
should be fine.
– Mego♦
Nov 17 at 4:28
add a comment |
Is//
really needed instead of/
?
– Mr. Xcoder
Nov 16 at 20:08
/
would produce floats right?
– Leaky Nun
Nov 16 at 20:09
Becaused
is a divisor ofn
by definition, the fractional part ofn/d
is zero, so there shouldn't be any issues with floating point arithmetic. Floats with fractional part zero are close enough to ints for Pythonic purposes, and the output of the function is a real number, so doingn/d
instead ofn//d
should be fine.
– Mego♦
Nov 17 at 4:28
Is
//
really needed instead of /
?– Mr. Xcoder
Nov 16 at 20:08
Is
//
really needed instead of /
?– Mr. Xcoder
Nov 16 at 20:08
/
would produce floats right?– Leaky Nun
Nov 16 at 20:09
/
would produce floats right?– Leaky Nun
Nov 16 at 20:09
Because
d
is a divisor of n
by definition, the fractional part of n/d
is zero, so there shouldn't be any issues with floating point arithmetic. Floats with fractional part zero are close enough to ints for Pythonic purposes, and the output of the function is a real number, so doing n/d
instead of n//d
should be fine.– Mego♦
Nov 17 at 4:28
Because
d
is a divisor of n
by definition, the fractional part of n/d
is zero, so there shouldn't be any issues with floating point arithmetic. Floats with fractional part zero are close enough to ints for Pythonic purposes, and the output of the function is a real number, so doing n/d
instead of n//d
should be fine.– Mego♦
Nov 17 at 4:28
add a comment |
up vote
3
down vote
Wolfram Language (Mathematica), 17 bytes
Of course Mathematica has a built-in. It also happens to know many of the example functions. I've included some working examples.
DirichletConvolve
Try it online!
add a comment |
up vote
3
down vote
Wolfram Language (Mathematica), 17 bytes
Of course Mathematica has a built-in. It also happens to know many of the example functions. I've included some working examples.
DirichletConvolve
Try it online!
add a comment |
up vote
3
down vote
up vote
3
down vote
Wolfram Language (Mathematica), 17 bytes
Of course Mathematica has a built-in. It also happens to know many of the example functions. I've included some working examples.
DirichletConvolve
Try it online!
Wolfram Language (Mathematica), 17 bytes
Of course Mathematica has a built-in. It also happens to know many of the example functions. I've included some working examples.
DirichletConvolve
Try it online!
answered Nov 16 at 21:12
Kelly Lowder
2,968416
2,968416
add a comment |
add a comment |
up vote
2
down vote
Add++, 51 bytes
D,g,@~,$z€¦~¦*
D,f,@@@,@b[VdF#B]dbRzGb]$dbL$@*z€g¦+
Try it online!
Takes two pre-defined functions as arguments, plus $n$, and outputs $(f * g)(n)$
How it works
D,g, ; Define a helper function, $g
@~, ; $g takes a single argument, an array, and splats that array to the stack
; $g takes the argument e.g. [[τ(x) φ(x)] [3 4]]
; STACK : [[τ(x) φ(x)] [3 4]]
$z ; Swap and zip: [[3 τ(x)] [4 φ(x)]]
€¦~ ; Reduce each by execution: [[τ(3) φ(4)]]
¦* ; Take the product and return: τ(3)⋅φ(4) = 4
D,f, ; Define the main function, $f
@@@, ; $f takes three arguments: φ(x), τ(x) and n (Let n = 12)
; STACK: [φ(x) τ(x) 12]
@ ; Reverse the stack: [12 τ(x) φ(x)]
b[V ; Pair and save: [12] Saved: [τ(x) φ(x)]
dF#B] ; List of factors: [[1 2 3 4 6 12]]
dbR ; Copy and reverse: [[1 2 3 4 6 12] [12 6 4 3 2 1]]
z ; Zip together: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]]]
Gb] ; Push Saved: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)]]]
$dbL ; Number of dividors: [[[τ(x) φ(x)]] [[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] 6]
$@* ; Repeat: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)]]]
z ; Zip: [[[τ(x) φ(x)] [1 12]] [[τ(x) φ(x)] [2 6]] [[τ(x) φ(x)] [3 4]] [[τ(x) φ(x)] [4 3]] [[τ(x) φ(x)] [6 2]] [[τ(x) φ(x)] [12 1]]]
€g ; Run $g over each subarray: [[4 4 4 6 4 6]]
¦+ ; Take the sum and return: 28
add a comment |
up vote
2
down vote
Add++, 51 bytes
D,g,@~,$z€¦~¦*
D,f,@@@,@b[VdF#B]dbRzGb]$dbL$@*z€g¦+
Try it online!
Takes two pre-defined functions as arguments, plus $n$, and outputs $(f * g)(n)$
How it works
D,g, ; Define a helper function, $g
@~, ; $g takes a single argument, an array, and splats that array to the stack
; $g takes the argument e.g. [[τ(x) φ(x)] [3 4]]
; STACK : [[τ(x) φ(x)] [3 4]]
$z ; Swap and zip: [[3 τ(x)] [4 φ(x)]]
€¦~ ; Reduce each by execution: [[τ(3) φ(4)]]
¦* ; Take the product and return: τ(3)⋅φ(4) = 4
D,f, ; Define the main function, $f
@@@, ; $f takes three arguments: φ(x), τ(x) and n (Let n = 12)
; STACK: [φ(x) τ(x) 12]
@ ; Reverse the stack: [12 τ(x) φ(x)]
b[V ; Pair and save: [12] Saved: [τ(x) φ(x)]
dF#B] ; List of factors: [[1 2 3 4 6 12]]
dbR ; Copy and reverse: [[1 2 3 4 6 12] [12 6 4 3 2 1]]
z ; Zip together: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]]]
Gb] ; Push Saved: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)]]]
$dbL ; Number of dividors: [[[τ(x) φ(x)]] [[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] 6]
$@* ; Repeat: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)]]]
z ; Zip: [[[τ(x) φ(x)] [1 12]] [[τ(x) φ(x)] [2 6]] [[τ(x) φ(x)] [3 4]] [[τ(x) φ(x)] [4 3]] [[τ(x) φ(x)] [6 2]] [[τ(x) φ(x)] [12 1]]]
€g ; Run $g over each subarray: [[4 4 4 6 4 6]]
¦+ ; Take the sum and return: 28
add a comment |
up vote
2
down vote
up vote
2
down vote
Add++, 51 bytes
D,g,@~,$z€¦~¦*
D,f,@@@,@b[VdF#B]dbRzGb]$dbL$@*z€g¦+
Try it online!
Takes two pre-defined functions as arguments, plus $n$, and outputs $(f * g)(n)$
How it works
D,g, ; Define a helper function, $g
@~, ; $g takes a single argument, an array, and splats that array to the stack
; $g takes the argument e.g. [[τ(x) φ(x)] [3 4]]
; STACK : [[τ(x) φ(x)] [3 4]]
$z ; Swap and zip: [[3 τ(x)] [4 φ(x)]]
€¦~ ; Reduce each by execution: [[τ(3) φ(4)]]
¦* ; Take the product and return: τ(3)⋅φ(4) = 4
D,f, ; Define the main function, $f
@@@, ; $f takes three arguments: φ(x), τ(x) and n (Let n = 12)
; STACK: [φ(x) τ(x) 12]
@ ; Reverse the stack: [12 τ(x) φ(x)]
b[V ; Pair and save: [12] Saved: [τ(x) φ(x)]
dF#B] ; List of factors: [[1 2 3 4 6 12]]
dbR ; Copy and reverse: [[1 2 3 4 6 12] [12 6 4 3 2 1]]
z ; Zip together: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]]]
Gb] ; Push Saved: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)]]]
$dbL ; Number of dividors: [[[τ(x) φ(x)]] [[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] 6]
$@* ; Repeat: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)]]]
z ; Zip: [[[τ(x) φ(x)] [1 12]] [[τ(x) φ(x)] [2 6]] [[τ(x) φ(x)] [3 4]] [[τ(x) φ(x)] [4 3]] [[τ(x) φ(x)] [6 2]] [[τ(x) φ(x)] [12 1]]]
€g ; Run $g over each subarray: [[4 4 4 6 4 6]]
¦+ ; Take the sum and return: 28
Add++, 51 bytes
D,g,@~,$z€¦~¦*
D,f,@@@,@b[VdF#B]dbRzGb]$dbL$@*z€g¦+
Try it online!
Takes two pre-defined functions as arguments, plus $n$, and outputs $(f * g)(n)$
How it works
D,g, ; Define a helper function, $g
@~, ; $g takes a single argument, an array, and splats that array to the stack
; $g takes the argument e.g. [[τ(x) φ(x)] [3 4]]
; STACK : [[τ(x) φ(x)] [3 4]]
$z ; Swap and zip: [[3 τ(x)] [4 φ(x)]]
€¦~ ; Reduce each by execution: [[τ(3) φ(4)]]
¦* ; Take the product and return: τ(3)⋅φ(4) = 4
D,f, ; Define the main function, $f
@@@, ; $f takes three arguments: φ(x), τ(x) and n (Let n = 12)
; STACK: [φ(x) τ(x) 12]
@ ; Reverse the stack: [12 τ(x) φ(x)]
b[V ; Pair and save: [12] Saved: [τ(x) φ(x)]
dF#B] ; List of factors: [[1 2 3 4 6 12]]
dbR ; Copy and reverse: [[1 2 3 4 6 12] [12 6 4 3 2 1]]
z ; Zip together: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]]]
Gb] ; Push Saved: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)]]]
$dbL ; Number of dividors: [[[τ(x) φ(x)]] [[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] 6]
$@* ; Repeat: [[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)]]]
z ; Zip: [[[τ(x) φ(x)] [1 12]] [[τ(x) φ(x)] [2 6]] [[τ(x) φ(x)] [3 4]] [[τ(x) φ(x)] [4 3]] [[τ(x) φ(x)] [6 2]] [[τ(x) φ(x)] [12 1]]]
€g ; Run $g over each subarray: [[4 4 4 6 4 6]]
¦+ ; Take the sum and return: 28
edited Nov 16 at 21:05
answered Nov 16 at 20:48
caird coinheringaahing
7,49632985
7,49632985
add a comment |
add a comment |
up vote
1
down vote
Jelly, 9 bytes
ÆDṚÇ€ḋÑ€Ʋ
Try it online!
Line at the top is the main line of $f$, line at the bottom is the main line of $g$. $n$ is passed as an argument to this function.
add a comment |
up vote
1
down vote
Jelly, 9 bytes
ÆDṚÇ€ḋÑ€Ʋ
Try it online!
Line at the top is the main line of $f$, line at the bottom is the main line of $g$. $n$ is passed as an argument to this function.
add a comment |
up vote
1
down vote
up vote
1
down vote
Jelly, 9 bytes
ÆDṚÇ€ḋÑ€Ʋ
Try it online!
Line at the top is the main line of $f$, line at the bottom is the main line of $g$. $n$ is passed as an argument to this function.
Jelly, 9 bytes
ÆDṚÇ€ḋÑ€Ʋ
Try it online!
Line at the top is the main line of $f$, line at the bottom is the main line of $g$. $n$ is passed as an argument to this function.
answered Nov 16 at 20:05
Erik the Outgolfer
30.8k429102
30.8k429102
add a comment |
add a comment |
up vote
1
down vote
Swift 4, 74 70 54 bytes
{n in(1...n).map{n%$0<1 ?f(n/$0)*g($0):0}.reduce(0,+)}
Try it online!
add a comment |
up vote
1
down vote
Swift 4, 74 70 54 bytes
{n in(1...n).map{n%$0<1 ?f(n/$0)*g($0):0}.reduce(0,+)}
Try it online!
add a comment |
up vote
1
down vote
up vote
1
down vote
Swift 4, 74 70 54 bytes
{n in(1...n).map{n%$0<1 ?f(n/$0)*g($0):0}.reduce(0,+)}
Try it online!
Swift 4, 74 70 54 bytes
{n in(1...n).map{n%$0<1 ?f(n/$0)*g($0):0}.reduce(0,+)}
Try it online!
edited Nov 16 at 20:34
answered Nov 16 at 20:25
Mr. Xcoder
31.3k759197
31.3k759197
add a comment |
add a comment |
up vote
1
down vote
R, 58 bytes
function(n,f,g){for(i in (1:n)[!n%%1:n])F=F+f(i)*g(n/i)
F}
Try it online!
Takes n
, f
, and g
. Luckily the numbers
package has quite a few of the functions implemented already.
If vectorized versions were available, which is possible by wrapping each with Vectorize
, then the following 45 byte version is possible:
R, 45 bytes
function(n,f,g,x=1:n,i=x[!n%%x])f(i)%*%g(n/i)
Try it online!
add a comment |
up vote
1
down vote
R, 58 bytes
function(n,f,g){for(i in (1:n)[!n%%1:n])F=F+f(i)*g(n/i)
F}
Try it online!
Takes n
, f
, and g
. Luckily the numbers
package has quite a few of the functions implemented already.
If vectorized versions were available, which is possible by wrapping each with Vectorize
, then the following 45 byte version is possible:
R, 45 bytes
function(n,f,g,x=1:n,i=x[!n%%x])f(i)%*%g(n/i)
Try it online!
add a comment |
up vote
1
down vote
up vote
1
down vote
R, 58 bytes
function(n,f,g){for(i in (1:n)[!n%%1:n])F=F+f(i)*g(n/i)
F}
Try it online!
Takes n
, f
, and g
. Luckily the numbers
package has quite a few of the functions implemented already.
If vectorized versions were available, which is possible by wrapping each with Vectorize
, then the following 45 byte version is possible:
R, 45 bytes
function(n,f,g,x=1:n,i=x[!n%%x])f(i)%*%g(n/i)
Try it online!
R, 58 bytes
function(n,f,g){for(i in (1:n)[!n%%1:n])F=F+f(i)*g(n/i)
F}
Try it online!
Takes n
, f
, and g
. Luckily the numbers
package has quite a few of the functions implemented already.
If vectorized versions were available, which is possible by wrapping each with Vectorize
, then the following 45 byte version is possible:
R, 45 bytes
function(n,f,g,x=1:n,i=x[!n%%x])f(i)%*%g(n/i)
Try it online!
answered Nov 16 at 21:54
Giuseppe
16.1k31052
16.1k31052
add a comment |
add a comment |
up vote
1
down vote
JavaScript (ES6), 47 bytes
Takes input as (f)(g)(n)
.
f=>g=>h=(n,d=n)=>d&&!(n%d)*f(n/d)*g(d)+h(n,d-1)
Try it online!
Examples
liouville =
n => (-1) ** (D = (n, k = 2) => k > n ? 0 : (n % k ? D(n, k + 1) : 1 + D(n / k, k)))(n)
mobius =
n => (M = (n, k = 1) => n % ++k ? k > n || M(n, k) : n / k % k && -M(n / k, k))(n)
sq =
n => +!((n ** 0.5) % 1)
identity =
n => 1
// sq = liouville * identity
console.log([...Array(25)].map((_, n) => F(liouville)(identity)(n + 1)))
// liouville = mobius * sq
console.log([...Array(20)].map((_, n) => F(mobius)(sq)(n + 1)))
add a comment |
up vote
1
down vote
JavaScript (ES6), 47 bytes
Takes input as (f)(g)(n)
.
f=>g=>h=(n,d=n)=>d&&!(n%d)*f(n/d)*g(d)+h(n,d-1)
Try it online!
Examples
liouville =
n => (-1) ** (D = (n, k = 2) => k > n ? 0 : (n % k ? D(n, k + 1) : 1 + D(n / k, k)))(n)
mobius =
n => (M = (n, k = 1) => n % ++k ? k > n || M(n, k) : n / k % k && -M(n / k, k))(n)
sq =
n => +!((n ** 0.5) % 1)
identity =
n => 1
// sq = liouville * identity
console.log([...Array(25)].map((_, n) => F(liouville)(identity)(n + 1)))
// liouville = mobius * sq
console.log([...Array(20)].map((_, n) => F(mobius)(sq)(n + 1)))
add a comment |
up vote
1
down vote
up vote
1
down vote
JavaScript (ES6), 47 bytes
Takes input as (f)(g)(n)
.
f=>g=>h=(n,d=n)=>d&&!(n%d)*f(n/d)*g(d)+h(n,d-1)
Try it online!
Examples
liouville =
n => (-1) ** (D = (n, k = 2) => k > n ? 0 : (n % k ? D(n, k + 1) : 1 + D(n / k, k)))(n)
mobius =
n => (M = (n, k = 1) => n % ++k ? k > n || M(n, k) : n / k % k && -M(n / k, k))(n)
sq =
n => +!((n ** 0.5) % 1)
identity =
n => 1
// sq = liouville * identity
console.log([...Array(25)].map((_, n) => F(liouville)(identity)(n + 1)))
// liouville = mobius * sq
console.log([...Array(20)].map((_, n) => F(mobius)(sq)(n + 1)))
JavaScript (ES6), 47 bytes
Takes input as (f)(g)(n)
.
f=>g=>h=(n,d=n)=>d&&!(n%d)*f(n/d)*g(d)+h(n,d-1)
Try it online!
Examples
liouville =
n => (-1) ** (D = (n, k = 2) => k > n ? 0 : (n % k ? D(n, k + 1) : 1 + D(n / k, k)))(n)
mobius =
n => (M = (n, k = 1) => n % ++k ? k > n || M(n, k) : n / k % k && -M(n / k, k))(n)
sq =
n => +!((n ** 0.5) % 1)
identity =
n => 1
// sq = liouville * identity
console.log([...Array(25)].map((_, n) => F(liouville)(identity)(n + 1)))
// liouville = mobius * sq
console.log([...Array(20)].map((_, n) => F(mobius)(sq)(n + 1)))
edited Nov 17 at 1:11
answered Nov 17 at 1:01
Arnauld
70.1k686295
70.1k686295
add a comment |
add a comment |
up vote
1
down vote
APL (Dyalog Classic), 20 bytes
{(⍺⍺¨∘⌽+.×⍵⍵¨)∪⍵∨⍳⍵}
with ⎕IO←1
Try it online!
Easy to solve, hard to test - generally not my type of challenge. Yet, I enjoyed this one very much!
{
}
defines a dyadic operator whose operands ⍺⍺
and ⍵⍵
are the two functions being convolved; ⍵
is the numeric argument
∪⍵∨⍳⍵
are the divisors of ⍵
in ascending order, i.e. unique (∪
) of the LCMs (∨
) of ⍵
with all natural numbers up to it (⍳
)
⍵⍵¨
apply the right operand to each
⍺⍺¨∘⌽
apply the left operand to each in reverse
+.×
inner product - multiply corresponding elements and sum
The same in ngn/apl looks better because of Unicode identifiers, but takes 2 additional bytes because of 1-indexing.
Pretty sure it takes 27 additional bytes in ngn/apl...
– Erik the Outgolfer
Nov 17 at 11:42
add a comment |
up vote
1
down vote
APL (Dyalog Classic), 20 bytes
{(⍺⍺¨∘⌽+.×⍵⍵¨)∪⍵∨⍳⍵}
with ⎕IO←1
Try it online!
Easy to solve, hard to test - generally not my type of challenge. Yet, I enjoyed this one very much!
{
}
defines a dyadic operator whose operands ⍺⍺
and ⍵⍵
are the two functions being convolved; ⍵
is the numeric argument
∪⍵∨⍳⍵
are the divisors of ⍵
in ascending order, i.e. unique (∪
) of the LCMs (∨
) of ⍵
with all natural numbers up to it (⍳
)
⍵⍵¨
apply the right operand to each
⍺⍺¨∘⌽
apply the left operand to each in reverse
+.×
inner product - multiply corresponding elements and sum
The same in ngn/apl looks better because of Unicode identifiers, but takes 2 additional bytes because of 1-indexing.
Pretty sure it takes 27 additional bytes in ngn/apl...
– Erik the Outgolfer
Nov 17 at 11:42
add a comment |
up vote
1
down vote
up vote
1
down vote
APL (Dyalog Classic), 20 bytes
{(⍺⍺¨∘⌽+.×⍵⍵¨)∪⍵∨⍳⍵}
with ⎕IO←1
Try it online!
Easy to solve, hard to test - generally not my type of challenge. Yet, I enjoyed this one very much!
{
}
defines a dyadic operator whose operands ⍺⍺
and ⍵⍵
are the two functions being convolved; ⍵
is the numeric argument
∪⍵∨⍳⍵
are the divisors of ⍵
in ascending order, i.e. unique (∪
) of the LCMs (∨
) of ⍵
with all natural numbers up to it (⍳
)
⍵⍵¨
apply the right operand to each
⍺⍺¨∘⌽
apply the left operand to each in reverse
+.×
inner product - multiply corresponding elements and sum
The same in ngn/apl looks better because of Unicode identifiers, but takes 2 additional bytes because of 1-indexing.
APL (Dyalog Classic), 20 bytes
{(⍺⍺¨∘⌽+.×⍵⍵¨)∪⍵∨⍳⍵}
with ⎕IO←1
Try it online!
Easy to solve, hard to test - generally not my type of challenge. Yet, I enjoyed this one very much!
{
}
defines a dyadic operator whose operands ⍺⍺
and ⍵⍵
are the two functions being convolved; ⍵
is the numeric argument
∪⍵∨⍳⍵
are the divisors of ⍵
in ascending order, i.e. unique (∪
) of the LCMs (∨
) of ⍵
with all natural numbers up to it (⍳
)
⍵⍵¨
apply the right operand to each
⍺⍺¨∘⌽
apply the left operand to each in reverse
+.×
inner product - multiply corresponding elements and sum
The same in ngn/apl looks better because of Unicode identifiers, but takes 2 additional bytes because of 1-indexing.
edited Nov 17 at 8:08
answered Nov 17 at 6:49
ngn
6,51312459
6,51312459
Pretty sure it takes 27 additional bytes in ngn/apl...
– Erik the Outgolfer
Nov 17 at 11:42
add a comment |
Pretty sure it takes 27 additional bytes in ngn/apl...
– Erik the Outgolfer
Nov 17 at 11:42
Pretty sure it takes 27 additional bytes in ngn/apl...
– Erik the Outgolfer
Nov 17 at 11:42
Pretty sure it takes 27 additional bytes in ngn/apl...
– Erik the Outgolfer
Nov 17 at 11:42
add a comment |
up vote
1
down vote
C (gcc), 108 bytes
#define F float
F c(F(*f)(int),F(*g)(int),int n){F s=0;for(int d=0;d++<n;)if(n%d<1)s+=f(n/d)*g(d);return s;}
Straightforward implementation, shamelessly stolen from Leaky Nun's Python answer.
Ungolfed:
float c(float (*f)(int), float (*g)(int), int n) {
float s = 0;
for(int d = 1; d <= n;++d) {
if(n % d == 0) {
s += f(n / d) * g(d);
}
}
return s;
}
Try it online!
add a comment |
up vote
1
down vote
C (gcc), 108 bytes
#define F float
F c(F(*f)(int),F(*g)(int),int n){F s=0;for(int d=0;d++<n;)if(n%d<1)s+=f(n/d)*g(d);return s;}
Straightforward implementation, shamelessly stolen from Leaky Nun's Python answer.
Ungolfed:
float c(float (*f)(int), float (*g)(int), int n) {
float s = 0;
for(int d = 1; d <= n;++d) {
if(n % d == 0) {
s += f(n / d) * g(d);
}
}
return s;
}
Try it online!
add a comment |
up vote
1
down vote
up vote
1
down vote
C (gcc), 108 bytes
#define F float
F c(F(*f)(int),F(*g)(int),int n){F s=0;for(int d=0;d++<n;)if(n%d<1)s+=f(n/d)*g(d);return s;}
Straightforward implementation, shamelessly stolen from Leaky Nun's Python answer.
Ungolfed:
float c(float (*f)(int), float (*g)(int), int n) {
float s = 0;
for(int d = 1; d <= n;++d) {
if(n % d == 0) {
s += f(n / d) * g(d);
}
}
return s;
}
Try it online!
C (gcc), 108 bytes
#define F float
F c(F(*f)(int),F(*g)(int),int n){F s=0;for(int d=0;d++<n;)if(n%d<1)s+=f(n/d)*g(d);return s;}
Straightforward implementation, shamelessly stolen from Leaky Nun's Python answer.
Ungolfed:
float c(float (*f)(int), float (*g)(int), int n) {
float s = 0;
for(int d = 1; d <= n;++d) {
if(n % d == 0) {
s += f(n / d) * g(d);
}
}
return s;
}
Try it online!
answered Nov 17 at 11:45
joH1
306211
306211
add a comment |
add a comment |
up vote
1
down vote
F#, 72 bytes
let x f g n=Seq.filter(fun d->n%d=0){1..n}|>Seq.sumBy(fun d->f(n/d)*g d)
Takes the two functions f
and g
and a natural number n
. Filters out the values of d
that do not naturally divide into n
. Then evaluates f(n/d)
and g(d)
, multiples them together, and sums the results.
add a comment |
up vote
1
down vote
F#, 72 bytes
let x f g n=Seq.filter(fun d->n%d=0){1..n}|>Seq.sumBy(fun d->f(n/d)*g d)
Takes the two functions f
and g
and a natural number n
. Filters out the values of d
that do not naturally divide into n
. Then evaluates f(n/d)
and g(d)
, multiples them together, and sums the results.
add a comment |
up vote
1
down vote
up vote
1
down vote
F#, 72 bytes
let x f g n=Seq.filter(fun d->n%d=0){1..n}|>Seq.sumBy(fun d->f(n/d)*g d)
Takes the two functions f
and g
and a natural number n
. Filters out the values of d
that do not naturally divide into n
. Then evaluates f(n/d)
and g(d)
, multiples them together, and sums the results.
F#, 72 bytes
let x f g n=Seq.filter(fun d->n%d=0){1..n}|>Seq.sumBy(fun d->f(n/d)*g d)
Takes the two functions f
and g
and a natural number n
. Filters out the values of d
that do not naturally divide into n
. Then evaluates f(n/d)
and g(d)
, multiples them together, and sums the results.
answered Nov 17 at 14:47
Ciaran_McCarthy
481118
481118
add a comment |
add a comment |
up vote
0
down vote
Pari/GP, 32 bytes
(f,g,n)->sumdiv(n,d,f(n/d)*g(d))
Try it online!
There is a built-in dirmul
function, but it only supports finite sequences.
add a comment |
up vote
0
down vote
Pari/GP, 32 bytes
(f,g,n)->sumdiv(n,d,f(n/d)*g(d))
Try it online!
There is a built-in dirmul
function, but it only supports finite sequences.
add a comment |
up vote
0
down vote
up vote
0
down vote
Pari/GP, 32 bytes
(f,g,n)->sumdiv(n,d,f(n/d)*g(d))
Try it online!
There is a built-in dirmul
function, but it only supports finite sequences.
Pari/GP, 32 bytes
(f,g,n)->sumdiv(n,d,f(n/d)*g(d))
Try it online!
There is a built-in dirmul
function, but it only supports finite sequences.
edited Nov 18 at 5:13
answered Nov 17 at 12:58
alephalpha
21k32888
21k32888
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f176100%2fdirichlet-convolution%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
@ngn oops, I think I originally wanted to add a corresponding example, but you're right, right now it is completely useless.
– flawr
Nov 17 at 19:07