Geodesic
Computing the inverses, their power sums, and extrema for Euler's totient and other multiplicative functions
Journal of integer sequences, Tome 19 (2016) no. 5.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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 $\sigma _{k}$(;). For example, we can establish that the number of solutions to $\sigma _{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.
Classification : 11Y16, 11A05, 11Y55, 11Y70, 30B50
Keywords: multiplicative function, Euler's totient function, sum of divisors, inverse function, Dirichlet series 
@article{JIS_2016__19_5_a1,
     author = {Alekseyev, Max A.},
     title = {Computing the inverses, their power sums, and extrema for {Euler's} totient and other multiplicative functions},
     journal = {Journal of integer sequences},
     publisher = {mathdoc},
     volume = {19},
     number = {5},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2016__19_5_a1/}
}
TY  - JOUR
AU  - Alekseyev, Max A.
TI  - Computing the inverses, their power sums, and extrema for Euler's totient and other multiplicative functions
JO  - Journal of integer sequences
PY  - 2016
VL  - 19
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JIS_2016__19_5_a1/
LA  - en
ID  - JIS_2016__19_5_a1
ER  - 
%0 Journal Article
%A Alekseyev, Max A.
%T Computing the inverses, their power sums, and extrema for Euler's totient and other multiplicative functions
%J Journal of integer sequences
%D 2016
%V 19
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JIS_2016__19_5_a1/
%G en
%F JIS_2016__19_5_a1
Alekseyev, Max A. Computing the inverses, their power sums, and extrema for Euler's totient and other multiplicative functions. Journal of integer sequences, Tome 19 (2016) no. 5. http://geodesic.mathdoc.fr/item/JIS_2016__19_5_a1/