Journal of Integer Sequences, Vol. 19 (2016), Article 16.5.2

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