login
a(n) = Sum_{1<=k<=n, gcd(k,n)=1}, A000217(k).
3

%I #33 Feb 15 2022 02:46:39

%S 1,1,4,7,20,16,56,50,93,80,220,110,364,224,340,372,816,354,1140,580,

%T 966,880,2024,820,2200,1456,2304,1666,4060,1240,4960,2856,3850,3264,

%U 5180,2706,8436,4560,6396,4440,11480,3612,13244,6710,8400,8096,17296,6344,17297,8600

%N a(n) = Sum_{1<=k<=n, gcd(k,n)=1}, A000217(k).

%C From _Wolfdieter Lang_, Jun 14 2011: (Start)

%C 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.

%C 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.

%C 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.

%C (End)

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

%H Seiichi Manyama, <a href="/A127415/b127415.txt">Table of n, a(n) for n = 1..10000</a>

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

%F From _Wolfdieter Lang_, May 17 2011: (Start)

%F 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).

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

%F Proof via inclusion-exclusion.

%F (End)

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

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

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

%o (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

%o (PARI) a(n) = sum(k=1, n, if (gcd(n,k)==1, k*(k+1)/2)); \\ _Michel Marcus_, Feb 01 2016

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

%K nonn,easy

%O 1,3

%A _Gary W. Adamson_, Jan 13 2007

%E More terms and formula from _Wolfdieter Lang_, May 17 2011

%E More terms from _Michel Marcus_, Feb 01 2016