7
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Luis Mendo Dec 22 '19 at 17:54
  • \$\begingroup\$ @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. \$\endgroup\$ – Hood Dec 22 '19 at 17:57
  • \$\begingroup\$ 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 \$\endgroup\$ – Luis Mendo Dec 22 '19 at 18:02
  • 2
    \$\begingroup\$ @LuisMendo I appreciate the feedback. I think the way I changed it is fine. \$\endgroup\$ – Hood Dec 22 '19 at 18:17
  • \$\begingroup\$ @LuisMendo Thanks, fixed. \$\endgroup\$ – Hood Dec 22 '19 at 18:36
4
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 33 bytes

FLθ⊞υ∕∨‹ι²±ΣEυ∧∧λ¬﹪ιλקθ÷ιλκ§θ¹Iυ

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:

FLθ

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.

±ΣEυ∧∧λ¬﹪ιλקθ÷ιλκ

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.

Iυ

Print the results.

Alternative rearrangement, also 33 bytes:

I⊟Eθ⊞Oυ∕∨‹κ²±ΣEυ∧∧μ¬﹪κμקθ÷κμλ§θ¹

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

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.