cp's OEIS Frontend

A023896 Sum of positive integers in smallest positive reduced residue system modulo n. a(1) = 1 by convention.

%I A023896 #162 Jun 21 2024 13:17:56
%S A023896 1,1,3,4,10,6,21,16,27,20,55,24,78,42,60,64,136,54,171,80,126,110,253,
%T A023896 96,250,156,243,168,406,120,465,256,330,272,420,216,666,342,468,320,
%U A023896 820,252,903,440,540,506,1081,384,1029,500,816,624,1378,486,1100,672
%N A023896 Sum of positive integers in smallest positive reduced residue system modulo n. a(1) = 1 by convention.
%C A023896 Sum of totatives of n, i.e., sum of integers up to n and coprime to n.
%C A023896 a(1) = 1, since 1 is coprime to any positive integer.
%C A023896 Row sums of A038566. - _Wolfdieter Lang_, May 03 2015
%C A023896 Islam & Manzoor prove that a(n) is an injection for n > 1, see links. In other words, if a(m) = a(n), and min(m, n) > 1, then m = n. - _Muhammed Hedayet_, May 19 2024
%D A023896 Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 48, problem 16, the function phi_1(n).
%D A023896 David M. Burton, Elementary Number Theory, p. 171.
%D A023896 James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 2001, p. 163.
%D A023896 J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 111.
%H A023896 Michael De Vlieger, <a href="/A023896/b023896.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)
%H A023896 John D. Baum, <a href="https://www.jstor.org/stable/2690056">A Number-Theoretic Sum</a>, Mathematics Magazine 55.2 (1982): 111-113.
%H A023896 Geoffrey B. Campbell, <a href="https://ideas.repec.org/a/hin/jijmms/728942.html">Dirichlet summations and products over primes</a>, Int. J. Math. Math. Sci. 16 92) (1993) 359. eq. (3.1)
%H A023896 Muhammed H. Islam and Shahriar Manzoor, <a href="https://www.researchgate.net/publication/303459783">φ1 and phitorial are injections, for any positive integer N, where N > 1</a>.
%H A023896 Constantin M. Petridi, <a href="https://arxiv.org/abs/1612.07632">The Sums of the k-powers of the Euler set and their connection with Artin's conjecture for primitive roots</a>, arXiv:1612.07632 [math.NT], 2016.
%H A023896 David Zmiaikou, <a href="https://tel.archives-ouvertes.fr/tel-00648120/">Origamis and permutation groups</a>, Thesis, 2011. See p. 65.
%F A023896 a(n) = n*A023022(n) for n > 2.
%F A023896 a(n) = phi(n^2)/2 = n*phi(n)/2 = A002618(n)/2 if n > 1, a(1)=1. See the Apostol reference for this exercise.
%F A023896 a(n) = Sum_{1 <= k < n, gcd(k, n) = 1} k.
%F A023896 If n = p is a prime, a(p) = T(p-1) where T(k) is the k-th triangular number (A000217). - _Robert G. Wilson v_, Jul 31 2004
%F A023896 Equals A054521 * [1,2,3,...]. - _Gary W. Adamson_, May 20 2007
%F A023896 a(n) = A053818(n) * A175506(n) / A175505(n). - _Jaroslav Krizek_, Aug 01 2010
%F A023896 If m,n > 1 and gcd(m,n) = 1 then a(m*n) = 2*a(m)*a(n). - _Thomas Ordowski_, Nov 09 2014
%F A023896 G.f.: Sum_{n>=1} mu(n)*n*x^n/(1-x^n)^3, where mu(n) = A008683(n). - _Mamuka Jibladze_, Apr 24 2015
%F A023896 G.f. A(x) satisfies A(x) = x/(1 - x)^3 - Sum_{k>=2} k * A(x^k). - _Ilya Gutkovskiy_, Sep 06 2019
%F A023896 For n > 1: a(n) = (n*A076512(n)/2)*A009195(n). - _Jamie Morken_, Dec 16 2019
%F A023896 Sum_{n>=1} 1/a(n) = 2 * A065484 - 1 = 3.407713... . - _Amiram Eldar_, Oct 09 2023
%e A023896 G.f. = x + x^2 + 3*x^3 + 4*x^4 + 10*x^5 + 6*x^6 + 21*x^7 + 16*x^8 + 27*x^9 + ...
%e A023896 a(12) = 1 + 5 + 7 + 11 = 24.
%e A023896 n = 40: The smallest positive reduced residue system modulo 40 is {1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39}. The sum is a(40) = 320. Average is 20.
%p A023896 A023896 := proc(n)
%p A023896     if n = 1 then
%p A023896         1;
%p A023896     else
%p A023896         n*numtheory[phi](n)/2 ;
%p A023896     end if;
%p A023896 end proc: # _R. J. Mathar_, Sep 26 2013
%t A023896 a[ n_ ] = n/2*EulerPhi[ n ]; a[ 1 ] = 1; Table[a[n], {n, 56}]
%t A023896 a[ n_] := If[ n < 2, Boole[n == 1], Sum[ k Boole[1 == GCD[n, k]], { k, n}]]; (* _Michael Somos_, Jul 08 2014 *)
%o A023896 (PARI) {a(n) = if(n<2, n>0, n*eulerphi(n)/2)};
%o A023896 (PARI) A023896(n)=n*eulerphi(n)\/2 \\ about 10% faster. - _M. F. Hasler_, Feb 01 2021
%o A023896 (Haskell)
%o A023896 a023896 = sum . a038566_row  -- _Reinhard Zumkeller_, Mar 04 2012
%o A023896 (Magma) [1] cat [n*EulerPhi(n)/2: n in [2..70]]; // _Vincenzo Librandi_, May 16 2015
%o A023896 (Python)
%o A023896 from sympy import totient
%o A023896 def A023896(n): return 1 if n == 1 else n*totient(n)//2 # _Chai Wah Wu_, Apr 08 2022
%o A023896 (SageMath)
%o A023896 def A023896(n): return 1 if n == 1 else n*euler_phi(n)//2
%o A023896 print([A023896(n) for n in range(1, 57)])  # _Peter Luschny_, Dec 03 2023
%Y A023896 Cf. A000010, A000203, A002180, A045545, A001783, A024816, A066760, A054521, A067392, A038566.
%Y A023896 Row sums of A127368, A144734, A144824.
%Y A023896 Cf. A000217, A002618, A008683, A009195, A023022, A065484, A076512, A175505, A175506.
%K A023896 nonn,easy,nice
%O A023896 1,3
%A A023896 _Olivier Gérard_
%E A023896 Typos in programs corrected by _Zak Seidov_, Aug 03 2010
%E A023896 Name and example edited by _Wolfdieter Lang_, May 03 2015