# Dirichlet Convolution Inverse

If $$\f,g\colon \mathbb{Z}_{\geq 1} \to \mathbb{R}\$$, the Dirichlet convolution of $$\f\$$ and $$\g\$$ is defined by

$$\ \qquad\qquad\qquad \displaystyle (f*g)(n) = \sum_{d|n}f(d)g(n/d).\$$

This question asked about computing Dirchlet convolution of functions. The identity element of the Dirichlet convolution is the function

$$\ \qquad\qquad\qquad\qquad\,\, e(n)=\begin{cases}1 & n=1 \\ 0 & \text{else}\end{cases}\$$.

If $$\f*g=e\$$ then $$\f\$$ and $$\g\$$ are convolutional inverses. If $$\f(1)\neq 0\$$ then $$\f\$$ has a convolutional inverse. There is a formula for the inverse:

$$\\qquad \qquad \qquad \qquad\,\,\,\displaystyle g(1)=\frac{1}{f(1)}\$$

$$\\qquad \qquad \qquad\qquad\,\, \displaystyle g(n)=\frac{-1}{f(1)}\sum_{\substack{d|n\\d1}\$$.

Given a list l of integers, compute the convolution inverse of l. The output should be a list of the same length as l. The list l represents the function

$$\\qquad\qquad\qquad\qquad\,\, f(n) = \begin{cases} \text{The nth entry of l} & n < \text{len(l)} \\ 0 & \text{else} \end{cases}\$$ My test cases are one-indexed because it makes sense in context. If you wish to pad the input and output with an ignored element at the beginning, or make some other modification to support zero indexing, that's fine. Most other i/o formats are probably acceptable. You may assume the output are integers.

## Test Cases

Input:  [1, 0, 0, 0, 0, 0, 0]
Output: [1, 0, 0, 0, 0, 0, 0]

Input:  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Output: [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0]

Input:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
Output: [1, -2, -3, 0, -5, 6, -7, 0, 0, 10, -11, 0, -13, 14, 15, 0]

Input:  [1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5]
Output: [1, -2, -2, 1, -2, 4, -2, 0, 1, 4, -2, -2, -2, 4, 4, 0]

Input:  [1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39]
Output: [1, -3, -4, 2, -6, 12, -8, 0, 3, 18, -12, -8, -14, 24, 24, 0, -18, -9]

Input:  [1, 5, 10, 21, 26, 50, 50, 85, 91, 130]
Output: [1, -5, -10, 4, -26, 50, -50, 0, 9, 130]

Input:  [-1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1]
Output: [-1, -1, 1, -2, 1, 1, 1, -4, 0, 1, 1, 2, 1, 1, -1, -8, 1, 0, 1]

• Using floats introduces precision issues. Could this be rephrased to use only integers? Most examples use only integers anyway. If I got it right, that would only restrict the first value in the input to be 1 Dec 22 '19 at 17:54
• @LuisMendo I don't have a super strong opinion, but I thought it would be nice to include division by f(1). I could add the condition that f(1)=1, or I could just stipulate that I don't care about floating point precision. Perhaps saying f(1)=1 is the best.
– Hood
Dec 22 '19 at 17:57
• I do not want to change your challenge too much. Maybe not being too strict about floating-point precision is enough. The main point for using only integers is that some esolangs can only handle integers Dec 22 '19 at 18:02
• @LuisMendo I appreciate the feedback. I think the way I changed it is fine.
– Hood
Dec 22 '19 at 18:17
• @LuisMendo Thanks, fixed.
– Hood
Dec 22 '19 at 18:36

# MATL, 32 bytes

1i1)/Gd"GX@QtZ\3L)/)y7M)*s_G1)/h


### How it works

1        % Push 1
i        % Take input: f, of size L
1)       % Get its first entry: f(1)
/        % Divide: gives 1/f(1). This is g(1). It will later be expanded into
% a vector to include g(2), g(3), ... g(L)
G        % Push input again
d        % Consecutuve differences: gives a vector of L-1 numbers
"        % For each: this iterates L-1 times
G      %   Push input again
X@Q    %   Push iteration index plus 1: gives 2, 3, ..., L respectively in
%   each iteration. This is n in the formula for computing g(n)
t      %   Duplicate
Z\     %   Divisors of n. Gives a vector with the values of d in the formula
3L)    %   Remove last. This corresponds to the condition d<n in the formula
/      %   Divide. Gives a vector with n/d for d<n
)      %   Index. Gives a vector with f(n/d)
y      %   Duplicate from below. Pushes a copy of g as built so far
7M     %   Push vector containing d for d<n, again
)      %   Index. Gives a vector with g(d)
*      %   Multiply, element-wise. Gives a vector containing f(n/d)*g(d)
s      %   Sum
_      %   Negate
G      %   Push input again
1)     %   Get its first entry: f(1)
/      %   Divide. This gives g(n)
h      %   Contatenate. This attaches the newly computed g(n) to the vector
%   containing the previous values of g
% End (implicit)
% Display (implicit)


# Jelly, 30 29 bytes

ÆD,U$ị"PṖS×Ḣḣ1N;"@ JḊç@ƒİḢ,ƊḢ  Try it online! I’m sure there’s a golfier way of doing this. A pair of links which is called as a monad with the list of integers as the argument. Returns a list of integers. ## Explanation ### Helper link Takes n as its left argument and the current pair of outputs for g and f as its right argument ÆD | Divisors ,U$               | Pair with reversed divisors
ị"             | Index into lists of g and f values respectively
P            | Product of g and f terms
Ṗ           | Remove last item from list
S          | Sum
×         | Multiply by current g and f terms
ḣ1      | First term (i.e. the sum of the product of the specific g and f terms above, multiplied by g(1)), still wrapped in a list
N     | Negate
;"@  | Concatenate to the end of the list of g terms


J           | Sequence along list
Ḋ          | Remove first item
ç@ƒ   Ɗ   | Reduce using helper link with reversed arguments and the following as a monad as the initial argument
İ      | Invert (the initial list of integers)
,    | Pair with initial list of integers
Ḣ  | Head (i.e. final list of g values)


# Charcoal, 33 bytes

ＦＬθ⊞υ∕∨‹ι²±ΣＥυ∧∧λ¬﹪ιλ×§θ÷ιλκ§θ¹Ｉυ


Try it online! Link is to verbose version of code. 0-indexed; on input, the 0th element is a dummy, while on output, it's a duplicate. Explanation:

ＦＬθ


Loop over the indices of the input list.

⊞υ


Save the results as we go.

∕∨...§θ¹


Each term is divided by $$\f(1)\$$.

‹ι²


For the 0th and 1st terms, the numerator is simply 1.

±ΣＥυ∧∧λ¬﹪ιλ×§θ÷ιλκ


Otherwise, multiply the terms computed so far whose index is a factor of the current index with the appropriate term from the input, and take the negated sum.

Ｉυ


Print the results.

Alternative rearrangement, also 33 bytes:

Ｉ⊟Ｅθ⊞Ｏυ∕∨‹κ²±ΣＥυ∧∧μ¬﹪κμ×§θ÷κμλ§θ¹


Try it online! Link is to verbose version of code.

# JavaScript (ES6),  77 76 70  69 bytes

a=>a.map((_,n)=>a[~n]=a.reduce(p=>p-=a[n/++d-1]*a[-d]|0,d=!n++)/a[0])


Try it online!