A006579 a(n) = Sum_{k=1..n-1} gcd(n,k).

0, 1, 2, 4, 4, 9, 6, 12, 12, 17, 10, 28, 12, 25, 30, 32, 16, 45, 18, 52, 44, 41, 22, 76, 40, 49, 54, 76, 28, 105, 30, 80, 72, 65, 82, 132, 36, 73, 86, 140, 40, 153, 42, 124, 144, 89, 46, 192, 84, 145, 114, 148, 52, 189, 134, 204, 128, 113, 58, 300, 60, 121, 210, 192

Offset: 1

Author

Marc LeBrun

Keywords

• nonn

Comments

This sequence for a(n) also arises in the following context. If f(x) is a monic univariate polynomial of degree d>1 over Zn (= Z/nZ, the ring of integers modulo n), and we let X be the number of distinct roots of f(x) in Zn taken over all n^d choices for f(x), then the variance Var[X] = a(n)/n and the expected value E[X] = 1. - Michael Monagan, Sep 11 2015

Conjecture: a(n) != -1 (mod n) for a composite n. - Thomas Ordowski, Jun 11 2025

Examples

			a(12) = gcd(12,1) + gcd(12,2) + ... + gcd(12,11) = 1 + 2 + 3 + 4 + 1 + 6 + 1 + 4 + 3 + 2 + 1 = 28.
		

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..2000 from T. D. Noe)
• Marc Le Brun, Email to N. J. A. Sloane, Jul 1991.
• Michael Monagan and Baris Tuncer, Some results on counting roots of polynomials and the Sylvester resultant, arXiv:1609.08712 [math.CO], 2016.

Crossrefs

Antidiagonal sums of array A003989.

Cf. A018804.

Programs

Maple

a:= n-> add(igcd(n, k), k=1..n-1):
seq(a(n), n=1..64);

Mathematica

f[n_] := Sum[ GCD[n, k], {k, 1, n - 1}]; Table[ f[n], {n, 1, 60}]
f[p_, e_] := (e*(p - 1)/p + 1)*p^e; a[n_] := Times @@ f @@@ FactorInteger[n] - n; Array[a, 100] (* Amiram Eldar, Apr 26 2023 *)

PARI

A006579(n) = sum(k=1,n-1,gcd(n,k)) \\ Michael B. Porter, Feb 23 2010

Python

from math import prod
from sympy import factorint
def A006579(n): return prod(p**(e-1)*((p-1)*e+p) for p, e in factorint(n).items()) - n # Chai Wah Wu, May 15 2022

Formula

a(p) = p-1 for a prime p.

a(n) = A018804(n)-n = Sum_{ d divides n } (d-1)*phi(n/d). - Vladeta Jovovic, May 04 2002

a(n+2) = Sum_{k=0..n} gcd(n-k+1, k+1) = -Sum_{k=0..4n+2} gcd(4n-k+3, k+1)*(-1)^k/4. - Paul Barry, May 03 2005

G.f.: Sum_{k>=1} phi(k) * x^(2*k) / (1 - x^k)^2. - Ilya Gutkovskiy, Feb 06 2020

a(p^k) = k(p-1)p^(k-1) for prime p. - Chai Wah Wu, May 15 2022

Extensions

More terms from Robert G. Wilson v, May 04 2002

Corrected by Ron Lalonde (ronronronlalonde(AT)hotmail.com), Oct 24 2002