Computing the inverses, their power sums, and extrema for Euler's totient and other multiplicative functions

MaRDI QIDQ2808585zbMATH OpenFDO

Authors Max A. Alekseyev

Publication date 24 May 2016

Published in Journal of Integer Sequences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.6054, http://www.emis.de/journals/JIS/VOL19/Alekseyev/alek5.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Dirichlet seriesmultiplicative functioninverse functionsum of divisorsEuler's totient function

Mathematics Subject Classification ID

Arithmetic functions; related numbers; inversion formulas (11A25) Values of arithmetic functions; tables (11Y70)

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 $varphi(cdot)$ and the $k$-th power sum of divisors $sigm{a}_k(cdot)$. For example, we can establish that the number of solutions to $sigm{a}_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.

Recommendations

• Euler's totient function and its inverse
• Complexity of inverting the Euler function
• Counting invertible sums of squares modulo \(n\) and a new generalization of Euler's totient function
• The distribution of totients
• scientific article; zbMATH DE number 3979140

Cited in

(1)

• scientific article; zbMATH DE number 2184737 (Why is no real title available?)

This page was built for publication: Computing the inverses, their power sums, and extrema for Euler's totient and other multiplicative functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2808585)