

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



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

It is also the product of n and (21/p), taken over all primes p dividing n.
Multiplicative with a(p^e) = 2*p^ep^(e1).


LINKS

Table of n, a(n) for n=1..63.
Laszlo Toth, A GcdSum Function Over Regular Integers Modulo n, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.5


FORMULA

Dirichlet g.f. zeta(s1)*product_p (1+p^(1s)p^(s)). Dirichlet convolution of the series of absolute values of A097945 with A000027.  R. J. Mathar, Jun 11 2011


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.


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


CROSSREFS

Cf. A143869.
Sequence in context: A072522 A070111 A070117 * A101139 A102606 A102372
Adjacent sequences: A176342 A176343 A176344 * A176346 A176347 A176348


KEYWORD

nonn,mult


AUTHOR

Jeffrey Shallit, Apr 15 2010


STATUS

approved



