Pillai's Arithmetical Function

The multiplicative gcd-sum function P(n)=sum from k=1 to n of gcd(k,n), whose divisor-class decomposition P=idphi exposes prime-power evaluation, Euler products, and average-order analysis.*

Version

v1 · 2026-08-30 · History

Domain-specific #

2487

Origin domain

number theory

Subdomain

multiplicative arithmetic functions

Aliases

Gcd-sum function, Pillai function

Core Idea

Pillai's arithmetical function, also called the gcd-sum function, is the positive-integer function

\[ P(n)=\sum_{k=1}^{n}\gcd(k,n). \]

It aggregates how strongly every residue representative from $1$ through \(n\) shares factors with the fixed modulus \(n\). The definition looks like an \(n\)-term scan, but grouping terms by their gcd value converts it into the divisor sum

\[ P(n)=\sum_{d\mid n}d\,\varphi(n/d)=(\operatorname{id}*\varphi)(n), \]

where \(\varphi\) is Euler's totient, \(\operatorname{id}(n)=n\), and \(*\) is Dirichlet convolution. That change of representation is the abstraction's operative center. It connects a local statistic over all \(k\) to the divisor lattice of \(n\), proves multiplicativity, reduces evaluation to prime powers, and opens the function to Dirichlet-series and average-order methods.

Scope of Application

The home scope is multiplicative and analytic number theory. Elementary work uses the divisor formula, prime-power values, and multiplicativity to evaluate or compare \(P(n)\). Analytic work studies summatory functions, means, moments, reciprocal sums, error terms, and the Dirichlet series. Broughan connects the function to a lattice-point counting problem and develops its growth and Dirichlet-series behavior. Tóth's survey documents classical properties, average orders, generalizations, unitary and exponential analogues, and several-variable versions.

Clarity

A recognition test has four checks. First, is the input one positive integer \(n\)? Second, does \(k\) range over $1$ through \(n\)? Third, is the summand exactly \(\gcd(k,n)\) with no exponent or auxiliary weight? Fourth, is the output the sum of those \(n\) gcds? If so, it is Pillai's arithmetical function regardless of whether it is written as a raw sum, divisor sum, convolution, prime-power product, or Dirichlet series.

Manages Complexity

Direct computation appears to require \(n\) gcd operations for each input. The divisor-class decomposition compresses those \(n\) terms to one term per divisor, and multiplicativity compresses a composite input further to its prime-power factors. For highly structured \(n\), the change is not cosmetic: it turns a long list of repeated gcd values into a short expression determined by the factorization.

Abstract Reasoning

Given a factorization, evaluation is immediate. Factor \(n=\prod p_i^{a_i}\), evaluate \(p_i^{a_i-1}((a_i+1)p_i-a_i)\) for each prime power, and multiply. Conversely, the size of \(P(n)/n\) reflects the distinct prime divisors and their exponents through

\[ \frac{P(p^a)}{p^a}=1+a\left(1-\frac1p\right). \]

Knowledge Transfer

Within number theory, the complete reasoning package transfers literally across arithmetic identities, multiplicative-function algebra, average-order analysis, lattice counting, and generalized gcd sums. The same \(P(n)\) can be recognized in a finite sum, a divisor convolution, a prime-power formula, a normalized mean, or a Dirichlet series. Fluency in one representation gives leverage in the others.

The method of grouping a sum by the value of an invariant transfers more broadly: partition the index set into gcd classes, count each class, and multiply class size by its common weight.

Relationships to Other Abstractions

Current abstraction Pillai's Arithmetical Function Domain-specific

Parents (1) — more general patterns this builds on

• Pillai's Arithmetical Function is a kind of Function (Mapping) Prime

  Pillai's Arithmetical Function strictly instantiates prime:function_mapping.

Hierarchy path (1) — routes to 1 parentless root

• Pillai's Arithmetical Function → Function (Mapping)

Neighborhood in Abstraction Space

Pillai's Arithmetical Function sits in a sparse region of the domain-specific corpus (82^nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Elliptic Arithmetic & Group Finiteness (5 abstractions)

Nearest neighbors

• Primefree Sequence — 0.82
• Coin Problem — 0.81
• Fermat number — 0.81
• Ramanujan's sum — 0.81
• Refactorable number — 0.81

Computed from structural-signature embeddings · 2026-09-08