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
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
For example, we can establish that the number of
solutions to σ1(x) = 101000
while it is intractable to iterate over the actual solutions.
Full version: pdf,
(Concerned with sequences
Received November 23 2015; revised version received April 27 2016.
Published in Journal of Integer Sequences, May 11 2016.
Journal of Integer Sequences home page