login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006579 Sum of GCD(n,k) for k = 1 to n-1.
(Formerly M0941)
11
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

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 := proc(n) local k; add( igcd(n, k), k=1..n-1 ) end;

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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified September 23 13:55 EDT 2017. Contains 292358 sequences.