A176345 Sum of gcd(k,n) from k = 1 to n over "regular" integers only (an integer k is regular if there is an x such that k^2 x == k (mod n)).
1, 3, 5, 6, 9, 15, 13, 12, 15, 27, 21, 30, 25, 39, 45, 24, 33, 45, 37, 54, 65, 63, 45, 60, 45, 75, 45, 78, 57, 135, 61, 48, 105, 99, 117, 90, 73, 111, 125, 108, 81, 195, 85, 126, 135, 135, 93, 120, 91, 135, 165, 150, 105, 135, 189, 156, 185, 171, 117, 270, 121, 183, 195
Offset: 1
Examples
For n = 8, the regular integers mod 8 are 1,3,5,7,8, so the sum of gcd's of 8 with these numbers is 12.
Links
- Daniel Suteu, Table of n, a(n) for n = 1..10000
- S. Chen and W. Zhai, Reciprocals of the Gcd-Sum Functions, J. Int. Seq. 14 (2011) # 11.8.3.
- J.-M. De Koninck and I. Katai, Some remarks on a paper of L. Toth, JIS 13 (2010) 10.1.2.
- Vaclav Kotesovec, Graph - the asymptotic ratio (1000000 terms)
- Laszlo Toth, A Gcd-Sum Function Over Regular Integers Modulo n, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.5.
- Laszlo Toth, A survey of gcd-sum functions, J. Int. Seq. 13 (2010) # 10.8.1.
- D. Zhang and W. Zhai, Mean Values of a Gcd-Sum Function Over Regular Integers Modulo n, J. Int. Seq. 13 (2010), 10.4.7.
- D. Zhang and W. Zhai, Mean Values of a Class of Arithmetical Functions, J. Int. Seq. 14 (2011) #11.6.5.
Programs
-
Maple
A176345 := proc(n) n*mul(2-1/p,p=numtheory[factorset](n)) ; end proc: seq(A176345(n),n=1..40) ; # R. J. Mathar, Sep 13 2016
-
Mathematica
f[p_, e_] := 2*p^e - p^(e - 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 11 2020 *)
-
PARI
isregg(k, n) = {g = gcd(k, n); if ((n % g == 0) && (gcd(g, n/g) == 1), return(g), return(0));} a(n) = sum(k=1, n, isregg(k, n)) \\ Michel Marcus, May 25 2013 -
PARI
a(n) = sumdiv(n, d, d * eulerphi(n/d) * moebius(n/d)^2); \\ Daniel Suteu, Jun 27 2018
-
PARI
a(n) = my(f=factor(n)); prod(k=1, #f~, 2*f[k,1]^f[k,2] - f[k,1]^(f[k,2]-1)); \\ Daniel Suteu, Jun 27 2018
-
PARI
for(n=1, 100, print1(direuler(p=2, n, (1 + p*X^2 - p^2*X^2 - X)/(1-p*X)^2)[n], ", ")) \\ Vaclav Kotesovec, Aug 20 2021
Formula
Multiplicative with a(p^e) = 2*p^e-p^(e-1).
Dirichlet g.f.: zeta(s-1)*product_p (1+p^(1-s)-p^(-s)). Dirichlet convolution of the series of absolute values of A097945 with A000027. - R. J. Mathar, Jun 11 2011
From Daniel Suteu, Jun 27 2018: (Start)
a(n) = Sum_{d|n} d * phi(n/d) * mu(n/d)^2.
a(n) = Sum_{d|n, gcd(n/d, d) = 1} d * phi(n/d). (End)
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} mu(n/gcd(n,k))^2*gcd(n,k).
a(n) = Sum_{k=1..n} mu(gcd(n,k))^2*n/gcd(n,k)*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
From Vaclav Kotesovec, Aug 20 2021: (Start)
Dirichlet g.f.: zeta(s-1)^2 * Product_{primes p} (1 + p^(1-2*s) - p^(2-2*s) - p^(-s)).
Let f(s) = Product_{primes p} (1 + p^(1-2*s) - p^(2-2*s) - p^(-s)), then Sum_{k=1..n} a(k) ~ n^2 * (f(2)*(log(n)/2 + gamma - 1/4) + f'(2)/2), where f(2) = Product_{primes p} (1 - 2/p^2 + 1/p^3) = A065464 = 0.428249505677094..., f'(2) = f(2) * Sum_{primes p} log(p) * (3*p - 2) / (p^3 - 2*p + 1) = 0.6293283828324697510445630056425352981207558777167836747744750359407300858... and gamma is the Euler-Mascheroni constant A001620. (End)
a(n) = Sum_{k = 1..n} rad(gcd(k, n)) = Sum_{d divides n} rad(d)*phi(n/d), where rad(n) = A007947(n). - Peter Bala, Jan 22 2024
Comments