Computation of the Totient Summatory Function

2025/06/09 by Brown, Lucas Augustus
Computer Science · Mathematics · #11A25 #11Y16 (Primary) 11-04 #11Y55 #11Y70 (Secondary) #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2506.07386

openalex publication_date 2025/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An algorithm is devised for computing Φ(n) = ϕ(1) + ϕ(2) + ⋯ + ϕ(n) in time \widetildeΘ(n^2/3) and space \widetildeΘ(n^1/3). The starting point is an existing algorithm based on the Dirichlet hyperbola method and the Mertens function. The algorithm is then used to compute Φ(10¹⁹) = 30396355092701331435065976498046398788.

Related

• A Successive Approximation Algorithm for Computing the Divisor Summatory Function
• Summing μ(n): a faster elementary algorithm
• On Summatory Totient Functions
• Note on a sum involving the Euler function
• Sums related to Euler's totient function