Dirichlet Convolution Inverse

Question

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\\d<n}} f(n/d)g(d) \qquad \text{for $n>1$}\$.

Task:

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 $n$th 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]

Answer 1

MATL, 32 bytes

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

Try it online! Or verify all test cases.

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)

Answer 2

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
           Ḣ        | Head
            ḣ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

Main link

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)
      Ḣ     | Head
       ,    | Pair with initial list of integers
         Ḣ  | Head (i.e. final list of g values)

Answer 3

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.

Answer 4

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!