Möbius Inversion of Divisor Sums
Recover f(1)…f(N) from F(n)=Σ(d|n)f(d) by exact triangular divisor-sum inversion; prefixes start at one and are capped at 1,000 entries.
Description
Möbius inversion recovers an arithmetic function from its divisor sums.
Möbius inversion recovers an arithmetic function from its divisor sums. A complete prefix makes the divisor relation triangular, so smaller recovered values can be subtracted from later multiples.1
The tool returns values. The indexing and output conventions below determine how to read these values.
When to use Möbius Inversion of Divisor Sums
Use this for the following task: Recover f(1)…f(N) from F(n)=Σ(d|n)f(d) by exact triangular divisor-sum inversion; prefixes start at one and are capped at 1,000 entries. Use the input and output conventions below to reproduce the intended mathematical quantity.
How to use Möbius Inversion of Divisor Sums and understand its results
- Choose the required indexes, integers or sequence entries. Preserve decimal-string encodings where the field table specifies strings.
- Enter divisorSums according to the field table, then run the tool.
- Read values. Preserve exact decimal strings and the stated indexing or coefficient order.
- Keep exact decimal strings for subsequent integer arithmetic; distinguish them from any explicitly approximate numeric result.
| Input field | Meaning | Value type and bounds | Requirement |
|---|---|---|---|
| divisorSums | Divisor sums F(1) through F(N) | list of string (integer/arbitrary); minimum entries 0; maximum entries 1000; each entry: maximum text length 200; pattern ^-?(0|[1-9][0-9]*)$ | Required |
Parse the signed decimal list as BigInt values. Process divisors upward, subtracting each recovered value from its higher multiples, and return a list of decimal strings.
F(n)=Σ[d|n]f(d); recover f from F by subtracting f(d) at every proper multiple of d The symbols and boundary conditions refer to the supplied fields and the implementation described above.
| Output field | Meaning | Value type |
|---|---|---|
| values | Recovered arithmetic function f(1) through f(N) | list of string (integer/arbitrary) |
{
"input": {
"divisorSums": [
"1",
"2",
"3",
"4",
"5",
"6"
]
},
"output": {
"values": [
"1",
"1",
"2",
"2",
"4",
"2"
]
}
}Limitations and assumptions
The first array entry is F(1), not F(0). Empty prefixes are allowed; at most 1000 entries are accepted, and no values beyond the prefix are inferred.
Use the declared integer bounds and string formats. Large exact outputs remain decimal strings; numerical approximations use ordinary floating-point arithmetic. A rejected input is different from a valid zero count or false membership flag.
Alternative or Complementary methods
Choose Dirichlet Convolution Prefix when you need its operation: Compute h(n)=Σ(d|n)f(d)g(n/d) for equally sized arithmetic-function prefixes starting at n=1, using exact integers and at most 1,000 terms. Choose Mertens Function for the complementary operation: Return M(n)=Σ(k≤n)μ(k) exactly by sieving distinct prime factors and square factors, with M(0)=0 and n capped at 1,000,000.
Background reference: Digital Library of Mathematical Functions, §27.5.
References
-
Digital Library of Mathematical Functions, §27.5 — National Institute of Standards and Technology
Similar or alternative tools
- Dirichlet Convolution Prefix
Compute h(n)=Σ(d|n)f(d)g(n/d) for equally sized arithmetic-function prefixes starting at n=1, using exact integers and at most 1,000 terms.
- Mertens Function
Return M(n)=Σ(k≤n)μ(k) exactly by sieving distinct prime factors and square factors, with M(0)=0 and n capped at 1,000,000.