login
a(n) = Sum_{k=1..n-1} gcd(n,k).
(Formerly M0941)
14

%I M0941 #61 Apr 26 2023 06:20:25

%S 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,

%T 49,54,76,28,105,30,80,72,65,82,132,36,73,86,140,40,153,42,124,144,89,

%U 46,192,84,145,114,148,52,189,134,204,128,113,58,300,60,121,210,192

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

%C 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

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

%H Amiram Eldar, <a href="/A006579/b006579.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..2000 from T. D. Noe)

%H Marc Le Brun, <a href="/A006577/a006577.pdf">Email to N. J. A. Sloane, Jul 1991</a>.

%H Michael Monagan and Baris Tuncer, <a href="http://arxiv.org/abs/1609.08712">Some results on counting roots of polynomials and the Sylvester resultant</a>, arXiv:1609.08712 [math.CO], 2016.

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

%F a(n) = A018804(n)-n = Sum_{ d divides n } (d-1)*phi(n/d). - _Vladeta Jovovic_, May 04 2002

%F 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

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

%F a(p^k) = k(p-1)p^(k-1) for prime p. - _Chai Wah Wu_, May 15 2022

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

%p a:= n-> add(igcd(n, k), k=1..n-1):

%p seq(a(n), n=1..64);

%t f[n_] := Sum[ GCD[n, k], {k, 1, n - 1}]; Table[ f[n], {n, 1, 60}]

%t 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 *)

%o (PARI) A006579(n) = sum(k=1,n-1,gcd(n,k)) \\ _Michael B. Porter_, Feb 23 2010

%o (Python)

%o from math import prod

%o from sympy import factorint

%o 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

%Y Antidiagonal sums of array A003989.

%Y Cf. A018804.

%K nonn

%O 1,3

%A _Marc LeBrun_

%E More terms from _Robert G. Wilson v_, May 04 2002

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