cp's OEIS Frontend

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

%I A006579 M0941 #68 Jun 19 2025 05:56:57
%S A006579 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 A006579 49,54,76,28,105,30,80,72,65,82,132,36,73,86,140,40,153,42,124,144,89,
%U A006579 46,192,84,145,114,148,52,189,134,204,128,113,58,300,60,121,210,192
%N A006579 a(n) = Sum_{k=1..n-1} gcd(n,k).
%C A006579 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
%C A006579 Conjecture: a(n) != -1 (mod n) for a composite n. - _Thomas Ordowski_, Jun 11 2025
%D A006579 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006579 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 A006579 Marc Le Brun, <a href="/A006577/a006577.pdf">Email to N. J. A. Sloane, Jul 1991</a>.
%H A006579 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 A006579 a(p) = p-1 for a prime p.
%F A006579 a(n) = A018804(n)-n = Sum_{ d divides n } (d-1)*phi(n/d). - _Vladeta Jovovic_, May 04 2002
%F A006579 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 A006579 G.f.: Sum_{k>=1} phi(k) * x^(2*k) / (1 - x^k)^2. - _Ilya Gutkovskiy_, Feb 06 2020
%F A006579 a(p^k) = k(p-1)p^(k-1) for prime p. - _Chai Wah Wu_, May 15 2022
%e A006579 a(12) = gcd(12,1) + gcd(12,2) + ... + gcd(12,11) = 1 + 2 + 3 + 4 + 1 + 6 + 1 + 4 + 3 + 2 + 1 = 28.
%p A006579 a:= n-> add(igcd(n, k), k=1..n-1):
%p A006579 seq(a(n), n=1..64);
%t A006579 f[n_] := Sum[ GCD[n, k], {k, 1, n - 1}]; Table[ f[n], {n, 1, 60}]
%t A006579 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 A006579 (PARI) A006579(n) = sum(k=1,n-1,gcd(n,k)) \\ _Michael B. Porter_, Feb 23 2010
%o A006579 (Python)
%o A006579 from math import prod
%o A006579 from sympy import factorint
%o A006579 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 A006579 Antidiagonal sums of array A003989.
%Y A006579 Cf. A018804.
%K A006579 nonn
%O A006579 1,3
%A A006579 _Marc LeBrun_
%E A006579 More terms from _Robert G. Wilson v_, May 04 2002
%E A006579 Corrected by Ron Lalonde (ronronronlalonde(AT)hotmail.com), Oct 24 2002