A066840 Sum of positive integers k where k <= n/2 and gcd(k,n) = 1.

0, 1, 1, 1, 3, 1, 6, 4, 7, 4, 15, 6, 21, 9, 14, 16, 36, 13, 45, 20, 30, 25, 66, 24, 63, 36, 61, 42, 105, 32, 120, 64, 80, 64, 102, 54, 171, 81, 114, 80, 210, 66, 231, 110, 134, 121, 276, 96, 258, 124, 200, 156, 351, 121, 270, 168, 252, 196, 435, 120, 465, 225, 282

Offset

1,5

Comments

a(n) = n iff n = 16, 20, 24. - Bernard Schott, Mar 17 2021

Links

Seiichi Manyama, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Harry J. Smith)

John D. Baum, A Number-Theoretic Sum, Mathematics Magazine 55.2 (1982): 111-113.

Karl Dilcher and Christophe Vignat, Infinite products involving Dirichlet characters and cyclotomic polynomials, arXiv:1801.09160 [math.NT], 2018.

David Zmiaikou, Origamis and permutation groups, Thesis, 2011. See p. 65.

Formula

For odd prime p, a(p) = (p^2-1)/8. - Thomas Ordowski, Nov 12 2014

Conjecture: a(n) = n*phi(n)/8 + O(n). - Thomas Ordowski, Nov 12 2014

G.f.: Sum_{n>=1} mu(n)*n*x^(2*n)/((1-x^n)*(1-x^(2*n))^2), where mu(n)=A008683(n). - Mamuka Jibladze, Apr 05 2015

For prime p: a(2p) = floor(p/2)^2. a(3p) = (p-1)(3p-1)/4, p>3. a(4p) = (p-1)*p, p>2. a(5p) = (p-1)(5p-1)/2, p=3 or p>5, ... - M. F. Hasler, Apr 09 2015

For odd prime p and e>0, a(p^e) = (p^(2e-1)+1)*(p-1)/8; a(2^e) = 4^(e-2) for e>1 (and a(2)=1). - Mamuka Jibladze, Apr 10 2015

If n == 0 (mod 4) then a(n) = n*phi(n)/8. - Robert Israel, Apr 13 2015

If n is prime then a(n) = binomial(1 + floor(n/2), 2). - David A. Corneth, Apr 14 2015

a(n) = (1/2) * Sum_{k=1..n} k * [gcd(k,2*n-k) = 2], where [ ] is the Iverson bracket. - Wesley Ivan Hurt, Jun 07 2021

Example

a(8) = 4 = 1 + 3 because 1 and 3 are the positive integers <= 8 / 2 = 4 and relatively prime to 8.
a(36) = 54. First, factor 36 = 2^2 * 3^2. look at distinct prime factors, 2 and 3. Add all positive integers up to floor(36/2) = 18, gives binomial(18 + 1, 2) = 171. Subtract all multiples of 2, i.e., subtract 2 * binomial(1+floor(18/2), 2) = 90, gives 171 - 90 = 81. Subtract all multiples of 3, i.e., subtract 3 * binomial(1+floor(18/3), 2) = 63, gives 81 - 63 = 18. Multiples of 2 * 3 = 6 were subtracted twice so add them, i.e., add 6 * binomial(1+floor(18/6), 2) = 36. Gives 18 + 36 = 54.
a(29#) = 826398242058977280 where p# is as in A002110. - David A. Corneth, Apr 14 2015

Maple

seq(convert(select(k->igcd(k, n)=1, [$1..floor(n/2)]), `+`), n=1..100); # Robert Israel, Apr 12 2015

Mathematica

f[n_] := Plus @@ Select[Range[Floor[n/2]], GCD[ #, n] == 1 &]; Table[f[n], {n, 65}] (* Ray Chandler, Dec 06 2006 *)

Prog

(PARI) for (n=1, 1000, k=1; s=0; while(k<=n/2, if (gcd(k, n) == 1, s+=k); k++); write("b066840.txt", n, " ", s) ) \\ Harry J. Smith, Apr 01 2010
(PARI) a(n) = sum(k=1, n\2, if (gcd(n, k)==1, k)); \\ Michel Marcus, Nov 12 2014
(PARI) a(n) = {my(h=n\2, d, b, r=0); f=factor(n)[, 1]; for(i=0, 2^#f - 1, b=binary(i); d=#f-#b; p=prod(j=1, #b, f[j+#f-#b]^b[j]); r += (-1)^vecsum(b) * p * binomial(1+h\p, 2)); r} \\ David A. Corneth, Apr 14 2015

Crossrefs

Cf. A124440, A124446, A124447, A282600, A282601.

Sequence in context: A370394 A021320 A193864 * A127754 A328508 A210841

Adjacent sequences: A066837 A066838 A066839 * A066841 A066842 A066843

Keyword

nonn

Author

Leroy Quet, Jan 20 2002

Status

approved