login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A023896 Sum of positive integers in reduced residue system modulo n. a(1) = 1 by convention. 47
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

a(n) = Sum_{1<=k<=n, GCD(k,n)=1} k.

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.

a(n) = n*A023022(n) for n>2.

a(n) = A053818(n) * A175506(n) / A175505(n). For number n >= 1 holds B(n) = a(n) / A023896(n) = A175505(n) / A175506(n), where B(n) = antiharmonic mean of numbers k such that GCD(k, n) = 1 for k < n. Cf. A179871, A179872, A179873, A179874, A179875, A179876, A179877, A179878, A179879, A179880, A179882, A179883, A179884, A179885, A179886, A179887, A179890, A179891, A007645, A003627, A034934. - Jaroslav Krizek, Aug 01 2010

REFERENCES

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 48, problem 16, the function phi_1(n).

D. M. Burton, Elementary Number Theory, p. 171.

Tattersall, J. "Elementary Number Theory in Nine Chapters", Cambridge University Press, 2001, p. 163.

LINKS

Michael De Vlieger (First 1000 terms from T. D. Noe), Table of n, a(n) for n = 1..10000

FORMULA

a(n) = n*phi(n)/2 = A002618(n)/2 if n>1, a(1)=1.

a(n) = Sum{1 <= k < n, k for GCD(k, n) =1}.

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

Equals A054521 * [1,2,3,...]. - Gary W. Adamson, May 20 2007

If m,n > 1 and gcd(m,n)=1 then a(m*n) = 2*a(m)*a(n). - Thomas Ordowski, Nov 09 2014

EXAMPLE

a(12) = 1 + 5 + 7 + 11 = 24.

Reduced residue system for 40 = {1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39}.  The sum is 320.  Average is 20.

MAPLE

A023896 := proc(n)

    if n = 1 then

        1;

    else

        n*numtheory[phi](n)/2 ;

    end if;

end proc: # R. J. Mathar, Sep 26 2013

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)

a023896 = sum . a038566_row  -- Reinhard Zumkeller, Mar 04 2012

CROSSREFS

Cf. A000010, A000203, A002180, A045545, A001783, A024816, A066760, A054521, A067392, A038566.

Row sums of A127368, A144734, A144824.

Sequence in context: A143443 A139556 A191150 * A222136 A128488 A226303

Adjacent sequences:  A023893 A023894 A023895 * A023897 A023898 A023899

KEYWORD

nonn,easy,nice,changed

AUTHOR

Olivier Gérard

EXTENSIONS

Typos in programs corrected by Zak Seidov, Aug 03 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 19 00:39 EST 2014. Contains 252175 sequences.