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,2

Comments

It is also the product of n and (2-1/p), taken over all primes p dividing n.

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.

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

Example

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.

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

Prog

(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

Crossrefs

Cf. A007947, A143869.

Sequence in context: A294909 A070111 A070117 * A101139 A309140 A102606

Adjacent sequences: A176342 A176343 A176344 * A176346 A176347 A176348

Keyword

nonn,mult,easy

Author

Jeffrey Shallit, Apr 15 2010

Status

approved