Computing the Inverses, their Power Sums, and Extrema for Euler's Totient and Other Multiplicative Functions
Max A. Alekseyev
Department of Mathematics
The George Washington University
801 22nd St. NW
Washington, DC 20052
USA
Abstract:
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 ϕ(·)
and the k-th power sum of
divisors σk(·).
For example, we can establish that the number of
solutions to σ1(x) = 101000
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.
Full version: pdf,
dvi,
ps,
latex
(Concerned with sequences
A055486
A055487
A055488
A055489
A055506
A072074
A072075
A072076
A110076
A110077
A110078
A153076
A153077
A153078
A165774.)
Received November 23 2015; revised version received April 27 2016.
Published in Journal of Integer Sequences, May 11 2016.
Return to
Journal of Integer Sequences home page