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
Keywords
Examples
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
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.
Programs
-
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 *) -
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
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
Comments