|
| |
|
|
A006579
|
|
Sum of gcd(n,k) for k = 1 to n-1.
(Formerly M0941)
|
|
13
|
|
|
|
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
|
T. D. Noe, Table of n, a(n) for n = 1..2000
M. Le Brun, Email to N. J. A. Sloane, Jul 1991
Michael Monagan, Baris Tuncer, Some results on counting roots of polynomials and the Sylvester resultant, arXiv:1609.08712 [math.CO], (27-September-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
|
|
|
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}]
|
|
|
PROG
|
(PARI) A006579(n) = sum(k=1, n-1, gcd(n, k)) \\ Michael B. Porter, Feb 23 2010
|
|
|
CROSSREFS
|
Antidiagonal sums of array A003989.
Sequence in context: A096189 A010464 A187209 * A227906 A195727 A256701
Adjacent sequences: A006576 A006577 A006578 * A006580 A006581 A006582
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Marc LeBrun
|
|
|
EXTENSIONS
|
More terms from Robert G. Wilson v, May 04 2002
Corrected by Ron Lalonde (ronronronlalonde(AT)hotmail.com), Oct 24 2002
|
|
|
STATUS
|
approved
|
| |
|
|
