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

zbMATH Open1338.11109arXiv1401.6054MaRDI QIDQ2808585FDOQ2808585

Authors: Max A. Alekseyev 

Publication date: 24 May 2016

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

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.

Full work available at URL: https://arxiv.org/abs/1401.6054

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

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

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)

Cited In (1)

• Title not available (Why is that?)

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)