Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
A127415
a(n) = 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
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 Product_{p|n} (1 - p) = 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
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
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