Your goal is to implement Möbius inversion, a linear operation on a sequence of numbers that is used in combinatorics and number theory. Fewest bytes wins.
What is Möbius inversion?
Given a (finite) integer sequence f_1, f_2, ..., f_N
, we can compute its divisor-partial-sum g
, whose n
th element g_n
is the sum of all terms f_d
whose index d
is a divisor of n
.
g_n = sum_(d with d|n) [f_d]
g_1 = f_1
g_2 = f_1 + f_2
g_3 = f_1 + f_3
g_4 = f_1 + f_2 + f_ 4
g_5 = f_1 + f_5
g_6 = f_1 + f_2 + f_3 + f_6
...
The sequence g
has the same length as f
.
Möbius inversion is the process of inverting this operation -- recovering f
from g
. This inverse is unique and produces an integer sequence. A explicit but complicated way to compute it is the Möbius inversion formula, which expresses f_n
as a weighted sum over divisors d
of n
:
f_n = sum_(d with d|n) [μ(d) * g_(n/d)]
and μ
is the Möbius function:
μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
μ(n) = 0 if n has a squared prime factor.
Program requirements
Write a function or program to perform Möbius inversion. Fewest bytes wins. Built-in methods to perform Möbius inversion, do sequence convolution, compute the Möbius function (or related thing like checking squarefreeness), or solve systems of equations are not allowed.
Input
A sequence of integers of length at least 1. Can be any format that represents an ordered sequence: array, list, stack, token-separated string, etc. Unordered maps from the index to the element like dictionaries and functions are not OK. You're not given the length of the input sequence separately.
Output
Return or print the output sequence in any format, with same restrictions as input. It should be the same length as the input sequence.
Test cases
Input: [1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6]
Output:[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Input: [0, -3, 6, 5, 1, 7, 5, 0, 4, 0]
Output: [0, -3, 6, 8, 1, 4, 5, -5, -2, 2]
Input: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Output: [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1]
Ax=B
for a matrix is equivalent to solving system of equations only. \$\endgroup\$ – Optimizer Nov 29 '14 at 20:52