login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A127415 Sum {1<=k<=n, gcd(k,n)=1}, A000217(k). 3
1, 1, 4, 7, 20, 16, 56, 50, 93, 80, 220, 110, 364, 224, 340, 372, 816, 354, 1140, 580, 966, 880, 2024, 820, 2200, 1456, 2304, 1666, 4060, 1240, 4960, 2856, 3850, 3264, 5180, 2706, 8436, 4560, 6396, 4440, 11480, 3612, 13244, 6710, 8400, 8096, 17296, 6344, 17297, 8600 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

From Wolfdieter Lang, Jun 14 2011: (Start)

Such sums are over a reduced residue system modulo n. See the Apostol reference, p. 133, for the definition or the wikipedia link given under A189918.

This sum over triangular numbers can be found using the results given in exercise 16 of the Apostol reference on p. 48, together with the definition of phi_1(n) and phi_2(n) from the exercise 15.

The result for n>=2 coincides with the formula given below, using for product(1-p,p|n) = mu(rad(n))*rad(n)*phi(n)/n, with the definitions given there.

(End)

REFERENCES

T. Apostol, Introduction to Analytic Number Theory, Springer, 1986.

LINKS

Seiichi Manyama, Table of n, a(n) for n = 1..10000

FORMULA

M * V where M = A054521 is an infinite lower triangular matrix and V = A000217: (1, 3, 6, 10,...).

From Wolfdieter Lang, May 17 2011: (Start)

a(n) = (n/(3!*2))*((2*n+3)*n + mu(rad(n))*rad(n))*(phi(n)/n), n>=2, with rad(n) the squarefree kernel of n (the largest squarefree number dividing n, see A007947), the Moebius function mu(n)=A008683(n), and the Euler totient function phi(n)= A000010(n).

Note that phi(n)/n = A076512(n)/A109395(n) = phi(rad(n))/rad(n).

Proof via inclusion-exclusion.

  (End)

EXAMPLE

a(6) = 16 since the relative primes of 6 are 1 and 5 and (1 + 15) = 16.

a(6) = (6/(3!*2))*(15*6 + 1*6)*(1/2)*(2/3)= 16.

MATHEMATICA

rad[n_] := Times @@ (FactorInteger[n][[ All, 1]]); a[n_] := (n/(3!*2))*((2*n+3)*n + MoebiusMu[ rad[n]]*rad[n])*(EulerPhi[n] / n); a[1] = 1; Table[ a[n], {n, 1, 33}] (* Jean-François Alcover, Oct 03 2011 *)

PROG

(PARI) a(n)=if(n<3, return(1)); my(s=factor(n)[, 1]); s=prod(i=1, #s, s[i]); (n/12)*((2*n+3)*n + moebius(s)*s)*(eulerphi(n)/n) \\ Charles R Greathouse IV, May 17 2011

(PARI) a(n) = sum(k=1, n, if (gcd(n, k)==1, k*(k+1)/2)); \\ Michel Marcus, Feb 01 2016

CROSSREFS

Cf. A000217, A023896, A076512/A109395, A189918.

Sequence in context: A133264 A253208 A275389 * A045548 A090879 A084404

Adjacent sequences:  A127412 A127413 A127414 * A127416 A127417 A127418

KEYWORD

nonn,easy

AUTHOR

Gary W. Adamson, Jan 13 2007

EXTENSIONS

More terms and formula from Wolfdieter Lang, May 17 2011

More terms from Michel Marcus, Feb 01 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 26 13:09 EST 2022. Contains 350598 sequences. (Running on oeis4.)