|
%I #146 Dec 03 2023 07:48:24
%S 1,1,3,4,10,6,21,16,27,20,55,24,78,42,60,64,136,54,171,80,126,110,253,
%T 96,250,156,243,168,406,120,465,256,330,272,420,216,666,342,468,320,
%U 820,252,903,440,540,506,1081,384,1029,500,816,624,1378,486,1100,672
%N Sum of positive integers in smallest positive reduced residue system modulo n. a(1) = 1 by convention.
%C Sum of totatives of n, i.e., sum of integers up to n and coprime to n.
%C a(1) = 1, since 1 is coprime to any positive integer.
%C Row sums of A038566. - _Wolfdieter Lang_, May 03 2015
%D Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 48, problem 16, the function phi_1(n).
%D David M. Burton, Elementary Number Theory, p. 171.
%D James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 2001, p. 163.
%D J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 111.
%H 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 John D. Baum, <a href="https://www.jstor.org/stable/2690056">A Number-Theoretic Sum</a>, Mathematics Magazine 55.2 (1982): 111-113.
%H 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 David Zmiaikou, <a href="https://tel.archives-ouvertes.fr/tel-00648120/">Origamis and permutation groups</a>, Thesis, 2011. See p. 65.
%F a(n) = n*A023022(n) for n>2.
%F 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 a(n) = Sum_{1 <= k < n, gcd(k, n) = 1} k.
%F 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 Equals A054521 * [1,2,3,...]. - _Gary W. Adamson_, May 20 2007
%F a(n) = A053818(n) * A175506(n) / A175505(n). - _Jaroslav Krizek_, Aug 01 2010
%F If m,n > 1 and gcd(m,n) = 1 then a(m*n) = 2*a(m)*a(n). - _Thomas Ordowski_, Nov 09 2014
%F 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 G.f. A(x) satisfies A(x) = x/(1 - x)^3 - Sum_{k>=2} k * A(x^k). - _Ilya Gutkovskiy_, Sep 06 2019
%F For n > 1: a(n) = (n*A076512(n)/2)*A009195(n). - _Jamie Morken_, Dec 16 2019
%F Sum_{n>=1} 1/a(n) = 2 * A065484 - 1 = 3.407713... . - _Amiram Eldar_, Oct 09 2023
%e 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 a(12) = 1 + 5 + 7 + 11 = 24.
%e 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 := proc(n)
%p if n = 1 then
%p 1;
%p else
%p n*numtheory[phi](n)/2 ;
%p end if;
%p end proc: # _R. J. Mathar_, Sep 26 2013
%t a[ n_ ] = n/2*EulerPhi[ n ]; a[ 1 ] = 1; Table[a[n], {n, 56}]
%t a[ n_] := If[ n < 2, Boole[n == 1], Sum[ k Boole[1 == GCD[n, k]], { k, n}]]; (* _Michael Somos_, Jul 08 2014 *)
%o (PARI) {a(n) = if(n<2, n>0, n*eulerphi(n)/2)};
%o (PARI) A023896(n)=n*eulerphi(n)\/2 \\ about 10% faster. - _M. F. Hasler_, Feb 01 2021
%o (Haskell)
%o a023896 = sum . a038566_row -- _Reinhard Zumkeller_, Mar 04 2012
%o (Magma) [1] cat [n*EulerPhi(n)/2: n in [2..70]]; // _Vincenzo Librandi_, May 16 2015
%o (Python)
%o from sympy import totient
%o def A023896(n): return 1 if n == 1 else n*totient(n)//2 # _Chai Wah Wu_, Apr 08 2022
%o (SageMath)
%o def A023896(n): return 1 if n == 1 else n*euler_phi(n)//2
%o print([A023896(n) for n in range(1, 57)]) # _Peter Luschny_, Dec 03 2023
%Y Cf. A000010, A000203, A002180, A045545, A001783, A024816, A066760, A054521, A067392, A038566.
%Y Row sums of A127368, A144734, A144824.
%Y Cf. A000217, A002618, A008683, A009195, A023022, A065484, A076512, A175505, A175506.
%K nonn,easy,nice
%O 1,3
%A _Olivier Gérard_
%E Typos in programs corrected by _Zak Seidov_, Aug 03 2010
%E Name and example edited by _Wolfdieter Lang_, May 03 2015
|
