Misplaced Pages

In number theory, the gcd-sum function, also called Pillai's arithmetical function, is defined for every ${\displaystyle n}$ by

${\displaystyle P(n)=\sum _{k=1}^{n}\gcd(k,n)}$

or equivalently

${\displaystyle P(n)=\sum _{d\mid n}d\varphi (n/d)}$

where ${\displaystyle d}$ is a divisor of ${\displaystyle n}$ and ${\displaystyle \varphi }$ is Euler's totient function.

it also can be written as

${\displaystyle P(n)=\sum _{d\mid n}d\tau (d)\mu (n/d)}$

where, ${\displaystyle \tau }$ is the divisor function, and ${\displaystyle \mu }$ is the Möbius function.

This multiplicative arithmetical function was introduced by the Indian mathematician Subbayya Sivasankaranarayana Pillai in 1933.

References

1. ^ Lászlo Tóth (2010). "A survey of gcd-sum functions". J. Integer Sequences. 13.
2. Sum of GCD(k,n)
3. S. S. Pillai (1933). "On an arithmetic function". Annamalai University Journal. II: 242–248.
4. Broughan, Kevin (2002). "The gcd-sum function". Journal of Integer Sequences. 4 (Article 01.2.2): 1–19.

OEIS: A018804

• Arithmetic functions