login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006579 a(n) = Sum_{k=1..n-1} gcd(n,k).
(Formerly M0941)
14
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
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
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)
Michael Monagan and Baris Tuncer, Some results on counting roots of polynomials and the Sylvester resultant, arXiv:1609.08712 [math.CO], 2016.
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
EXAMPLE
a(12) = gcd(12,1) + gcd(12,2) + ... + gcd(12,11) = 1 + 2 + 3 + 4 + 1 + 6 + 1 + 4 + 3 + 2 + 1 = 28.
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 *)
PROG
(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
CROSSREFS
Antidiagonal sums of array A003989.
Cf. A018804.
Sequence in context: A096189 A010464 A187209 * A227906 A366974 A346004
KEYWORD
nonn
AUTHOR
EXTENSIONS
More terms from Robert G. Wilson v, May 04 2002
Corrected by Ron Lalonde (ronronronlalonde(AT)hotmail.com), Oct 24 2002
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)