##
**
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*) = 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.

**
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**