






















We propose a generic algorithm for computing the inverses of a multiplicative function under the assumption that the set of inverses is finite. More generally, our algorithm can compute certain functions of the inverses, such as their power sums (e.g., cardinality) or extrema, without direct enumeration of the inverses. We illustrate our algorithm with Euler's totient function $\varphi(\cdot)$ and the $k$-th power sum of divisors $σ_k(\cdot)$. For example, we can establish that the number of solutions to $σ_1(x) = 10^{1000}$ is 15,512,215,160,488,452,125,793,724,066,873,737,608,071,476, while it is intractable to iterate over the actual solutions.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。