|
|
A023896
|
|
Sum of positive integers in smallest positive reduced residue system modulo n. a(1) = 1 by convention.
|
|
91
|
|
|
1, 1, 3, 4, 10, 6, 21, 16, 27, 20, 55, 24, 78, 42, 60, 64, 136, 54, 171, 80, 126, 110, 253, 96, 250, 156, 243, 168, 406, 120, 465, 256, 330, 272, 420, 216, 666, 342, 468, 320, 820, 252, 903, 440, 540, 506, 1081, 384, 1029, 500, 816, 624, 1378, 486, 1100, 672
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Sum of totatives of n, i.e., sum of integers up to n and coprime to n.
a(1) = 1, since 1 is coprime to any positive integer.
|
|
REFERENCES
|
Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 48, problem 16, the function phi_1(n).
David M. Burton, Elementary Number Theory, p. 171.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 2001, p. 163.
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 111.
|
|
LINKS
|
|
|
FORMULA
|
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.
a(n) = Sum_{1 <= k < n, gcd(k, n) = 1} k.
If m,n > 1 and gcd(m,n) = 1 then a(m*n) = 2*a(m)*a(n). - Thomas Ordowski, Nov 09 2014
G.f. A(x) satisfies A(x) = x/(1 - x)^3 - Sum_{k>=2} k * A(x^k). - Ilya Gutkovskiy, Sep 06 2019
|
|
EXAMPLE
|
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 + ...
a(12) = 1 + 5 + 7 + 11 = 24.
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.
|
|
MAPLE
|
if n = 1 then
1;
else
n*numtheory[phi](n)/2 ;
end if;
|
|
MATHEMATICA
|
a[ n_ ] = n/2*EulerPhi[ n ]; a[ 1 ] = 1; Table[a[n], {n, 56}]
a[ n_] := If[ n < 2, Boole[n == 1], Sum[ k Boole[1 == GCD[n, k]], { k, n}]]; (* Michael Somos, Jul 08 2014 *)
|
|
PROG
|
(PARI) {a(n) = if(n<2, n>0, n*eulerphi(n)/2)};
(Haskell)
(Python)
from sympy import totient
(SageMath)
def A023896(n): return 1 if n == 1 else n*euler_phi(n)//2
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Typos in programs corrected by Zak Seidov, Aug 03 2010
|
|
STATUS
|
approved
|
|
|
|