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.^[1] 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.^[2]

The function was introduced by S. S. Pillai in 1933 and now anchors a family of gcd-sum analogues and generalizations.^[3]^[1] It is a specific mathematical mapping, not a generic technique called “Pillai's function”: the input is a positive integer, the summands are greatest common divisors with that input, and the output is their sum.

Structural Signature¶

The signature is:

fixed positive integer $n$ + complete residue interval $1\leq k\leq n$ + gcd statistic $\gcd(k,n)$ + aggregation over $k$ + regrouping by divisor classes + multiplicative reconstruction from prime powers.

Every value $d=\gcd(k,n)$ must divide $n$. For a fixed divisor $d\mid n$, write $k=dj$. The condition $\gcd(k,n)=d$ becomes $\gcd(j,n/d)=1$, and exactly $\varphi(n/d)$ relevant values of $j$ occur. The gcd-$d$ class therefore contributes $d\varphi(n/d)$, proving the divisor formula.

Because both $\operatorname{id}$ and $\varphi$ are multiplicative and Dirichlet convolution preserves multiplicativity,

\[ \gcd(m,n)=1\quad\Longrightarrow\quad P(mn)=P(m)P(n). \]

For a prime power $p^a$,

\[ P(p^a)=p^a+a\,p^{a-1}(p-1)=p^{a-1}((a+1)p-a). \]

Thus if $n=\prod_i p_i^{a_i}$, the whole value is $P(n)=\prod_i P(p_i^{a_i})$. The input domain, gcd weighting, complete interval, and divisor-class regrouping are mandatory. Replacing gcd, changing the weights, or summing over only coprime $k$ defines a related function rather than a harmless presentation variant.

What It Is Not¶

Pillai's function is not the divisor-counting function $\tau(n)=\sum_{d\mid n}1$ and not the sum-of-divisors function $\sigma(n)=\sum_{d\mid n}d$. Those sum directly over divisors. $P$ sums gcd values over a complete residue interval, and its divisor representation weights each $d$ by $\varphi(n/d)$.

It is not Euler's totient function. $\varphi(n)$ counts integers up to $n$ coprime to $n$; in the gcd-sum, totients count how many summands occupy each gcd class. Totient is a constituent of the convolution, not an alias.

It is not the bare summatory function of gcd in two unbounded variables. Here one argument is fixed at $n$ and the other ranges through exactly one complete interval. Nor is it any statistic that happens to contain a gcd.

It is also not the unrelated functions, distributions, trace statistics, inequalities, or tests bearing Pillai's name. The eponym alone does not establish identity. “Pillai function” should be accepted only where the gcd-sum context is clear.

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.^[2] Tóth's survey documents classical properties, average orders, generalizations, unitary and exponential analogues, and several-variable versions.^[1]

The normalized mean

\[ A(n)=\frac{P(n)}{n}=\sum_{d\mid n}\frac{\varphi(d)}{d} \]

is the arithmetic mean of $\gcd(1,n),\ldots,\gcd(n,n)$. The Dirichlet generating series follows from $P=\operatorname{id}*\varphi$:

\[ \sum_{n\ge1}\frac{P(n)}{n^s}=\frac{\zeta(s-1)^2}{\zeta(s)} \]

in its half-plane of absolute convergence.^[1]^[2] These are exact transformations of the same function, not new definitions.

Analogues using unitary gcds, exponential divisors, regular integers, several variables, powers, or other weights belong to the gcd-sum family. They are not automatically values or aliases of the original $P$; each changes at least one mandatory role.

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.

Equivalent formulas should be checked by role, not typography. The divisor expression $\sum_{d\mid n}d\varphi(n/d)$ and the rearranged normalized expression $\sum_{d\mid n}\varphi(d)/d$ refer to the same gcd classes after a change of divisor variable. The Möbius form

\[ P(n)=\sum_{d\mid n}d\,\tau(d)\mu(n/d) \]

follows from $\varphi=\operatorname{id}*\mu$ and $\operatorname{id}*\operatorname{id}(d)=d\tau(d)$. Formula equivalence is structural evidence; it must not be mistaken for three different functions.

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.

The abstraction also unifies different questions. The raw sum answers a finite combinatorial question about common divisors. The convolution form places the function in the algebra of arithmetic functions. The Euler product and Dirichlet series connect it to complex-analytic tools. The normalized form interprets it as an average gcd. One named function lets results migrate among those representations without rederiving the object each time.

Finally, it provides a baseline for generalization. Researchers can state exactly which role changes—gcd notion, weighting, number of variables, allowed divisors, or averaging operator—and compare a new function to $P$ instead of inventing an unrelated notation for every variation.

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). \]

This licenses comparisons: adding a new prime factor multiplies the normalized value by a factor greater than one; increasing an exponent changes the prime-power factor linearly in $a$ after normalization.

The divisor formula licenses inversion and transform reasoning. Since $P=\operatorname{id}*\varphi=\operatorname{id}*\operatorname{id}*\mu$, identities for Dirichlet convolution can move between $P$, $\varphi$, $\mu$, and $\tau$. Dirichlet-series multiplication then converts convolution into a quotient of zeta functions, and singularities of that series guide average-order analysis.^[2]

Boundary counterfactuals are equally useful. Restrict the raw sum to $\gcd(k,n)=1$ and every retained term is one, yielding $\varphi(n)$ rather than $P(n)$. Replace gcd by $\gcd(k,n)^r$ and one obtains a power-weighted analogue. The original identity survives only when the mandatory roles stay fixed.

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. Dirichlet convolution and multiplicative reconstruction also transfer to many arithmetic functions. But those general methods belong to aggregation, partitioning, factorization, and function mapping. Calling every divisor-class sum “Pillai's function” would confuse a reusable method with this exact function.

Outside mathematics, the eponym has no literal application. A social or engineering system that “adds shared factors” is at most an analogy. The mathematical mapping remains domain-specific even though its internal relations are entirely structural.

Examples¶

Canonical: $n=12$¶

The direct definition gives

\[ P(12)=1+2+3+4+1+6+1+4+3+2+1+12=40. \]

Grouping by divisors gives the same result:

\[ \sum_{d\mid12}d\varphi(12/d)=1\cdot4+2\cdot2+3\cdot2+4\cdot2+6\cdot1+12\cdot1=40. \]

The multiplicative route is shorter still. Since $12=2^2\cdot3$ and the factors are coprime,

\[ P(12)=P(4)P(3)=8\cdot5=40. \]

The fixed input is 12; the twelve gcd values are the summands; divisors of 12 are the gcd classes; totients are the class counts; and the prime-power factors are the multiplicative reconstruction.

Applied: lattice-counting and average order¶

Broughan studies the gcd-sum as an arithmetic function arising in an asymptotic lattice-point counting problem and develops its multiplicativity, polynomial growth, Dirichlet series, and partial-sum estimates.^[2] In that setting, the finite gcd statistic becomes a coefficient sequence whose Dirichlet series is expressed compactly through the Riemann zeta function.

Mapped back, $P(n)$ is still the same coefficient function; $P=\operatorname{id}*\varphi$ is the convolution bridge; the zeta quotient is the transform representation; and summing $P(n)$ or $P(n)/n^s$ over ranges is the average-order problem. The application demonstrates why the entry is more than a sequence lookup: its divisor structure supports a reusable analytic program.

Structural Tensions¶

Direct definition versus structural formula. The gcd sum is intuitive but computationally long; the divisor and prime-power formulas are efficient but hide the original statistic. Diagnostic: use the raw form to establish meaning and the convolution form to prove and calculate.
Exact function versus family of analogues. Generalization reveals structure, but loose naming can erase which gcd, divisor system, exponent, or variable count is used. Diagnostic: state the altered mandatory role and assign a separate symbol before importing a theorem.
Multiplicativity versus non-complete additivity. Coprime factorization makes $P$ multiplicative, but $P(mn)=P(m)P(n)$ need not hold when $m$ and $n$ share primes. Diagnostic: check coprimality or work at prime powers before multiplying.
Factorization efficiency versus factorization cost. The prime-power formula is fast once $n$ is factored, but obtaining the factorization may dominate for large inputs. Diagnostic: compare divisor enumeration, gcd scanning, and factorization costs for the actual input regime.
Equivalent notation versus name collision. “Pillai function” is concise in context but Pillai's name labels other mathematical objects. Diagnostic: require gcd-sum or the defining formula wherever context is not exclusively multiplicative number theory.

Structural–Framed Character¶

Pillai's Arithmetical Function is structural, with aggregate framed score $0.04$. Its identity is fixed by a mapping on positive integers, and its convolution, multiplicativity, and prime-power behavior hold independently of users, institutions, or evaluative judgments. No outcome is marked good or bad.

The eponym and the decision to study this mapping are historical, but the mathematical relation is not institution-created. Another culture could discover the same gcd sum and all the same identities under a different name. Applying it means recognizing an extensional function, not imposing a frame.

Structural Core vs. Domain Accent¶

What is skeletal. Partition a finite index set by an invariant value, count each class, aggregate class value times multiplicity, and exploit factorization when the resulting mapping is multiplicative. This is a portable mathematical pattern.

What is domain-bound. Positive integers, greatest common divisors, Euler's totient, divisor lattices, Dirichlet convolution, prime powers, Möbius inversion, and zeta-function transforms make the object specifically number-theoretic. Remove them and the remaining aggregation method is not Pillai's function.

Why not a prime. A prime should recur as the same abstraction across unrelated substrates. This exact function remains a named object within number theory. Function Mapping, Aggregation, Partitioning, and Factorization carry the generalizable structure. The autonomous mathematical identity merits a domain-specific entry, while its specificity blocks prime promotion.

Pillai's Arithmetical Function strictly instantiates prime:function_mapping. Its domain is the positive integers; its codomain is the positive integers; and every input $n$ receives the uniquely determined output $\sum_{k=1}^{n}\gcd(k,n)$. Function Mapping supplies the input–output relation, while this child adds its gcd aggregation and arithmetic structure.

It is related to the accepted-workspace domain_specific:natural_number, which supplies its domain but is not a containing abstraction; to prime:aggregation, because it sums a finite family; to prime:factorization, because multiplicativity reduces values to prime powers; and to prime:discreteness, because its domain and divisor classes are discrete. The accepted domain_specific:normal_order_arithmetic_function is an analytic technique that could be applied to arithmetic functions; it does not define this one.

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

Not to Be Confused With¶

Euler's totient $\varphi(n)$. Counts residues coprime to $n$. Tell: totient supplies the multiplicity of each gcd class inside $P$.
Divisor count $\tau(n)$. Counts positive divisors. Tell: it has no gcd-class weight and enters only in an alternative convolution identity.
Sum of divisors $\sigma(n)$. Adds each divisor once. Tell: $P$ adds each divisor weighted by a totient count.
A general arithmetic function. Any complex-valued function on positive integers. Tell: Pillai's function is one exact member fixed by the gcd sum.
A general gcd-sum analogue. May use powers, weights, unitary or exponential gcds, or several variables. Tell: verify the unweighted ordinary gcd and the range $1\le k\le n$.
Pillai distribution or Pillai trace. Unrelated eponymous objects in probability and multivariate statistics. Tell: require the number-theoretic formula, not the surname.
Normal order of an arithmetic function. Describes typical asymptotic size outside a density-zero exception set. Tell: it is a property framework applicable to functions, not the gcd-sum mapping itself.

References¶

[1] László Tóth, “A Survey of Gcd-Sum Functions,” Journal of Integer Sequences 13 (2010), Article 10.8.1. https://cs.uwaterloo.ca/journals/JIS/VOL13/Toth/toth10.pdf registry ↩a ↩b ↩c ↩d

[2] Kevin A. Broughan, “The GCD-Sum Function,” Journal of Integer Sequences 4 (2001), Article 01.2.2. https://hdl.handle.net/10289/2024 registry ↩a ↩b ↩c ↩d ↩e

[3] S. S. Pillai, “On an Arithmetic Function,” Annamalai University Journal 2, no. 2 (1933): 242–248. Bibliographic listing: https://www.hri.res.in/~thanga/sspillai/PILLAI.html registry ↩

[4] László Tóth, “Another Generalization of the GCD-Sum Function,” Arabian Journal of Mathematics 2 (2013): 313–320. https://doi.org/10.1007/s40065-013-0077-y registry

[5] Kevin A. Broughan, “The Average Order of the Dirichlet Series of the GCD-Sum Function,” Journal of Integer Sequences 10 (2007), Article 07.4.2. https://cs.uwaterloo.ca/journals/JIS/VOL10/Broughan/broughan1.pdf registry