cp's OEIS Frontend

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

%I A066840 #100 Jun 07 2021 21:13:25
%S A066840 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,
%T A066840 42,105,32,120,64,80,64,102,54,171,81,114,80,210,66,231,110,134,121,
%U A066840 276,96,258,124,200,156,351,121,270,168,252,196,435,120,465,225,282
%N A066840 Sum of positive integers k where k <= n/2 and gcd(k,n) = 1.
%C A066840 a(n) = n iff n = 16, 20, 24. - _Bernard Schott_, Mar 17 2021
%H A066840 Seiichi Manyama, <a href="/A066840/b066840.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from Harry J. Smith)
%H A066840 John D. Baum, <a href="https://www.jstor.org/stable/2690056">A Number-Theoretic Sum</a>, Mathematics Magazine 55.2 (1982): 111-113.
%H A066840 Karl Dilcher and Christophe Vignat, <a href="https://arxiv.org/abs/1801.09160">Infinite products involving Dirichlet characters and cyclotomic polynomials</a>, arXiv:1801.09160 [math.NT], 2018.
%H A066840 David Zmiaikou, <a href="https://tel.archives-ouvertes.fr/tel-00648120/">Origamis and permutation groups</a>, Thesis, 2011. See p. 65.
%F A066840 For odd prime p, a(p) = (p^2-1)/8. - _Thomas Ordowski_, Nov 12 2014
%F A066840 Conjecture: a(n) = n*phi(n)/8 + O(n). - _Thomas Ordowski_, Nov 12 2014
%F A066840 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
%F A066840 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
%F A066840 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
%F A066840 If n == 0 (mod 4) then a(n) = n*phi(n)/8. - _Robert Israel_, Apr 13 2015
%F A066840 If n is prime then a(n) = binomial(1 + floor(n/2), 2). - _David A. Corneth_, Apr 14 2015
%F A066840 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
%e A066840 a(8) = 4 = 1 + 3 because 1 and 3 are the positive integers <= 8 / 2 = 4 and relatively prime to 8.
%e A066840 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.
%e A066840 a(29#) = 826398242058977280 where p# is as in A002110. - _David A. Corneth_, Apr 14 2015
%p A066840 seq(convert(select(k->igcd(k,n)=1, [$1..floor(n/2)]),`+`),n=1..100); # _Robert Israel_, Apr 12 2015
%t A066840 f[n_] := Plus @@ Select[Range[Floor[n/2]], GCD[ #, n] == 1 &];Table[f[n], {n, 65}] (* _Ray Chandler_, Dec 06 2006 *)
%o A066840 (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
%o A066840 (PARI) a(n) = sum(k=1, n\2, if (gcd(n,k)==1, k)); \\ _Michel Marcus_, Nov 12 2014
%o A066840 (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
%Y A066840 Cf. A124440, A124446, A124447, A282600, A282601.
%K A066840 nonn
%O A066840 1,5
%A A066840 _Leroy Quet_, Jan 20 2002