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.
Description
Dirichlet convolution combines arithmetic functions over divisors of an integer.
Dirichlet convolution combines arithmetic functions over divisors of an integer. Its array representation starts at argument one, unlike a zero-indexed sequence transform.1
The tool returns values. The indexing and output conventions below determine how to read these values.
When to use Dirichlet Convolution Prefix
Use this for the following task: 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. Use the input and output conventions below to reproduce the intended mathematical quantity.
How to use Dirichlet Convolution Prefix and understand its results
- Choose the required indexes, integers or sequence entries. Preserve decimal-string encodings where the field table specifies strings.
- Enter left, right 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 |
|---|---|---|---|
| left | Values 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 |
| right | Values g(1) through g(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 |
Read equally sized signed-decimal prefixes with BigInt, then visit divisor/quotient pairs whose product lies in the prefix and add their product to that output entry.
h(n)=Σ[d|n]f(d)×g(n/d) The symbols and boundary conditions refer to the supplied fields and the implementation described above.
| Output field | Meaning | Value type |
|---|---|---|
| values | Dirichlet convolution h(1) through h(N) | list of string (integer/arbitrary) |
{
"input": {
"left": [
"1",
"1",
"1",
"1",
"1",
"1"
],
"right": [
"1",
"2",
"3",
"4",
"5",
"6"
]
},
"output": {
"values": [
"1",
"3",
"4",
"7",
"6",
"12"
]
}
}Limitations and assumptions
Empty prefixes are allowed and each list is capped at 1000 entries. Unequal lengths are an error, and no functions are inferred outside the supplied range.
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 Möbius Inversion of Divisor Sums when you need its operation: 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. Choose Binomial Transform of an Integer Sequence for the complementary operation: Transform a zero-indexed prefix by b(n)=ΣC(n,k)a(k) using exact decimal integers; empty prefixes are allowed and input is capped at 256 terms.
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
- 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.
- Binomial Transform of an Integer Sequence
Transform a zero-indexed prefix by b(n)=ΣC(n,k)a(k) using exact decimal integers; empty prefixes are allowed and input is capped at 256 terms.